#include <bits/stdc++.h>
using namespace std;
const long long N = 1005, oo = 1000000005;
long long l1, r1, l2, r2, n, i, k, a[N][N], quemax[N], q1[N], m, q, ans[N][N],
    an = oo;
inline long long read() {
  long long x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(long long a) {
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(long long a) {
  write(a);
  puts("");
}
int main() {
  n = read();
  m = read();
  k = read();
  q = read();
  for (i = 1; i <= n; i++)
    for (long long j = 1; j <= m; j++) a[i][j] = oo;
  while (q--) {
    long long x = read(), y = read();
    a[x][y] = read();
  }
  for (long long j = 1; j <= n; j++) {
    r1 = 0;
    l1 = 1;
    for (i = 1; i <= k - 1; i++) {
      while (quemax[r1] <= a[j][i] && l1 <= r1) r1--;
      quemax[++r1] = a[j][i];
      q1[r1] = i;
    }
    for (i = k; i <= m; i++) {
      if (q1[l1] == i - k && l1 <= r1) l1++;
      while (quemax[r1] <= a[j][i] && l1 <= r1) r1--;
      quemax[++r1] = a[j][i];
      q1[r1] = i;
      ans[j][i] = quemax[l1];
    }
  }
  for (long long j = k; j <= m; j++) {
    r1 = 0;
    l1 = 1;
    for (i = 1; i <= k - 1; i++) {
      while (quemax[r1] <= ans[i][j] && l1 <= r1) r1--;
      quemax[++r1] = ans[i][j];
      q1[r1] = i;
    }
    for (i = k; i <= n; i++) {
      if (q1[l1] == i - k && l1 <= r1) l1++;
      while (quemax[r1] <= ans[i][j] && l1 <= r1) r1--;
      quemax[++r1] = ans[i][j];
      q1[r1] = i;
      an = min(an, quemax[l1]);
    }
  }
  if (an != oo)
    writeln(an);
  else
    puts("-1");
}
