import java.util.*;
import java.util.zip.*;
import java.util.List;
import java.util.regex.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.table.*;
import java.io.*;
import java.net.*;
import java.lang.reflect.*;
import java.lang.ref.*;
import java.lang.management.*;
import java.security.*;
import java.security.spec.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.imageio.*;
import java.math.*;

class main {

  final static class IntegralImage {

    final int w, h;

    // 3 ints per pixel
    final int[] data;

    /* *(BufferedImage img) {
    w = img.getWidth();
    h = img.getHeight();
    if (longMul(w, h) > 8000000) fail("Image too big: " + w + "*" + h);
    int[] pixels = pixelsOfBufferedImage(img);
  */
    IntegralImage(int w, int h, int[] pixels) {
      this.h = h;
      this.w = w;
      data = new int[w * h * 3];
      int i = 0, j = 0, sumR = 0, sumG = 0, sumB = 0;
      for (int x = 0; x < w; x++) {
        int rgb = pixels[j++];
        data[i++] = (sumR += (rgb >> 16) & 0xFF);
        data[i++] = (sumG += (rgb >> 8) & 0xFF);
        data[i++] = (sumB += rgb & 0xFF);
      }
      for (int y = 1; y < h; y++) {
        sumR = sumG = sumB = 0;
        for (int x = 0; x < w; x++) {
          int rgb = pixels[j++];
          sumR += (rgb >> 16) & 0xFF;
          sumG += (rgb >> 8) & 0xFF;
          sumB += rgb & 0xFF;
          data[i] = sumR + data[i - w * 3];
          data[i + 1] = sumG + data[i - w * 3 + 1];
          data[i + 2] = sumB + data[i - w * 3 + 2];
          i += 3;
        }
      }
    }

    // gets the integral value at x/y for given RGB channel
    public double getIntegralValue(int x, int y, int channel) {
      return x < 0 || y < 0 || x >= w || y >= h ? 0 : data[(y * w + x) * 3 + channel];
    }

    // gets sum of the 3 channels
    public double getIntegralValue(int x, int y) {
      if (x < 0 || y < 0 || x >= w || y >= h)
        return 0;
      int i = (y * w + x) * 3;
      return data[i] + data[i + 1] + data[i + 2];
    }

    double averageBrightness() {
      return doubleRatio(getIntegralValue(w - 1, h - 1), w * h * 3 * 255.0);
    }

    public String toString() {
      return "IntegralImage " + w + "*" + h + ", brightness: " + this.averageBrightness();
    }

    // public BufferedImage getBufferedImage() { ret integralImageToBufferedImage(this); }
    public int getWidth() {
      return w;
    }

    public int getHeight() {
      return h;
    }

    double rectSum(int x1, int y1, int x2, int y2, int channel) {
      double bottomLeft = getIntegralValue(x1 - 1, y2 - 1, channel);
      double bottomRight = getIntegralValue(x2 - 1, y2 - 1, channel);
      double topLeft = getIntegralValue(x1 - 1, y1 - 1, channel);
      double topRight = getIntegralValue(x2 - 1, y1 - 1, channel);
      return bottomRight + topLeft - topRight - bottomLeft;
    }

    double rectSum(int x1, int y1, int x2, int y2) {
      double bottomLeft = getIntegralValue(x1 - 1, y2 - 1);
      double bottomRight = getIntegralValue(x2 - 1, y2 - 1);
      double topLeft = getIntegralValue(x1 - 1, y1 - 1);
      double topRight = getIntegralValue(x2 - 1, y1 - 1);
      return bottomRight + topLeft - topRight - bottomLeft;
    }
  }

  static double doubleRatio(double x, double y) {
    return y == 0 ? 0 : x / y;
  }
}