CF846D.Monitor

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).

最近，Luba 购买了一台显示器。该显示器是一个大小为 $n \times m$ 的矩形矩阵。但随后她开始注意到，某些像素点逐渐无法正常工作。Luba 认为：当显示器中首次出现一个完全由坏点组成的 $k \times k$ 正方形区域时，显示器即宣告损坏。她已知共有 $q$ 个像素点已经损坏，并且对每个坏点，她都知晓其失效的具体时刻。请帮助 Luba 判断显示器在何时损坏（或者说明：即使全部 $q$ 个像素点均已失效，显示器仍未损坏）。

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 x__i, y__i, t__i (1 ≤ x__i ≤ n, 1 ≤ y__i ≤ 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 t__i.

第一行包含四个整数 $n$、$m$、$k$、$q$（$1 \le n, m \le 500$，$1 \le k \le \min(n, m)$，$0 \le q \le n \cdot m$）—— 分别表示显示器的长与宽、导致显示器损坏的破损矩形的尺寸（即若存在一个大小为 $k \times k$ 的全破损矩形，则显示器损坏），以及破损像素的数量。

接下来的 $q$ 行，每行包含三个整数 $x_i$、$y_i$、$t_i$（$1 \le x_i \le n$，$1 \le y_i \le m$，$0 \le t_i \le 10^9$）—— 表示第 $i$ 个破损像素的坐标（其在矩阵中的行号与列号）及其失效时刻。每个像素至多被列出一次。

我们认为像素在时刻 $t_i$ 已经处于破损状态。

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

输出一个数字——显示器发生故障的最早时刻；如果在这些 $q$ 个像素停止工作后显示器仍未损坏，则输出 "-1"。