#include <bits/stdc++.h>
template <typename Type>
class SegmentTree {
 public:
  Type (*func)(const Type&, const Type&);

 private:
  unsigned _size;
  std::vector<Type> _tree;
  std::vector<Type> _plus;
  void __build(const std::vector<Type>& vec, unsigned v, unsigned l,
               unsigned r) {
    if (l == r)
      _tree[v] = vec[l];
    else {
      unsigned m = (l + r) >> 1;
      __build(vec, v << 1, l, m);
      __build(vec, (v << 1) | 1, m + 1, r);
      _tree[v] = func(_tree[v << 1], _tree[(v << 1) | 1]);
    }
  }
  void __build_equal(unsigned v, unsigned tl, unsigned tr, const Type& value) {
    if (tl == tr)
      _tree[v] = value;
    else {
      unsigned tm = (tl + tr) >> 1;
      __build_equal(v << 1, tl, tm, value);
      __build_equal((v << 1) | 1, tm + 1, tr, value);
      _tree[v] = func(_tree[v << 1], _tree[(v << 1) | 1]);
    }
  }
  std::pair<Type, bool> __get(unsigned v, unsigned l, unsigned r, unsigned tl,
                              unsigned tr) {
    if (r < l) return std::pair<Type, bool>(NULL, false);
    if (l == tl && r == tr) return std::pair<Type, bool>(_tree[v], true);
    unsigned tm = (tl + tr) >> 1;
    std::pair<Type, bool> _f1 = __get(v << 1, l, min(r, tm), tl, tm);
    std::pair<Type, bool> _f2 =
        __get((v << 1) + 1, max(l, tm + 1), r, tm + 1, tr);
    if (_f1.second && _f2.second)
      return std::pair<Type, bool>(func(_f1.first, _f2.first) + _plus[v], true);
    if (_f1.second) {
      _f1.first += _plus[v];
      return _f1;
    }
    _f2.first += _plus[v];
    return _f2;
  }
  void __update(unsigned v, unsigned tl, unsigned tr, unsigned pos,
                const Type& newValue) {
    if (tl == tr)
      _tree[v] = newValue;
    else {
      unsigned tm = (tl + tr) >> 1;
      if (pos <= tm)
        __update(v << 1, tl, tm, pos, newValue);
      else
        __update((v << 1) | 1, tm + 1, tr, pos, newValue);
      _tree[v] = func(_tree[v << 1], _tree[(v << 1) | 1]) + _plus[v];
    }
  }
  void __change(unsigned v, unsigned tl, unsigned tr, unsigned pos,
                const Type& delta) {
    if (tl == tr)
      _tree[v] += delta;
    else {
      unsigned tm = (tl + tr) >> 1;
      if (pos <= tm)
        __change(v << 1, tl, tm, pos, delta);
      else
        __change((v << 1) | 1, tm + 1, tr, pos, delta);
      _tree[v] = func(_tree[v << 1], _tree[(v << 1) | 1]) + _plus[v];
    }
  }
  unsigned __left_pos(unsigned v, unsigned tl, unsigned tr,
                      const unsigned& s_val) {
    if (tl == tr)
      return tl;
    else {
      unsigned tm = (tl + tr) >> 1;
      if (_tree[v << 1] >= s_val)
        return __left_pos(v << 1, tl, tm, s_val);
      else
        return __left_pos((v << 1) | 1, tm + 1, tr, s_val - _tree[v << 1]);
    }
  }
  unsigned __right_pos(unsigned v, unsigned tl, unsigned tr,
                       const unsigned& s_val) {
    if (tl == tr)
      return tr;
    else {
      unsigned tm = (tl + tr) >> 1;
      if (_tree[(v << 1) | 1] >= s_val)
        return __right_pos((v << 1) | 1, tm + 1, tr, s_val);
      else
        return __right_pos(v << 1, tl, tm, s_val - _tree[(v << 1) | 1]);
    }
  }
  void __add(unsigned v, unsigned l, unsigned r, unsigned tl, unsigned tr,
             const Type& delta) {
    if (tl == l && tr == r) {
      _plus[v] += delta;
      _tree[v] += delta;
    } else {
      int tm = (tl + tr) >> 1;
      if (r <= tm)
        __add(v << 1, l, r, tl, tm, delta);
      else if (l > tm)
        __add((v << 1) | 1, l, r, tm + 1, tr, delta);
      else {
        __add(v << 1, l, tm, tl, tm, delta);
        __add((v << 1) | 1, tm + 1, r, tm + 1, tr, delta);
      }
      _tree[v] = func(_tree[v << 1], _tree[(v << 1) | 1]) + _plus[v];
    }
  }

 public:
  SegmentTree(const std::vector<Type>& vec,
              Type (*func)(const Type&, const Type&) = nullptr)
      : func(func), _size(vec.size()) {
    _tree.resize(_size << 2);
    _plus.resize(_size << 2);
    if (_size) {
      assert(func);
      __build(vec, 1, 0, _size - 1);
    }
  }
  SegmentTree(unsigned size, const Type& value,
              Type (*func)(const Type&, const Type&) = nullptr)
      : func(func), _size(size) {
    _size++;
    _tree.resize(_size << 2);
    _plus.resize(_size << 2);
    if (_size) {
      assert(func);
      if (func(value, value) == value)
        std::fill(_tree.begin(), _tree.end(), value);
      else
        __build_equal(1, 0, _size - 1, value);
    }
  }
  void update(unsigned pos, const Type& newValue) {
    __update(1, 0, _size - 1, pos, newValue);
  }
  void change(unsigned pos, const Type& delta) {
    __change(1, 0, _size - 1, pos, delta);
  }
  void reBuild(const std::vector<Type>& vec) {
    _size = vec.size();
    _tree.resize(_size << 2);
    _plus.resize(_size << 2, NULL);
    if (_size) {
      assert(func);
      __build(vec, 1, 0, _size - 1);
    }
  }
  void reBuild(unsigned size, const Type& value) {
    _size = size;
    _tree.resize(_size << 2);
    _plus.resize(_size << 2, NULL);
    if (_size) {
      assert(func);
      if (func(value, value) == value)
        std::fill(_tree.begin(), _tree.end(), value);
      else
        __build_equal(1, 0, _size - 1, value);
    }
  }
  Type operator()(int l, int r) {
    assert(l >= 0 && r >= 0);
    assert((unsigned)l < _size && (unsigned)r < _size);
    assert(l <= r);
    return __get(1, l, r, 0, _size - 1).first;
  }
  unsigned leftPos(const Type& value) {
    return __left_pos(1, 0, _size - 1, value);
  }
  unsigned rightPos(const Type& value) {
    return __right_pos(1, 0, _size - 1, value);
  }
  void add(unsigned l, unsigned r, const Type& delta) {
    assert(l >= 0 && r >= 0);
    assert((unsigned)l < _size && (unsigned)r < _size);
    assert(l <= r);
    if (delta == NULL) return;
    __add(1, l, r, 0, _size - 1, delta);
  }
  static inline Type sum(const Type& fir, const Type& sec) { return fir + sec; }
  static inline Type diff(const Type& fir, const Type& sec) {
    return fir - sec;
  }
  static inline Type mult(const Type& fir, const Type& sec) {
    return fir * sec;
  }
  static inline Type div(const Type& fir, const Type& sec) { return fir / sec; }
  static inline Type mod(const Type& fir, const Type& sec) { return fir % sec; }
  static inline Type min(const Type& fir, const Type& sec) {
    return (fir < sec ? fir : sec);
  }
  static inline Type max(const Type& fir, const Type& sec) {
    return (fir > sec ? fir : sec);
  }
  static inline Type gcd(const Type& fir, const Type& sec) {
    return __gcd(fir, sec);
  }
  static inline Type lcm(const Type& fir, const Type& sec) {
    return fir * sec / gcd(fir, sec);
  }
  static inline Type bit_or(const Type& fir, const Type& sec) {
    return fir | sec;
  }
  static inline Type bit_and(const Type& fir, const Type& sec) {
    return fir & sec;
  }
  static inline Type bit_xor(const Type& fir, const Type& sec) {
    return fir ^ sec;
  }
  static inline Type bit_left_shift(const Type& fir, const Type& sec) {
    return fir << sec;
  }
  static inline Type bit_right_shift(const Type& fir, const Type& sec) {
    return fir >> sec;
  }
  static inline Type logical_or(const Type& fir, const Type& sec) {
    return fir || sec;
  }
  static inline Type logical_and(const Type& fir, const Type& sec) {
    return fir && sec;
  }
};
using namespace std;
template <typename Type>
inline Type sqr(const Type& x) {
  return x * x;
}
template <typename Type>
inline Type cub(const Type& x) {
  return x * x * x;
}
template <typename Type>
inline Type _pow(Type x, int power) {
  if (power == 1) return x;
  if (power == 0) return NULL;
  return sqr(_pow(x, power >> 1)) * ((power & 1) ? x : 1);
}
int main() {
  cin.tie();
  cout.tie();
  cerr.tie();
  ios_base::sync_with_stdio(false);
  unsigned N, M, k, Q;
  cin >> N >> M >> k >> Q;
  vector<SegmentTree<unsigned> > vecTree(
      N, SegmentTree<unsigned>(M, 2e9, SegmentTree<unsigned>::max));
  for (unsigned i = 0; i < Q; i++) {
    unsigned x, y, t;
    cin >> x >> y >> t;
    x--;
    y--;
    vecTree[x].update(y, t);
  }
  unsigned ans = 2e9;
  for (unsigned i = 0; i < N - k + 1; i++) {
    for (unsigned j = 0; j < M - k + 1; j++) {
      unsigned mi = 0;
      for (unsigned h = 0; h < k; h++) {
        mi = max(mi, vecTree[i + h](j, j + k - 1));
        if (mi == 2e9) break;
      }
      ans = min(ans, mi);
    }
  }
  cout << (ans == 2e9 ? -1 : (int)ans);
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

Recently Luba bought a monitor. Monitor is a rectangular matrix of size n × m. But then she started to notice that some pixels cease to work properly. Luba thinks that the monitor will become broken the first moment when it contains a square k × k consisting entirely of broken pixels. She knows that q pixels are already broken, and for each of them she knows the moment when it stopped working. Help Luba to determine when the monitor became broken (or tell that it's still not broken even after all q pixels stopped working).

Input

The first line contains four integer numbers n, m, k, q (1 ≤ n, m ≤ 500, 1 ≤ k ≤ min(n, m), 0 ≤ q ≤ n·m) — the length and width of the monitor, the size of a rectangle such that the monitor is broken if there is a broken rectangle with this size, and the number of broken pixels.

Each of next q lines contain three integer numbers xi, yi, ti (1 ≤ xi ≤ n, 1 ≤ yi ≤ m, 0 ≤ t ≤ 109) — coordinates of i-th broken pixel (its row and column in matrix) and the moment it stopped working. Each pixel is listed at most once.

We consider that pixel is already broken at moment ti.

Output

Print one number — the minimum moment the monitor became broken, or "-1" if it's still not broken after these q pixels stopped working.

Examples

Input

2 3 2 5
2 1 8
2 2 8
1 2 1
1 3 4
2 3 2


Output

8


Input

3 3 2 5
1 2 2
2 2 1
2 3 5
3 2 10
2 1 100


Output

-1

### Response

```cpp
#include <bits/stdc++.h>
template <typename Type>
class SegmentTree {
 public:
  Type (*func)(const Type&, const Type&);

 private:
  unsigned _size;
  std::vector<Type> _tree;
  std::vector<Type> _plus;
  void __build(const std::vector<Type>& vec, unsigned v, unsigned l,
               unsigned r) {
    if (l == r)
      _tree[v] = vec[l];
    else {
      unsigned m = (l + r) >> 1;
      __build(vec, v << 1, l, m);
      __build(vec, (v << 1) | 1, m + 1, r);
      _tree[v] = func(_tree[v << 1], _tree[(v << 1) | 1]);
    }
  }
  void __build_equal(unsigned v, unsigned tl, unsigned tr, const Type& value) {
    if (tl == tr)
      _tree[v] = value;
    else {
      unsigned tm = (tl + tr) >> 1;
      __build_equal(v << 1, tl, tm, value);
      __build_equal((v << 1) | 1, tm + 1, tr, value);
      _tree[v] = func(_tree[v << 1], _tree[(v << 1) | 1]);
    }
  }
  std::pair<Type, bool> __get(unsigned v, unsigned l, unsigned r, unsigned tl,
                              unsigned tr) {
    if (r < l) return std::pair<Type, bool>(NULL, false);
    if (l == tl && r == tr) return std::pair<Type, bool>(_tree[v], true);
    unsigned tm = (tl + tr) >> 1;
    std::pair<Type, bool> _f1 = __get(v << 1, l, min(r, tm), tl, tm);
    std::pair<Type, bool> _f2 =
        __get((v << 1) + 1, max(l, tm + 1), r, tm + 1, tr);
    if (_f1.second && _f2.second)
      return std::pair<Type, bool>(func(_f1.first, _f2.first) + _plus[v], true);
    if (_f1.second) {
      _f1.first += _plus[v];
      return _f1;
    }
    _f2.first += _plus[v];
    return _f2;
  }
  void __update(unsigned v, unsigned tl, unsigned tr, unsigned pos,
                const Type& newValue) {
    if (tl == tr)
      _tree[v] = newValue;
    else {
      unsigned tm = (tl + tr) >> 1;
      if (pos <= tm)
        __update(v << 1, tl, tm, pos, newValue);
      else
        __update((v << 1) | 1, tm + 1, tr, pos, newValue);
      _tree[v] = func(_tree[v << 1], _tree[(v << 1) | 1]) + _plus[v];
    }
  }
  void __change(unsigned v, unsigned tl, unsigned tr, unsigned pos,
                const Type& delta) {
    if (tl == tr)
      _tree[v] += delta;
    else {
      unsigned tm = (tl + tr) >> 1;
      if (pos <= tm)
        __change(v << 1, tl, tm, pos, delta);
      else
        __change((v << 1) | 1, tm + 1, tr, pos, delta);
      _tree[v] = func(_tree[v << 1], _tree[(v << 1) | 1]) + _plus[v];
    }
  }
  unsigned __left_pos(unsigned v, unsigned tl, unsigned tr,
                      const unsigned& s_val) {
    if (tl == tr)
      return tl;
    else {
      unsigned tm = (tl + tr) >> 1;
      if (_tree[v << 1] >= s_val)
        return __left_pos(v << 1, tl, tm, s_val);
      else
        return __left_pos((v << 1) | 1, tm + 1, tr, s_val - _tree[v << 1]);
    }
  }
  unsigned __right_pos(unsigned v, unsigned tl, unsigned tr,
                       const unsigned& s_val) {
    if (tl == tr)
      return tr;
    else {
      unsigned tm = (tl + tr) >> 1;
      if (_tree[(v << 1) | 1] >= s_val)
        return __right_pos((v << 1) | 1, tm + 1, tr, s_val);
      else
        return __right_pos(v << 1, tl, tm, s_val - _tree[(v << 1) | 1]);
    }
  }
  void __add(unsigned v, unsigned l, unsigned r, unsigned tl, unsigned tr,
             const Type& delta) {
    if (tl == l && tr == r) {
      _plus[v] += delta;
      _tree[v] += delta;
    } else {
      int tm = (tl + tr) >> 1;
      if (r <= tm)
        __add(v << 1, l, r, tl, tm, delta);
      else if (l > tm)
        __add((v << 1) | 1, l, r, tm + 1, tr, delta);
      else {
        __add(v << 1, l, tm, tl, tm, delta);
        __add((v << 1) | 1, tm + 1, r, tm + 1, tr, delta);
      }
      _tree[v] = func(_tree[v << 1], _tree[(v << 1) | 1]) + _plus[v];
    }
  }

 public:
  SegmentTree(const std::vector<Type>& vec,
              Type (*func)(const Type&, const Type&) = nullptr)
      : func(func), _size(vec.size()) {
    _tree.resize(_size << 2);
    _plus.resize(_size << 2);
    if (_size) {
      assert(func);
      __build(vec, 1, 0, _size - 1);
    }
  }
  SegmentTree(unsigned size, const Type& value,
              Type (*func)(const Type&, const Type&) = nullptr)
      : func(func), _size(size) {
    _size++;
    _tree.resize(_size << 2);
    _plus.resize(_size << 2);
    if (_size) {
      assert(func);
      if (func(value, value) == value)
        std::fill(_tree.begin(), _tree.end(), value);
      else
        __build_equal(1, 0, _size - 1, value);
    }
  }
  void update(unsigned pos, const Type& newValue) {
    __update(1, 0, _size - 1, pos, newValue);
  }
  void change(unsigned pos, const Type& delta) {
    __change(1, 0, _size - 1, pos, delta);
  }
  void reBuild(const std::vector<Type>& vec) {
    _size = vec.size();
    _tree.resize(_size << 2);
    _plus.resize(_size << 2, NULL);
    if (_size) {
      assert(func);
      __build(vec, 1, 0, _size - 1);
    }
  }
  void reBuild(unsigned size, const Type& value) {
    _size = size;
    _tree.resize(_size << 2);
    _plus.resize(_size << 2, NULL);
    if (_size) {
      assert(func);
      if (func(value, value) == value)
        std::fill(_tree.begin(), _tree.end(), value);
      else
        __build_equal(1, 0, _size - 1, value);
    }
  }
  Type operator()(int l, int r) {
    assert(l >= 0 && r >= 0);
    assert((unsigned)l < _size && (unsigned)r < _size);
    assert(l <= r);
    return __get(1, l, r, 0, _size - 1).first;
  }
  unsigned leftPos(const Type& value) {
    return __left_pos(1, 0, _size - 1, value);
  }
  unsigned rightPos(const Type& value) {
    return __right_pos(1, 0, _size - 1, value);
  }
  void add(unsigned l, unsigned r, const Type& delta) {
    assert(l >= 0 && r >= 0);
    assert((unsigned)l < _size && (unsigned)r < _size);
    assert(l <= r);
    if (delta == NULL) return;
    __add(1, l, r, 0, _size - 1, delta);
  }
  static inline Type sum(const Type& fir, const Type& sec) { return fir + sec; }
  static inline Type diff(const Type& fir, const Type& sec) {
    return fir - sec;
  }
  static inline Type mult(const Type& fir, const Type& sec) {
    return fir * sec;
  }
  static inline Type div(const Type& fir, const Type& sec) { return fir / sec; }
  static inline Type mod(const Type& fir, const Type& sec) { return fir % sec; }
  static inline Type min(const Type& fir, const Type& sec) {
    return (fir < sec ? fir : sec);
  }
  static inline Type max(const Type& fir, const Type& sec) {
    return (fir > sec ? fir : sec);
  }
  static inline Type gcd(const Type& fir, const Type& sec) {
    return __gcd(fir, sec);
  }
  static inline Type lcm(const Type& fir, const Type& sec) {
    return fir * sec / gcd(fir, sec);
  }
  static inline Type bit_or(const Type& fir, const Type& sec) {
    return fir | sec;
  }
  static inline Type bit_and(const Type& fir, const Type& sec) {
    return fir & sec;
  }
  static inline Type bit_xor(const Type& fir, const Type& sec) {
    return fir ^ sec;
  }
  static inline Type bit_left_shift(const Type& fir, const Type& sec) {
    return fir << sec;
  }
  static inline Type bit_right_shift(const Type& fir, const Type& sec) {
    return fir >> sec;
  }
  static inline Type logical_or(const Type& fir, const Type& sec) {
    return fir || sec;
  }
  static inline Type logical_and(const Type& fir, const Type& sec) {
    return fir && sec;
  }
};
using namespace std;
template <typename Type>
inline Type sqr(const Type& x) {
  return x * x;
}
template <typename Type>
inline Type cub(const Type& x) {
  return x * x * x;
}
template <typename Type>
inline Type _pow(Type x, int power) {
  if (power == 1) return x;
  if (power == 0) return NULL;
  return sqr(_pow(x, power >> 1)) * ((power & 1) ? x : 1);
}
int main() {
  cin.tie();
  cout.tie();
  cerr.tie();
  ios_base::sync_with_stdio(false);
  unsigned N, M, k, Q;
  cin >> N >> M >> k >> Q;
  vector<SegmentTree<unsigned> > vecTree(
      N, SegmentTree<unsigned>(M, 2e9, SegmentTree<unsigned>::max));
  for (unsigned i = 0; i < Q; i++) {
    unsigned x, y, t;
    cin >> x >> y >> t;
    x--;
    y--;
    vecTree[x].update(y, t);
  }
  unsigned ans = 2e9;
  for (unsigned i = 0; i < N - k + 1; i++) {
    for (unsigned j = 0; j < M - k + 1; j++) {
      unsigned mi = 0;
      for (unsigned h = 0; h < k; h++) {
        mi = max(mi, vecTree[i + h](j, j + k - 1));
        if (mi == 2e9) break;
      }
      ans = min(ans, mi);
    }
  }
  cout << (ans == 2e9 ? -1 : (int)ans);
  return 0;
}

```