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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
const double pi = acos(-1.0);
const double eps = 1e-11;
template <class T>
inline void checkmin(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
inline void checkmax(T &a, T b) {
  if (b > a) a = b;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
typedef pair<int, int> ipair;
template <class T>
inline T lowbit(T n) {
  return (n ^ (n - 1)) & n;
}
template <class T>
inline int countbit(T n) {
  return (n == 0) ? 0 : (1 + countbit(n & (n - 1)));
}
template <class T>
inline T gcd(T a, T b) {
  if (a < 0) return gcd(-a, b);
  if (b < 0) return gcd(a, -b);
  return (b == 0) ? a : gcd(b, a % b);
}
template <class T>
inline T lcm(T a, T b) {
  if (a < 0) return lcm(-a, b);
  if (b < 0) return lcm(a, -b);
  return a * (b / gcd(a, b));
}
template <class T>
inline T euclide(T a, T b, T &x, T &y) {
  if (a < 0) {
    T d = euclide(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = euclide(a, -b, x, y);
    y = -y;
    return d;
  }
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = euclide(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
template <class T>
inline vector<pair<T, int> > factorize(T n) {
  vector<pair<T, int> > R;
  for (T i = 2; n > 1;) {
    if (n % i == 0) {
      int C = 0;
      for (; n % i == 0; C++, n /= i)
        ;
      R.push_back(make_pair(i, C));
    }
    i++;
    if (i > n / i) i = n;
  }
  if (n > 1) R.push_back(make_pair(n, 1));
  return R;
}
template <class T>
inline bool isPrimeNumber(T n) {
  if (n <= 1) return false;
  for (T i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
template <class T>
inline T eularFunction(T n) {
  vector<pair<T, int> > R = factorize(n);
  T r = n;
  for (int i = 0; i < R.size(); i++) r = r / R[i].first * (R[i].first - 1);
  return r;
}
const int MaxMatrixSize = 40;
template <class T>
inline void showMatrix(int n, T A[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) cout << A[i][j];
    cout << endl;
  }
}
template <class T>
inline T checkMod(T n, T m) {
  return (n % m + m) % m;
}
template <class T>
inline void identityMatrix(int n, T A[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) A[i][j] = (i == j) ? 1 : 0;
}
template <class T>
inline void addMatrix(int n, T C[MaxMatrixSize][MaxMatrixSize],
                      T A[MaxMatrixSize][MaxMatrixSize],
                      T B[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) C[i][j] = A[i][j] + B[i][j];
}
template <class T>
inline void subMatrix(int n, T C[MaxMatrixSize][MaxMatrixSize],
                      T A[MaxMatrixSize][MaxMatrixSize],
                      T B[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) C[i][j] = A[i][j] - B[i][j];
}
template <class T>
inline void mulMatrix(int n, T C[MaxMatrixSize][MaxMatrixSize],
                      T _A[MaxMatrixSize][MaxMatrixSize],
                      T _B[MaxMatrixSize][MaxMatrixSize]) {
  T A[MaxMatrixSize][MaxMatrixSize], B[MaxMatrixSize][MaxMatrixSize];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      A[i][j] = _A[i][j], B[i][j] = _B[i][j], C[i][j] = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++) C[i][j] += A[i][k] * B[k][j];
}
template <class T>
inline void addModMatrix(int n, T m, T C[MaxMatrixSize][MaxMatrixSize],
                         T A[MaxMatrixSize][MaxMatrixSize],
                         T B[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) C[i][j] = checkMod(A[i][j] + B[i][j], m);
}
template <class T>
inline void subModMatrix(int n, T m, T C[MaxMatrixSize][MaxMatrixSize],
                         T A[MaxMatrixSize][MaxMatrixSize],
                         T B[MaxMatrixSize][MaxMatrixSize]) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) C[i][j] = checkMod(A[i][j] - B[i][j], m);
}
template <class T>
inline T multiplyMod(T a, T b, T m) {
  return (T)((((int64)(a) * (int64)(b) % (int64)(m)) + (int64)(m)) %
             (int64)(m));
}
template <class T>
inline void mulModMatrix(int n, T m, T C[MaxMatrixSize][MaxMatrixSize],
                         T _A[MaxMatrixSize][MaxMatrixSize],
                         T _B[MaxMatrixSize][MaxMatrixSize]) {
  T A[MaxMatrixSize][MaxMatrixSize], B[MaxMatrixSize][MaxMatrixSize];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      A[i][j] = _A[i][j], B[i][j] = _B[i][j], C[i][j] = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++)
        C[i][j] = (C[i][j] + multiplyMod(A[i][k], B[k][j], m)) % m;
}
template <class T>
inline T powerMod(T p, int e, T m) {
  if (e == 0)
    return 1 % m;
  else if (e % 2 == 0) {
    T t = powerMod(p, e / 2, m);
    return multiplyMod(t, t, m);
  } else
    return multiplyMod(powerMod(p, e - 1, m), p, m);
}
double dist(double x1, double y1, double x2, double y2) {
  return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}
double distR(double x1, double y1, double x2, double y2) {
  return sqr(x1 - x2) + sqr(y1 - y2);
}
template <class T>
T cross(T x0, T y0, T x1, T y1, T x2, T y2) {
  return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
}
int crossOper(double x0, double y0, double x1, double y1, double x2,
              double y2) {
  double t = (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
  if (fabs(t) <= eps) return 0;
  return (t < 0) ? -1 : 1;
}
bool isIntersect(double x1, double y1, double x2, double y2, double x3,
                 double y3, double x4, double y4) {
  return crossOper(x1, y1, x2, y2, x3, y3) * crossOper(x1, y1, x2, y2, x4, y4) <
             0 &&
         crossOper(x3, y3, x4, y4, x1, y1) * crossOper(x3, y3, x4, y4, x2, y2) <
             0;
}
bool isMiddle(double s, double m, double t) {
  return fabs(s - m) <= eps || fabs(t - m) <= eps || (s < m) != (t < m);
}
bool isUpperCase(char c) { return c >= 'A' && c <= 'Z'; }
bool isLowerCase(char c) { return c >= 'a' && c <= 'z'; }
bool isLetter(char c) { return c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z'; }
bool isDigit(char c) { return c >= '0' && c <= '9'; }
char toLowerCase(char c) { return (isUpperCase(c)) ? (c + 32) : c; }
char toUpperCase(char c) { return (isLowerCase(c)) ? (c - 32) : c; }
template <class T>
string toString(T n) {
  ostringstream ost;
  ost << n;
  ost.flush();
  return ost.str();
}
int toInt(string s) {
  int r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
int64 toInt64(string s) {
  int64 r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
double toDouble(string s) {
  double r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
template <class T>
void stoa(string s, int &n, T A[]) {
  n = 0;
  istringstream sin(s);
  for (T v; sin >> v; A[n++] = v)
    ;
}
template <class T>
void atos(int n, T A[], string &s) {
  ostringstream sout;
  for (int i = 0; i < n; i++) {
    if (i > 0) sout << ' ';
    sout << A[i];
  }
  s = sout.str();
}
template <class T>
void atov(int n, T A[], vector<T> &vi) {
  vi.clear();
  for (int i = 0; i < n; i++) vi.push_back(A[i]);
}
template <class T>
void vtoa(vector<T> vi, int &n, T A[]) {
  n = vi.size();
  for (int i = 0; i < n; i++) A[i] = vi[i];
}
template <class T>
void stov(string s, vector<T> &vi) {
  vi.clear();
  istringstream sin(s);
  for (T v; sin >> v; vi.push_bakc(v))
    ;
}
template <class T>
void vtos(vector<T> vi, string &s) {
  ostringstream sout;
  for (int i = 0; i < vi.size(); i++) {
    if (i > 0) sout << ' ';
    sout << vi[i];
  }
  s = sout.str();
}
template <class T>
struct Fraction {
  T a, b;
  Fraction(T a = 0, T b = 1);
  string toString();
};
template <class T>
Fraction<T>::Fraction(T a, T b) {
  T d = gcd(a, b);
  a /= d;
  b /= d;
  if (b < 0) a = -a, b = -b;
  this->a = a;
  this->b = b;
}
template <class T>
string Fraction<T>::toString() {
  ostringstream sout;
  sout << a << "/" << b;
  return sout.str();
}
template <class T>
Fraction<T> operator+(Fraction<T> p, Fraction<T> q) {
  return Fraction<T>(p.a * q.b + q.a * p.b, p.b * q.b);
}
template <class T>
Fraction<T> operator-(Fraction<T> p, Fraction<T> q) {
  return Fraction<T>(p.a * q.b - q.a * p.b, p.b * q.b);
}
template <class T>
Fraction<T> operator*(Fraction<T> p, Fraction<T> q) {
  return Fraction<T>(p.a * q.a, p.b * q.b);
}
template <class T>
Fraction<T> operator/(Fraction<T> p, Fraction<T> q) {
  return Fraction<T>(p.a * q.b, p.b * q.a);
}
const int maxsize = 1000 + 5;
int n, m, a, b;
int A[maxsize][maxsize], B[maxsize][maxsize];
int64 SA[maxsize][maxsize];
int sizeQ;
pair<int64, int> Q[maxsize * maxsize];
int r_cnt, r_pos[maxsize * maxsize];
int64 r_cost[maxsize * maxsize];
int C[maxsize][maxsize];
void solve(int n, int A[], int R[], int L) {
  int next[maxsize], stack[maxsize], size;
  stack[size = 0] = n + 1;
  for (int i = n; i >= 1; i--) {
    for (; size > 0 && A[stack[size]] >= A[i]; size--)
      ;
    next[i] = stack[size];
    stack[++size] = i;
  }
  int key = 1;
  for (int i = 1; i <= n - L + 1; i++) {
    if (key < i) key = i;
    for (; next[key] <= i + L - 1; key = next[key])
      ;
    R[i] = A[key];
  }
}
void addC(int x0, int y0) {
  for (int x = x0; x <= n; x = (x | (x - 1)) + 1)
    for (int y = y0; y <= m; y = (y | (y - 1)) + 1) C[x][y]++;
}
int getC(int x0, int y0) {
  int R = 0;
  for (int x = x0; x > 0; x &= (x - 1))
    for (int y = y0; y > 0; y &= (y - 1)) R += C[x][y];
  return R;
}
int main() {
  vector<int> R;
  scanf("%d%d%d%d", &n, &m, &a, &b);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) scanf("%d", &A[i][j]);
  for (int i = 1; i <= n; i++) solve(m, A[i], B[i], b);
  for (int j = 1; j <= m - b + 1; j++) {
    int C[maxsize], D[maxsize];
    for (int i = 1; i <= n; i++) C[i] = B[i][j];
    solve(n, C, D, a);
    for (int i = 1; i <= n - a + 1; i++) B[i][j] = D[i];
  }
  memset(SA, 0, sizeof(SA));
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      SA[i][j] = SA[i - 1][j] + SA[i][j - 1] - SA[i - 1][j - 1] + A[i][j];
  sizeQ = 0;
  for (int i = a; i <= n; i++)
    for (int j = b; j <= m; j++)
      Q[sizeQ++] =
          make_pair(SA[i][j] + SA[i - a][j - b] - SA[i - a][j] - SA[i][j - b] -
                        (int64)a * (int64)b * (int64)B[i - a + 1][j - b + 1],
                    i * 10000 + j);
  sort(Q, Q + sizeQ);
  r_cnt = 0;
  memset(C, 0, sizeof(C));
  for (int step = 0; step < sizeQ; step++) {
    int x2 = Q[step].second / 10000;
    int y2 = Q[step].second % 10000;
    int x1 = x2 - a + 1;
    int y1 = y2 - b + 1;
    if (getC(x2, y2) + getC(x1 - 1, y1 - 1) - getC(x2, y1 - 1) -
            getC(x1 - 1, y2) ==
        0) {
      r_pos[r_cnt] = x1 * 10000 + y1;
      r_cost[r_cnt++] = Q[step].first;
      for (int x = x1; x <= x2; x++)
        for (int y = y1; y <= y2; y++) addC(x, y);
    }
  }
  printf("%d\n", r_cnt);
  for (int i = 0; i < r_cnt; i++)
    printf("%d %d %I64d\n", r_pos[i] / 10000, r_pos[i] % 10000, r_cost[i]);
  return 0;
}