Problem: There is an area map that is a rectangular matrix n × m, each cell of the matrix contains the average height of a corresponding area part. Peter works for a company that has to build several cities within this area, each of the cities will occupy a rectangle a × b cells on the map. To start construction works in a particular place Peter needs to remove excess ground from the construction site where a new city will be built. To do so he chooses a cell of the minimum height within this site, and removes excess ground from other cells of the site down to this minimum level. Let's consider that to lower the ground level from h2 to h1 (h1 ≤ h2) they need to remove h2 - h1 ground units.

Let's call a site's position optimal, if the amount of the ground removed from this site is minimal compared to other possible positions. Peter constructs cities according to the following algorithm: from all the optimum site's positions he chooses the uppermost one. If this position is not unique, he chooses the leftmost one. Then he builds a city on this site. Peter repeats this process untill he can build at least one more city. For sure, he cannot carry out construction works on the occupied cells. Would you, please, help Peter place cities according to the algorithm? 

Input

The first line contains four space-separated integers: map sizes n, m and city sizes a, b (1 ≤ a ≤ n ≤ 1000, 1 ≤ b ≤ m ≤ 1000). Then there follow n lines, each contains m non-negative space-separated numbers, describing the height matrix. Each number doesn't exceed 109. 

Output

In the first line output k — the amount of constructed cities. In each of the following k lines output 3 space-separated numbers — the row number and the column number of the upper-left corner of a subsequent construction site, and the amount of the ground to remove from it. Output the sites in the order of their building up.

Examples

Input

2 2 1 2
1 2
3 5


Output

2
1 1 1
2 1 2


Input

4 4 2 2
1 5 3 4
2 7 6 1
1 1 2 2
2 2 1 2


Output

3
3 1 2
3 3 3
1 2 9

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.*;
import java.util.*;
//import java.util.stream.*;

@SuppressWarnings("unchecked")
public class P15D {

  final static int SHIFT = 10;
  final static int MASK = (1 << SHIFT) - 1;

  int n, m, a, b, na, mb;
  int [][] h = null;
  ArrayList<long []> calcMins_Sums() {
    long sums, ab = a * b;
    ArrayList<long []> calc = new ArrayList(na * mb);
    int [][] hm = new int [na][m];
    long [][] hs = new long [na][m];
    int [] mins = new int [Math.max(n, m) + 1];
    int mh, mt;

    for (int x = 0; x < m; x++) {
      sums = mh = mt = 0;

      for (int y = 0; y < n; y++) {
        if (y >= a) {
          hs[y - a][x] = sums;
          sums -= h[y - a][x];
          hm[y - a][x] = mins[mh];
          if (mins[mh] == h[y - a][x]) { mh++; }
        }

        sums += h[y][x];
        for (; (mt > mh) && (mins[mt - 1] > h[y][x]); mt--);
        mins[mt] = h[y][x];
        mt++;
      }

      hs[n - a][x] = sums;
      hm[n - a][x] = mins[mh];
    }

    for (int y = 0; y < na; y++ ) {
      sums = mh = mt = 0;

      for (int x = 0; x < m; x++) {
        if (x >= b) {
//          calc.add(((sums - (long)mins[mh] * (long)ab) * (long)na * (long)mb) + (y * mb) + (x - b));
          calc.add(new long [] {sums - mins[mh] * ab, (y << SHIFT) | (x - b)});
          sums -= hs[y][x - b];
          if (mins[mh] == hm[y][x - b]) { mh++; }
        }
        
        sums += hs[y][x];
        for (; (mt > mh) && (mins[mt - 1] > hm[y][x]); mt--);
        mins[mt] = hm[y][x];
        mt++;
      }

//      calc.add(((sums - (long)mins[mh] * (long)ab) * (long)na * (long)mb) + (y * mb) + (m - b));
        calc.add(new long [] {sums - mins[mh] * ab, (y << SHIFT) | (m - b)});
    }

    return calc;
  }
// ------------------------------------------------------------------
  public void run() throws Exception {
    n = nextInt();
    m = nextInt();
    a = nextInt();
    b = nextInt();
    h = new int [n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        h[i][j] = nextInt();
      }
    }
//n = 1000; m = 1000; a = 5; b = 5; h = new int [n][m]; Random r = new Random(); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) h[i][j] = r.nextInt(1_000_000);
//startTime = System.currentTimeMillis();
    na = n - a + 1;
    mb = m - b + 1;

    ArrayList<long []> sites = calcMins_Sums();
//System.err.println("[Time (site)  : " + (System.currentTimeMillis() - startTime) + " ms]");
//for (int i = 0; i < (na * mb); i++) { if ((i % mb) == 0) println(); print((sites.get(i) >>> SHIFT >>> SHIFT) + "\t"); } println();

//    sites.sort(new Comparator<long []> (){
    Collections.sort(sites, new Comparator<long []> (){
      @Override
      public int compare(long [] a, long [] b) {
        if (a[0] < b[0]) {
          return -1;
        } else if (a[0] > b[0]) {
          return 1;
        } else {
          return (int)(a[1] - b[1]);
        }
      }
    });
//System.err.println("[Time (sort) : " + (System.currentTimeMillis() - startTime) + " ms]");
//for (int i = 0; i < (na * mb); i++) { if ((i % mb) == 0) println(); print(sites.get(i) + "\t"); } println();

    ArrayList<long []> result = new ArrayList();
    boolean [][] used = new boolean [na][mb];
    for (long [] site : sites) {
      int xx = (int)(site[1] & MASK);
      int yy = (int)(site[1] >> SHIFT);

      if (!used[yy][xx]) {
        result.add(site);

        for (int y = Math.max(yy - a + 1, 0); y < Math.min(yy + a, na); y++) {
          for (int x = Math.max(xx - b + 1, 0); x < Math.min(xx + b, mb); x++) {
            used[y][x] = true;
          }
        }
      }
    }
//System.err.println("[Time (done) : " + (System.currentTimeMillis() - startTime) + " ms]");

    println(result.size());
    for (long [] site : result) {
      println(((site[1] >> SHIFT) + 1) + " " + ((site[1] & MASK) + 1) + " " + site[0]);
    }
  }

// #5 : 10 10 3 3  20 30 97 51 18 21 53 48 46 35  80 80 65 78 47 69 5 35 11 75  67 53 95 67 9 76 68 31 100 81  23 48 3 82 52 0 47 98 50 65  30 74 50 30 40 22 100 46 82 56  17 53 67 67 37 16 73 58 82 95  94 80 50 46 83 83 50 86 81 5  22 79 25 82 80 29 76 18 83 73  80 72 97 50 15 61 15 88 65 90  87 78 51 28 97 70 72 16 66 23
  public static void main(String... args) throws Exception {
    br = new BufferedReader(new InputStreamReader(System.in));
    pw = new PrintWriter(new BufferedOutputStream(System.out));
    new P15D().run();
    br.close();
    pw.close();
//    System.err.println("\n[Time : " + (System.currentTimeMillis() - startTime) + " ms]");
  }

//  static long startTime = 0;System.currentTimeMillis();
  static BufferedReader br;
  static PrintWriter pw;
  StringTokenizer stok;

  String nextToken() throws IOException {
    while (stok == null || !stok.hasMoreTokens()) {
      String s = br.readLine();
      if (s == null) { return null; }
      stok = new StringTokenizer(s);
    }
    return stok.nextToken();
  }

  void print(byte b) { print("" + b); }
  void print(int i) { print("" + i); }
  void print(long l) { print("" + l); }
  void print(double d) { print("" + d); }
  void print(char c) { print("" + c); }
  void print(Object o) {
    if (o instanceof int[]) { print(Arrays.toString((int [])o));
    } else if (o instanceof long[]) { print(Arrays.toString((long [])o));
    } else if (o instanceof char[]) { print(Arrays.toString((char [])o));
    } else if (o instanceof byte[]) { print(Arrays.toString((byte [])o));
    } else if (o instanceof short[]) { print(Arrays.toString((short [])o));
    } else if (o instanceof boolean[]) { print(Arrays.toString((boolean [])o));
    } else if (o instanceof float[]) { print(Arrays.toString((float [])o));
    } else if (o instanceof double[]) { print(Arrays.toString((double [])o));
    } else if (o instanceof Object[]) { print(Arrays.toString((Object [])o));
    } else { print("" + o); }
  }
  void print(String s) { pw.print(s); }
  void println() { println(""); }
  void println(byte b) { println("" + b); }
  void println(int i) { println("" + i); }
  void println(long l) { println("" + l); }
  void println(double d) { println("" + d); }
  void println(char c) { println("" + c); }
  void println(Object o) { print(o); println(); }
  void println(String s) { pw.println(s); }
  int nextInt() throws IOException { return Integer.parseInt(nextToken()); }
  long nextLong() throws IOException { return Long.parseLong(nextToken()); }
  double nextDouble() throws IOException { return Double.parseDouble(nextToken()); }
  char nextChar() throws IOException { return (char) (br.read()); }
  String next() throws IOException { return nextToken(); }
  String nextLine() throws IOException { return br.readLine(); }
  int [] readInt(int size) throws IOException {
    int [] array = new int [size];
    for (int i = 0; i < size; i++) { array[i] = nextInt(); }
    return array;
  }
  long [] readLong(int size) throws IOException {
    long [] array = new long [size];
    for (int i = 0; i < size; i++) { array[i] = nextLong(); }
    return array;
  }
  double [] readDouble(int size) throws IOException {
    double [] array = new double [size];
    for (int i = 0; i < size; i++) { array[i] = nextDouble(); }
    return array;
  }
  String [] readLines(int size) throws IOException {
    String [] array = new String [size];
    for (int i = 0; i < size; i++) { array[i] = nextLine(); }
    return array;
  }
}