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.util.*;
import java.io.BufferedOutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.math.*;
import static java.lang.Character.isDigit;
import static java.lang.Character.isLowerCase;
import static java.lang.Character.isUpperCase;
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Character.isDigit;

public class Main{
    
    static void debug(Object...os){
        System.err.println(deepToString(os));
    }
    long start;
    void test() {
        int n=1000,m=1000,a=1,b=1;
        int[][] is=new int[n][m];
        Random r = new Random(1249127498L);
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)is[i][j] = r.nextInt(1000000000);
        start = System.currentTimeMillis();
        solve(is,a,b);
        System.out.println(System.currentTimeMillis()-start);
        System.out.println("OK");
        System.out.flush();
    }
    
    void run(){
        System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
//      test();
        
        int n=nextInt(),m=nextInt(),a=nextInt(),b=nextInt();
        int[][] is=new int[n][m];
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)is[i][j]=nextInt();
        solve(is,a,b);
    }
    void solve(int[][] is,int a,int b) {
        int n=is.length,m=is[0].length;
        long[][] S=new long[n+1][m+1];
        for(int i=0;i<n;i++)for(int j=0;j<m;j++) {
            S[i+1][j+1] = is[i][j] + S[i+1][j] + S[i][j+1] - S[i][j];
        }
        int[][] rowMin = new int[n][m-b+1];
        RMQ row = new RMQ(is[0]);
        for(int i=0;i<n;i++) {
            row.clear(is[i]);
            for(int j=0;j<m-b+1;j++)rowMin[i][j] = is[i][row.query(j,j+b)];
        }
        int[][] min=new int[n-a+1][m-b+1];
        RMQ col = new RMQ(new int[n]);
        for(int j=0;j<m-b+1;j++) {
            int[] js=new int[n];
            for(int i=0;i<n;i++)js[i]=rowMin[i][j];
            col.clear(js);
            for(int i=0;i<n-a+1;i++) {
                min[i][j] = js[col.query(i,i+a)];
            }
        }
        
        tick();
        
        E[] es = new E[(n-a+1)*(m-b+1)];
        for(int i=0,i2=0;i<n-a+1;i++)for(int j=0;j<m-b+1;j++) {
            long val = S[i+a][j+b] - S[i][j+b] - S[i+a][j] + S[i][j] - (long)min[i][j] * a*b;
            es[i2++]=new E(val,i,j);
        }
        
        tick();
        
        sort(es);
        
        tick();
        
        boolean[][] bs=new boolean[n][m];
        int cnt=0;
        for(E e:es) {
            int x=e.x,y=e.y;
            if(!bs[x][y] && !bs[x+a-1][y] && !bs[x][y+b-1] && !bs[x+a-1][y+b-1]) {
                cnt++;
                for(int i=0;i<a;i++)for(int j=0;j<b;j++) {
                    bs[x+i][y+j]=true;
                }
            }
        }
        System.out.println(cnt);
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)bs[i][j]=false;
        for(E e:es) {
            int x=e.x,y=e.y;
            if(!bs[x][y] && !bs[x+a-1][y] && !bs[x][y+b-1] && !bs[x+a-1][y+b-1]) {
                sb.append((x+1)+" "+(y+1)+" "+e.val+"\n");
                for(int i=0;i<a;i++)for(int j=0;j<b;j++) {
                    bs[x+i][y+j]=true;
                }
                if(sb.length()>100000) {
                    System.out.println(sb);
                    sb.setLength(0);
                }
            }
        }
        System.out.println(sb);
        System.out.flush();
    }
    private void tick(){
//      System.out.println(System.currentTimeMillis()-start);
    }
    class E implements Comparable<E>{
        long val;
        int x,y;
        private E(long val,int x,int y){
            super();
            this.val=val;
            this.x=x;
            this.y=y;
        }
        public int compareTo(E o){
            if(val!=o.val)return Long.signum(val-o.val);
            if(x!=o.x)return x-o.x;
            return y-o.y;
        }
    }
    
    public class RangeMinimumQuery{
        int[] v;
        
        public RangeMinimumQuery(int size){
            v=new int[size];
        }
        
        public void update(int at,int what){
            if(at<0) at=0;
            while(at<v.length){
                v[at]=Math.min(v[at],what);
                at=at|(at+1);
            }
        }
        
        public int getMin(int right){// [0,right]
            int res=0;
            while(right>=0){
                res=Math.min(res,v[right]);
                right=(right&(right+1))-1;
            }
            return res;
        }
    }
        
    class RMQ {
        int[] vs;
        int[][] min;
        int n,m;
        RMQ(int[] vs) {
            n = vs.length; m = log2(n) + 1;
            this.vs = vs;
            min = new int[m][n];
            for (int i = 0; i < n; i++) min[0][i] = i;
            for (int i = 1, k = 1; i < m; i++, k <<= 1) {
                for (int j = 0; j + k < n; j++) {
                    min[i][j] = vs[min[i - 1][j]] <= vs[min[i - 1][j + k]] ?
                        min[i - 1][j] : min[i - 1][j + k];
                }
            }
        }
        void clear(int[] vs) {
            for(int i=0;i<n;i++)this.vs[i]=vs[i];
            for (int i = 0; i < n; i++) min[0][i] = i;
            for (int i = 1, k = 1; i < m; i++, k <<= 1) {
                for (int j = 0; j + k < n; j++) {
                    min[i][j] = vs[min[i - 1][j]] <= vs[min[i - 1][j + k]] ?
                        min[i - 1][j] : min[i - 1][j + k];
                }
            }
        }
        
        int query(int from, int to) {
            int k = log2(to - from);
            return vs[min[k][from]] <= vs[min[k][to - (1 << k)]] ?
                min[k][from] : min[k][to - (1 << k)];
        }
        int log2(int b) {
            return 31 - Integer.numberOfLeadingZeros(b);
        }
    }
    
    int nextInt(){
        try{
            int c=System.in.read();
            if(c==-1) return c;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=System.in.read();
                if(c==-1) return c;
            }
            if(c=='-') return -nextInt();
            int res=0;
            do{
                res*=10;
                res+=c-'0';
                c=System.in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }
    
    long nextLong(){
        try{
            int c=System.in.read();
            if(c==-1) return -1;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=System.in.read();
                if(c==-1) return -1;
            }
            if(c=='-') return -nextLong();
            long res=0;
            do{
                res*=10;
                res+=c-'0';
                c=System.in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }
    
    double nextDouble(){
        return Double.parseDouble(next());
    }
    
    String next(){
        try{
            StringBuilder res=new StringBuilder("");
            int c=System.in.read();
            while(Character.isWhitespace(c))
                c=System.in.read();
            do{
                res.append((char)c);
            }while(!Character.isWhitespace(c=System.in.read()));
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }
    
    String nextLine(){
        try{
            StringBuilder res=new StringBuilder("");
            int c=System.in.read();
            while(c=='\r'||c=='\n')
                c=System.in.read();
            do{
                res.append((char)c);
                c=System.in.read();
            }while(c!='\r'&&c!='\n');
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }
    public static void main(String[] args){
        new Main().run();
    }
}