모니터

Recently Luba은 모니터를 샀다. 모니터는 크기가 n × m인 직사각형 행렬이다. 그러나 얼마 뒤 일부 픽셀이 제대로 작동하지 않게 되는 것을 알아차렸다. Luba는 모니터에 고장 난 픽셀로만 이루어진 k × k 정사각형이 생기는 최초의 순간에 모니터가 고장 난다고 생각한다. 그녀는 이미 q개의 픽셀이 고장 났다는 것을 알고 있으며, 각 픽셀이 작동을 멈춘 순간도 알고 있다. Help Luba 모니터가 언제 고장 났는지 판단한다(또는 q개의 픽셀이 모두 작동을 멈춘 뒤에도 여전히 고장 나지 않았다고 알린다).

첫째 줄에 네 정수 n, m, k, q (1 ≤ n, m ≤ 500, 1 ≤ k ≤ min(n, m), 0 ≤ q ≤ n·m)가 주어진다. 각각 모니터의 길이와 너비, 이 크기의 고장 난 직사각형이 있으면 모니터가 고장 난 것으로 간주하는 직사각형의 크기, 고장 난 픽셀의 수를 나타낸다.

이어지는 q개의 줄에는 각각 세 정수 xi, yi, ti (1 ≤ xi ≤ n, 1 ≤ yi ≤ m, 0 ≤ t ≤ 109)가 주어진다. 이는 i-th 고장 난 픽셀의 좌표(행렬에서의 행과 열)와 그 픽셀이 작동을 멈춘 순간을 나타낸다. 각 픽셀은 최대 한 번만 나열된다.

픽셀은 ti 순간에 이미 고장 난 것으로 간주한다.

모니터가 고장 난 최소 순간을 하나의 수로 출력한다. 이 q개의 픽셀이 작동을 멈춘 뒤에도 여전히 고장 나지 않았다면 "-1"을 출력한다.