import javax.imageio.*;
import java.awt.image.*;
import java.awt.*;
import java.security.NoSuchAlgorithmException;
import java.security.MessageDigest;
import java.lang.reflect.*;
import java.net.*;
import java.io.*;
import javax.swing.*;
import java.util.regex.*;
import java.util.List;
import java.util.*;

import static java.lang.Math.*;

class RGB {
  public final float r, g, b;

  public RGB(float r, float g, float b) {
    this.r = r;
    this.g = g;
    this.b = b;
  }

  public RGB(double r, double g, double b) {
    this.r = (float) r;
    this.g = (float) g;
    this.b = (float) b;
  }

  public RGB(double brightness) {
    this.r = this.g = this.b = (float) brightness;
  }

  public RGB(Color color) {
    this.r = color.getRed()/255f;
    this.g = color.getGreen()/255f;
    this.b = color.getBlue()/255f;
  }

  public RGB(String hex) {
    r = Integer.parseInt(hex.substring(0, 2), 16)/255f;
    g = Integer.parseInt(hex.substring(2, 4), 16)/255f;
    b = Integer.parseInt(hex.substring(4, 6), 16)/255f;
  }

  public float getComponent(int i) {
    return i == 0 ? r : i == 1 ? g : b;
  }

  public Color getColor() {
    return new Color(r, g, b);
  }

  public static RGB newSafe(float r, float g, float b) {
    return new RGB(Math.max(0, Math.min(1, r)), Math.max(0, Math.min(1, g)), Math.max(0, Math.min(1, b)));
  }

  public int asInt() {
    return getColor().getRGB() & 0xFFFFFF;
  }

  public float getBrightness() {
    return (r+g+b)/3.0f;
  }

  public String getHexString() {
    return Integer.toHexString(asInt() | 0xFF000000).substring(2).toUpperCase();
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof RGB)) return false;

    RGB rgb = (RGB) o;

    if (Float.compare(rgb.b, b) != 0) return false;
    if (Float.compare(rgb.g, g) != 0) return false;
    if (Float.compare(rgb.r, r) != 0) return false;

    return true;
  }

  @Override
  public int hashCode() {
    int result = (r != +0.0f ? Float.floatToIntBits(r) : 0);
    result = 31 * result + (g != +0.0f ? Float.floatToIntBits(g) : 0);
    result = 31 * result + (b != +0.0f ? Float.floatToIntBits(b) : 0);
    return result;
  }

  public boolean isBlack() {
    return r == 0f && g == 0f && b == 0f;
  }

  public boolean isWhite() {
    return r == 1f && g == 1f && b == 1f;
  }

  public String toString() {
    return getHexString();
  }
}

class RGBImage {
  private BufferedImage bufferedImage;
  private File file;
  private int width, height;
  private int[] pixels;

  // color returned when getPixel is called with out-of-bounds position
  private int background = 0xFFFFFF;

  public RGBImage(BufferedImage image) {
    this(image, null);
  }

  public RGBImage(BufferedImage image, File file) {
    this.file = file;
    bufferedImage = image;
    width = image.getWidth();
    height = image.getHeight();
    pixels = new int[width*height];
    PixelGrabber pixelGrabber = new PixelGrabber(image, 0, 0, width, height, pixels, 0, width);
    try {
      if (!pixelGrabber.grabPixels())
        throw new RuntimeException("Could not grab pixels");
      cleanPixels(); // set upper byte to 0
    } catch (InterruptedException e) {
      throw new RuntimeException(e);
    }
  }

  /** We assume it's a file name to load from */
  public RGBImage(String file) throws IOException {
    this(new File(file));
  }

  public RGBImage(Dimension size, Color color) {
    this(size.width, size.height, color);
  }

  public RGBImage(Dimension size, RGB color) {
    this(size.width, size.height, color);
  }

  private void cleanPixels() {
    for (int i = 0; i < pixels.length; i++)
      pixels[i] &= 0xFFFFFF;
  }

  public RGBImage(int width, int height, int[] pixels) {
    this.width = width;
    this.height = height;
    this.pixels = pixels;
  }

  public RGBImage(int w, int h, RGB[] pixels) {
    this.width = w;
    this.height = h;
    this.pixels = asInts(pixels);
  }

  public static int[] asInts(RGB[] pixels) {
    int[] ints = new int[pixels.length];
    for (int i = 0; i < pixels.length; i++)
      ints[i] = pixels[i] == null ? 0 : pixels[i].getColor().getRGB();
    return ints;
  }

  public RGBImage(int w, int h, RGB rgb) {
    this.width = w;
    this.height = h;
    this.pixels = new int[w*h];
    int col = rgb.asInt();
    if (col != 0)
      for (int i = 0; i < pixels.length; i++)
        pixels[i] = col;
  }

  public RGBImage(RGBImage image) {
    this(image.width, image.height, copyPixels(image.pixels));
  }

  public RGBImage(int width, int height, Color color) {
    this(width, height, new RGB(color));
  }

  public RGBImage(File file) throws IOException {
    this(javax.imageio.ImageIO.read(file));
  }

  private static int[] copyPixels(int[] pixels) {
    int[] copy = new int[pixels.length];
    System.arraycopy(pixels, 0, copy, 0, pixels.length);
    return copy;
  }

  public int getIntPixel(int x, int y) {
    if (inRange(x, y))
      return pixels[y * width + x];
    else
      return background;
  }

  public static RGB asRGB(int packed) {
    int r = (packed >> 16) & 0xFF;
    int g = (packed >> 8) & 0xFF;
    int b = packed & 0xFF;
    return new RGB(r / 255f, g / 255f, b / 255f);
  }

  public RGB getRGB(int x, int y) {
    if (inRange(x, y))
      return asRGB(pixels[y * width + x]);
    else
      return new RGB(background);
  }

  /** alias of getRGB - I kept typing getPixel instead of getRGB all the time, so I finally created it */
  public RGB getPixel(int x, int y) {
    return getRGB(x, y);
  }

  public int getWidth() {
    return width;
  }

  public int getHeight() {
    return height;
  }

  /** Attention: cached, i.e. does not change when image itself changes */
  /** @NotNull */
  public BufferedImage getBufferedImage() {
    if (bufferedImage == null) {
      bufferedImage = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
      //bufferedImage.setData(Raster.createRaster(new SampleModel()));
      for (int y = 0; y < height; y++)
        for (int x = 0; x < width; x++)
          bufferedImage.setRGB(x, y, pixels[y*width+x]);
    }
    return bufferedImage;
  }

  public RGBImage clip(Rectangle r) {
    r = fixClipRect(r);
    int[] newPixels;
    try {
      newPixels = new int[r.width*r.height];
    } catch (RuntimeException e) {
      System.out.println(r);
      throw e;
    }
    for (int y = 0; y < r.height; y++) {
      System.arraycopy(pixels, (y+r.y)*width+r.x, newPixels, y*r.width, r.width);
    }
    return new RGBImage(r.width, r.height, newPixels);
  }

  private Rectangle fixClipRect(Rectangle r) {
    r = r.intersection(new Rectangle(0, 0, width, height));
    if (r.isEmpty())
      r = new Rectangle(r.x, r.y, 0, 0);
    return r;
  }

  public File getFile() {
    return file;
  }

  /** can now also do GIF (not just JPEG) */
  public static RGBImage load(String fileName) {
    return load(new File(fileName));
  }

  /** can now also do GIF (not just JPEG) */
  public static RGBImage load(File file) {
    try {
      BufferedImage bufferedImage = javax.imageio.ImageIO.read(file);
      return new RGBImage(bufferedImage);
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
  }

  public int getInt(int x, int y) {
    return pixels[y * width + x];
  }

  public void save(File file) throws IOException {
    String name = file.getName().toLowerCase();
    String type;
    if (name.endsWith(".png")) type = "png";
    else if (name.endsWith(".jpg") || name.endsWith(".jpeg")) type = "jpeg";
    else throw new IOException("Unknown image extension: " + name);
    javax.imageio.ImageIO.write(getBufferedImage(), type, file);
  }

  public static RGBImage dummyImage() {
    return new RGBImage(1, 1, new int[] {0xFFFFFF});
  }

  public int[] getPixels() {
    return pixels;
  }

  public void setPixel(int x, int y, RGB rgb) {
    if (x >= 0 && y >= 0 && x < width && y < height)
      pixels[y*width+x] = rgb.asInt();
  }

  public void setPixel(int x, int y, Color color) {
    setPixel(x, y, new RGB(color));
  }

  public void setPixel(int x, int y, int rgb) {
    if (x >= 0 && y >= 0 && x < width && y < height)
      pixels[y*width+x] = rgb;
  }

  public RGBImage copy() {
    return new RGBImage(this);
  }

  public boolean inRange(int x, int y) {
    return x >= 0 && y >= 0 && x < width && y < height;
  }

  public int getBackground() {
    return background;
  }

  public void setBackground(int background) {
    this.background = background;
  }

  public Dimension getSize() {
    return new Dimension(width, height);
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    RGBImage rgbImage = (RGBImage) o;

    if (height != rgbImage.height) return false;
    if (width != rgbImage.width) return false;
    if (!Arrays.equals(pixels, rgbImage.pixels)) return false;

    return true;
  }

  @Override
  public int hashCode() {
    int result = width;
    result = 31 * result + height;
    result = 31 * result + Arrays.hashCode(pixels);
    return result;
  }

  public String getHex(int x, int y) {
    return getPixel(x, y).getHexString();
  }

  public RGBImage clip(int x, int y, int width, int height) {
    return clip(new Rectangle(x, y, width, height));
  }

  public RGBImage clipLine(int y) {
    return clip(0, y, width, 1);
  }

  public int numPixels() {
    return width*height;
  }
}

abstract class Surface extends JPanel {


  public Object AntiAlias = RenderingHints.VALUE_ANTIALIAS_ON;
  public Object Rendering = RenderingHints.VALUE_RENDER_SPEED;
  public AlphaComposite composite;
  public Paint texture;
  public BufferedImage bimg;
  public int imageType;
  public String name;
  public boolean clearSurface = true;
  // Demos using animated gif's that implement ImageObserver set dontThread.
  public boolean dontThread;

  protected long sleepAmount = 50; // max20 fps

  private long orig, start, frame;
  private Toolkit toolkit;
  private boolean perfMonitor, outputPerf;
  private int biw, bih;
  private boolean clearOnce;
  private boolean toBeInitialized = true;


  public Surface() {
    setDoubleBuffered(false);
    toolkit = getToolkit();
    name = this.getClass().getName();
    name = name.substring(name.indexOf(".", 7)+1);
    setImageType(0);

    // To launch an individual demo with the performance str output  :
    //    java -Djava2demo.perf= -cp Java2Demo.jar demos.Clipping.ClipAnim
    try {
      if (System.getProperty("java2demo.perf") != null) {
        perfMonitor = outputPerf = true;
      }
    } catch (Exception ex) { }
  }


    /*protected Image getImage(String name) {
        return DemoImages.getImage(name, this);
    }


    protected Font getFont(String name) {
        return DemoFonts.getFont(name);
    }*/


  public int getImageType() {
    return imageType;
  }


  public void setImageType(int imgType) {
    if (imgType == 0) {
      imageType = 1;
    } else {
      imageType = imgType;
    }
    bimg = null;
  }


  public void setAntiAlias(boolean aa) {
    AntiAlias = aa
      ? RenderingHints.VALUE_ANTIALIAS_ON
      : RenderingHints.VALUE_ANTIALIAS_OFF;
  }


  public void setRendering(boolean rd) {
    Rendering = rd
      ? RenderingHints.VALUE_RENDER_QUALITY
      : RenderingHints.VALUE_RENDER_SPEED;
  }


  public void setTexture(Object obj) {
    if (obj instanceof GradientPaint) {
      texture = new GradientPaint(0, 0, Color.white,
        getSize().width*2, 0, Color.green);
    } else {
      texture = (Paint) obj;
    }
  }


  public void setComposite(boolean cp) {
    composite = cp
      ? AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 0.5f)
      : null;
  }


  public void setMonitor(boolean pm) {
    perfMonitor = pm;
  }


  public void setSleepAmount(long amount) {
    sleepAmount = amount;
  }


  public long getSleepAmount() {
    return sleepAmount;
  }


  public BufferedImage createBufferedImage(Graphics2D g2,
                                           int w,
                                           int h,
                                           int imgType) {
    BufferedImage bi = null;
    if (imgType == 0) {
      bi = (BufferedImage) g2.getDeviceConfiguration().
        createCompatibleImage(w, h);
    } else if (imgType > 0 && imgType < 14) {
      bi = new BufferedImage(w, h, imgType);
    } else if (imgType == 14) {
      bi = createBinaryImage(w, h, 2);
    } else if (imgType == 15) {
      bi = createBinaryImage(w, h, 4);
    } else if (imgType == 16) {
      bi = createSGISurface(w, h, 32);
    } else if (imgType == 17) {
      bi = createSGISurface(w, h, 16);
    }
    biw = w;
    bih = h;
    return bi;
  }


  // Lookup tables for BYTE_BINARY 1, 2 and 4 bits.
  static byte[] lut1Arr = new byte[] {0, (byte)255 };
  static byte[] lut2Arr = new byte[] {0, (byte)85, (byte)170, (byte)255};
  static byte[] lut4Arr = new byte[] {0, (byte)17, (byte)34, (byte)51,
    (byte)68, (byte)85,(byte) 102, (byte)119,
    (byte)136, (byte)153, (byte)170, (byte)187,
    (byte)204, (byte)221, (byte)238, (byte)255};


  private BufferedImage createBinaryImage(int w, int h, int pixelBits) {
    int bytesPerRow = w * pixelBits / 8;
    if (w * pixelBits % 8 != 0) {
      bytesPerRow++;
    }
    byte[] imageData = new byte[h * bytesPerRow];
    IndexColorModel cm = null;
    switch (pixelBits) {
      case 1:
        cm = new IndexColorModel(pixelBits, lut1Arr.length,
          lut1Arr, lut1Arr, lut1Arr);
        break;
      case 2:
        cm = new IndexColorModel(pixelBits, lut2Arr.length,
          lut2Arr, lut2Arr, lut2Arr);
        break;
      case 4:
        cm = new IndexColorModel(pixelBits, lut4Arr.length,
          lut4Arr, lut4Arr, lut4Arr);
        break;
      default:
      {new Exception("Invalid # of bit per pixel").printStackTrace();}
    }

    DataBuffer db = new DataBufferByte(imageData, imageData.length);
    WritableRaster r = Raster.createPackedRaster(db, w, h, pixelBits, null);
    return new BufferedImage(cm, r, false, null);
  }

  private BufferedImage createSGISurface(int w, int h, int pixelBits) {
    int rMask32 = 0xFF000000;
    int rMask16 = 0xF800;
    int gMask32 = 0x00FF0000;
    int gMask16 = 0x07C0;
    int bMask32 = 0x0000FF00;
    int bMask16 = 0x003E;

    DirectColorModel dcm = null;
    DataBuffer db = null;
    WritableRaster wr = null;
    switch (pixelBits) {
      case 16:
        short[] imageDataUShort = new short[w * h];
        dcm = new DirectColorModel(16, rMask16, gMask16, bMask16);
        db = new DataBufferUShort(imageDataUShort, imageDataUShort.length);
        wr = Raster.createPackedRaster(db, w, h, w,
          new int[] {rMask16, gMask16, bMask16},
          null);
        break;
      case 32:
        int[] imageDataInt = new int[w * h];
        dcm = new DirectColorModel(32, rMask32, gMask32, bMask32);
        db = new DataBufferInt(imageDataInt, imageDataInt.length);
        wr = Raster.createPackedRaster(db, w, h, w,
          new int[] {rMask32, gMask32, bMask32},
          null);
        break;
      default:
      {new Exception("Invalid # of bit per pixel").printStackTrace();}
    }

    return new BufferedImage(dcm, wr, false, null);
  }

  public Graphics2D createGraphics2D(int width,
                                     int height,
                                     BufferedImage bi,
                                     Graphics g) {

    Graphics2D g2 = null;

    if (bi != null) {
      g2 = bi.createGraphics();
    } else {
      g2 = (Graphics2D) g;
    }

    g2.setBackground(getBackground());
    g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, AntiAlias);
    g2.setRenderingHint(RenderingHints.KEY_RENDERING, Rendering);

    if (clearSurface || clearOnce) {
      g2.clearRect(0, 0, width, height);
      clearOnce = false;
    }

    if (texture != null) {
      // set composite to opaque for texture fills
      g2.setComposite(AlphaComposite.SrcOver);
      g2.setPaint(texture);
      g2.fillRect(0, 0, width, height);
    }

    if (composite != null) {
      g2.setComposite(composite);
    }

    return g2;
  }

  public abstract void render(int w, int h, Graphics2D g);


  /**
   * It's possible to turn off double-buffering for just the repaint
   * calls invoked directly on the non double buffered component.
   * This can be done by overriding paintImmediately() (which is called
   * as a result of repaint) and getting the current RepaintManager and
   * turning off double buffering in the RepaintManager before calling
   * super.paintImmediately(g).
   */
  public void paintImmediately(int x,int y,int w, int h) {
    RepaintManager repaintManager = null;
    boolean save = true;
    if (!isDoubleBuffered()) {
      repaintManager = RepaintManager.currentManager(this);
      save = repaintManager.isDoubleBufferingEnabled();
      repaintManager.setDoubleBufferingEnabled(false);
    }
    super.paintImmediately(x, y, w, h);

    if (repaintManager != null) {
      repaintManager.setDoubleBufferingEnabled(save);
    }
  }


  public void paint(Graphics g) {

    Dimension d = getSize();

    if (imageType == 1)
      bimg = null;
    else if (bimg == null || biw != d.width || bih != d.height) {
      bimg = createBufferedImage((Graphics2D)g,
        d.width, d.height, imageType-2);
      clearOnce = true;
      toBeInitialized = true;
    }

    if (toBeInitialized) {
      toBeInitialized = false;
      startClock();
    }

    Graphics2D g2 = createGraphics2D(d.width, d.height, bimg, g);
    render(d.width, d.height, g2);
    g2.dispose();

    if (bimg != null)  {
      g.drawImage(bimg, 0, 0, null);
      toolkit.sync();
    }

  }


  public void startClock() {
    orig = System.currentTimeMillis();
    start = orig;
    frame = 0;
  }

  private static final int REPORTFRAMES = 30;


  public static void setAlpha(Graphics2D g, float alpha) {
    g.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, alpha));
  }
}

class ImageSurface extends Surface {
  private BufferedImage image;
  private double zoomX = 1, zoomY = 1;
  private Rectangle selection;

  public ImageSurface() {
    this(new RGBImage(1, 1, new int[] { 0xFFFFFF }));
  }

  public ImageSurface(RGBImage image) {
    this(image.getBufferedImage());
  }

  public ImageSurface(BufferedImage image) {
    clearSurface = false;
    this.image = image;

    /*addMouseMotionListener(new MouseAdapter() {
      public void mouseMoved(MouseEvent e) {
        getMousePosition()

      }
    });*/
  }

  public ImageSurface(RGBImage image, double zoom) {
    this(image);
    setZoom(zoom);
  }

  public void render(int w, int h, Graphics2D g) {
    g.setColor(Color.white);
    g.fillRect(0, 0, w, h);
    if (image != null)
      g.drawImage(image, 0, 0, getZoomedWidth(), getZoomedHeight(), null);

    if (selection != null) {
      // drawRect is inclusive, selection is exclusive, so... whatever, tests show it's cool.
      drawSelectionRect(g, selection, Color.green, Color.white);
    }
  }

  public void drawSelectionRect(Graphics2D g, Rectangle selection, Color green, Color white) {
    g.setColor(green);
    int top = (int) (selection.y * zoomY);
    int bottom = (int) ((selection.y+selection.height) * zoomY);
    int left = (int) (selection.x * zoomX);
    int right = (int) ((selection.x+selection.width) * zoomX);
    g.drawRect(left-1, top-1, right-left+1, bottom-top+1);
    g.setColor(white);
    g.drawRect(left - 2, top - 2, right - left + 3, bottom - top + 3);
  }

  public void setZoom(double zoom) {
    setZoom(zoom, zoom);
  }

  public void setZoom(double zoomX, double zoomY) {
    this.zoomX = zoomX;
    this.zoomY = zoomY;
    revalidate();
    repaint();
  }

  public Dimension getMinimumSize() {
    int w = getZoomedWidth();
    int h = getZoomedHeight();
    Dimension min = super.getMinimumSize();
    return new Dimension(Math.max(w, min.width), Math.max(h, min.height));
  }

  private int getZoomedHeight() {
    return (int) (image.getHeight() * zoomY);
  }

  private int getZoomedWidth() {
    return (int) (image.getWidth() * zoomX);
  }

  public void setImage(RGBImage image) {
    setImage(image.getBufferedImage());
  }

  public void setImage(BufferedImage image) {
    this.image = image;
    revalidate();
    repaint();
  }

  public BufferedImage getImage() {
    return image;
  }

  public double getZoomX() {
    return zoomX;
  }

  public double getZoomY() {
    return zoomY;
  }

  public Dimension getPreferredSize() {
    return new Dimension(getZoomedWidth(), getZoomedHeight());
  }

  /** returns a scrollpane with the scroll-mode prevent-garbage-drawing fix applied */
  public JScrollPane makeScrollPane() {
    JScrollPane scrollPane = new JScrollPane(this);
    scrollPane.getViewport().setScrollMode(JViewport.BACKINGSTORE_SCROLL_MODE);
    return scrollPane;
  }

  public void zoomToDisplaySize() {
    if (image == null) return;
    Dimension display = getDisplaySize();
    double xRatio = display.width/(double) image.getWidth();
    double yRatio = display.height/(double) image.getHeight();
    setZoom(Math.min(xRatio, yRatio));
    revalidate();
  }

  /** tricky magic to get parent scroll pane */
  private Dimension getDisplaySize() {
    Container c = getParent();
    while (c != null) {
      if (c instanceof JScrollPane)
        return c.getSize();
      c = c.getParent();
    }
    return getSize();
  }

  public void setSelection(Rectangle r) {
    selection = r;
    repaint();
  }

  public Rectangle getSelection() {
    return selection;
  }

  public RGBImage getRGBImage() {
    return new RGBImage(getImage());
  }
}
class FrameWithImages {
  JFrame frame;
  ImageSurface[] surfaces;
  int n;
  
  FrameWithImages(int numImages) {
    frame = new JFrame("A JavaX Frame");
    
    n = numImages;
    JPanel grid = new JPanel(new GridLayout(n, 1));
    surfaces = new ImageSurface[n];
    for (int i = 0; i < n; i++)
      grid.add(surfaces[i] = new ImageSurface());
    
    frame.add(grid);
    frame.setBounds(100, 100, 100+400+20, 100+600);
  }
  
  void hop() {
    frame.setVisible(true);
    main.exitOnFrameClose(frame);
  }
  
  void setImage(int i, RGBImage img) {
    if (i >= 0 && i < n)
      surfaces[i].setImage(img);
  }
  
  void setInnerSize(RGBImage img) {
    setInnerSize(img.getWidth(), img.getHeight());
  }
  
  void setInnerSize(int w, int h) {
    double zoom = surfaces[0].getZoomX();
    frame.setSize((int) (w*zoom)+20, (int) (h*zoom*n)+40); // todo...
  }
  
  void setZoom(double zoom) {
    for (ImageSurface s : surfaces) s.setZoom(zoom);
  }
}


public class main {
    static RGB probeRandomPixel(RGBImage image) {
    int x = (int) (random()*(image.getWidth()-1));
    int y = (int) (random()*(image.getHeight()-1));
    return image.getPixel(x, y);
  }
  
  static RGB randomColor() {
    return new RGB(random(), random(), random());
  }
  
  static RGBImage resizeToWidth(RGBImage image, int w) {
    return resize(image, w, (int) ((image.getHeight()*(double) w)/image.getWidth()));
  }
  
  public static RGBImage resize(RGBImage image, int w, int h) {
    if (w == image.getWidth() && h == image.getHeight()) return image;

    int[] pixels = new int[w*h];
    for (int y = 0; y < h; y++)
      for (int x = 0; x < w; x++)
        pixels[y*w+x] = image.getInt(x*image.getWidth()/w, y*image.getHeight()/h);
    return new RGBImage(w, h, pixels);
  }

  static Random _random = new Random();
  static double random() {
    return _random.nextInt(100001)/100000.0;
  }
  
  static int random(int max) {
    return _random.nextInt(max);
  }
  
  static double random(double min, double max) {
    return min+random()*(max-min);
  }
  
  static double normalize(double d) {
    return Math.max(0, Math.min(1, d));
  }
  
  static int round(double d) {
    return (int) Math.round(d);
  }
  
  static double mix(double a, double b, double bishness) {
    return a+(b-a)*bishness;
  }
  
  public static double pixelDiff(RGB a, RGB b) {
    return (Math.abs(a.r-b.r) + Math.abs(a.g-b.g) + Math.abs(a.b-b.b))/3;
  }

  public static double diff(RGBImage image, RGBImage image2) {
    int w = image.getWidth(), h = image.getHeight();
    double sum = 0;
    for (int y = 0; y < h; y++)
      for (int x = 0; x < w; x++)
        sum += pixelDiff(image.getRGB(x, y), image2.getRGB(x, y));
    return sum/(w*h);
  }
  
  public static void copy(RGBImage src, int srcX, int srcY, RGBImage dst, int dstX, int dstY, int w, int h) {
    for (int y = 0; y < h; y++)
      for (int x = 0; x < w; x++)
        dst.setPixel(dstX+x, dstY+y, src.getPixel(srcX+x, srcY+y));
  }
  
  static float varyChannel(float x) {
    return Math.max(0f, Math.min(1f, (float) (x+random(-0.1, 0.1))));
  }
  
  static double vary01(double x) {
    return Math.max(0, Math.min(1, x+random(-0.1, 0.1)));
  }
  
  static RGB varyColor(RGB rgb) {
    int s = random(3);
    if (s == 0)
      return new RGB(varyChannel(rgb.r), rgb.g, rgb.b);
    else if (s == 1)
      return new RGB(rgb.r, varyChannel(rgb.g), rgb.b);
    else
      return new RGB(rgb.r, rgb.g, varyChannel(rgb.b));
  }
 // helper functions

  // St = Structure
  static abstract class St {
    abstract double def(double x, double y);
  }
  
  static class SConst extends St {
    double value;
    
    SConst(double value) {
  this.value = value;}
    
    double def(double x, double y) {
      return value;
    }
  }
  
  static class SX extends St {
    double def(double x, double y) {
      return x;
    }
  }
  
  static class SY extends St {
    double def(double x, double y) {
      return y;
    }
  }
  
  static class SSin extends St {
    St a;
    SSin(St a) {
  this.a = a;}
    
    double def(double x, double y) {
      return sin(a.def(x, y));
    }
  }
  
  static class SCos extends St {
    St a;
    SCos(St a) {
  this.a = a;}
    
    double def(double x, double y) {
      return cos(a.def(x, y));
    }
  }
  
  static class SPlus extends St {
    St a, b;
    SPlus(St a, St b) {
  this.b = b;
  this.a = a;}
    
    double def(double x, double y) {
      return a.def(x, y) + b.def(x, y);
    }
  }
  
  static class SMinus extends St {
    St a, b;
    SMinus(St a, St b) {
  this.b = b;
  this.a = a;}
    
    double def(double x, double y) {
      return a.def(x, y) - b.def(x, y);
    }
  }
  
  static class SMul extends St {
    St a, b;
    SMul(St a, St b) {
  this.b = b;
  this.a = a;}
    
    double def(double x, double y) {
      return a.def(x, y) * b.def(x, y);
    }
  }
  
  static class SDiv extends St {
    St a, b;
    SDiv(St a, St b) {
  this.b = b;
  this.a = a;}
    
    double def(double x, double y) {
      return a.def(x, y) / b.def(x, y);
    }
  }
  
  static class SSwitch extends St {
    St a, b, c;
    SSwitch(St a, St b, St c) {
  this.c = c;
  this.b = b;
  this.a = a;}
    
    double def(double x, double y) {
      return a.def(x, y) < 0 ? b.def(x, y) : c.def(x, y);
    }
  }
  
  static St randomConst() {
    int n = random(2);
    double d;
    if (n == 0) d = random(-10.0, 10.0);
    else d = random(0.0, 1.0);
    return new SConst(d);
  }
  
  static St makeStructure(int budget) {
    if (budget < 1)
      fail("no budget");
    int n = random(min(3, budget));
    if (n == 0)
      return makeStructure1();
    if (n == 1)
      return makeStructure2(budget);
    return makeStructure3(budget);
  }
  
  static St makeStructure1() {
    int n = random(3);
    if (n == 0) return randomConst();
    else if (n == 1) return new SX();
    else return new SY();
  }
  
  static St makeStructure2(int budget) {
    int n = random(6);
    if (n == 0) return new SSin(makeStructure(budget-1));
    else if (n == 1) return new SCos(makeStructure(budget-1));
    
    // split budget among parts
    int b1 = 1+random(budget-1), b2 = budget-b1;
    //System.out.println((budget+1) + " => " + b1 + "/" + b2);
    
    St a = makeStructure(b1), b = makeStructure(b2);
    if (n == 2) return new SPlus(a, b);
    if (n == 3) return new SMinus(a, b);
    if (n == 4) return new SMul(a, b);
    return new SDiv(a, b);
  }
  
  static St makeStructure3(int budget) {
    // split budget among parts
    int b1 = 1+random(budget-2);
    int b2 = 1+random(budget-1-b1);
    int b3 = budget-b1-b2;
    St a = makeStructure(b1), b = makeStructure(b2), c = makeStructure(b3);
    return new SSwitch(a, b, c);
  }
  
  static RGBImage render(St st, int w, int h) {
    RGBImage img = new RGBImage(w, h, Color.white);
     for (int y = 0; y < h; y++)
      for (int x = 0; x < w; x++) {
        double nx = x/(double)(w-1);
        double ny = y/(double)(h-1);
        double d = st.def(nx, ny);
        d = min(1, max(0, d));
        img.setPixel(x, y, new RGB(d, d, d));
      }
    return img;
  }
  
  static FrameWithImages fwi;
  static int budget = 4;
  static int numImages = 8;
  static int delay = 100;
  
  public static void main(String[] args) throws Exception {
    fwi = new FrameWithImages(numImages);
    fwi.hop();
    final int w = 50, h = 50;
    
    for (int i = 0; i < args.length; i++) {
      String a = args[i];
      if (a.equals("budget"))
        budget = Integer.parseInt(args[++i]);
    }
    
    fwi.setInnerSize(w, h);

    Thread _t = new Thread() {
public void run() {
try {

      int n = 0;
      while (true) {
        St struct = makeStructure(budget);
        RGBImage img = render(struct, w, h);
        fwi.setImage(n, img);
        n = (n+1) % numImages;
        System.out.println(structure(struct));
        Thread.sleep(delay);
      }
    } catch (Exception _e) {
  throw _e instanceof RuntimeException ? (RuntimeException) _e : new RuntimeException(_e); } }
};
_t.start();
  }
  
   static String structure(Object o) {
    if (o == null) return "null";
    String name = o.getClass().getName();
    
    StringBuilder buf = new StringBuilder();
    
    if (o instanceof Collection) {
      for (Object x : (Collection) o) {
        if (buf.length() != 0) buf.append(", ");
        buf.append(structure(x));
      }
      return "{" + buf + "}";
    }
    
    if (o.getClass().isArray()) {
      int n = Array.getLength(o);
      for (int i = 0; i < n; i++) {
        if (buf.length() != 0) buf.append(", ");
        buf.append(structure(Array.get(o, i)));
      }
      return "{" + buf + "}";
    }

    if (o instanceof String)
      return quote((String) o);
    
    // Need more cases? This should cover all library classes...
    if (name.startsWith("java.") || name.startsWith("javax."))
      return String.valueOf(o);
      
    String shortName = o.getClass().getName().replaceAll("^main\\$", "");

    // TODO: go to superclasses too
    Field[] fields = o.getClass().getDeclaredFields();
    int numFields = 0;
    String fieldName = "";
    for (Field field : fields) {
      if ((field.getModifiers() & Modifier.STATIC) != 0)
        continue;
      Object value;
      try {
        value = field.get(o);
      } catch (Exception e) {
        value = "?";
      }
      
      fieldName = field.getName();
      
      // insert special cases here

      if (value != null) {
        if (buf.length() != 0) buf.append(", ");
        buf.append(fieldName + "=" + structure(value));
      }
      ++numFields;
    }
    String b = buf.toString();
    if (numFields == 1)
      b = b.replaceAll("^" + fieldName + "=", ""); // drop field name if only one
    String s = shortName;
    if (buf.length() != 0)
      s += "(" + b + ")";
    return s;
  }
  

  static void exitOnFrameClose(JFrame frame) {
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  }


  public static String quote(String s) {
    if (s == null) return "null";
    return "\"" + s.replace("\\", "\\\\").replace("\"", "\\\"").replace("\r", "\\r").replace("\n", "\\n") + "\"";
  }

  static Class<?> getClass(String name) {
    try {
      return Class.forName(name);
    } catch (ClassNotFoundException e) {
      return null;
    }
  }

  static void set(Class c, String field, Object value) {
    try {
      Field f = set_findStaticField(c, field);
      f.setAccessible(true);
      f.set(null, value);
    } catch (Exception e) {
      throw new RuntimeException(e);
    }
  }
  
  static Field set_findStaticField(Class<?> c, String field) {
    for (Field f : c.getDeclaredFields())
      if (f.getName().equals(field) && (f.getModifiers() & Modifier.STATIC) != 0)
        return f;
    throw new RuntimeException("Static field '" + field + "' not found in " + c.getName());
  }

  static void fail() {
    throw new RuntimeException("fail");
  }
  
  static void fail(String msg) {
    throw new RuntimeException(msg);
  }
}