题目描述

佩奇最近买了个显示器，这个显示器是一个 $\red{n×}$$\red{m}$的矩形。

但是不久之后她发现这个显示器上有些像素不正常工作（可能会成为坏点）。如果屏幕上有一块 $\red{k×}$$\red{k}$的区域都是坏点，那么佩奇就觉得这个显示器坏了。

她知道有$\red{q }$个像素不正常，而且知道它们变成坏点的时间。

请告诉佩奇显示器会不会坏掉，如果会请告诉她具体时间。

输入格式

第一行四个整数 $\red{n,m,k,q}$

接下来 $\red{q}$行，每行三个整数 $\red{x_i,y_i,t_i,(1<=x_i<=n,1<=y_i<=m,1<=t_i<=10^9)，}$表示 $\red{(x_i,y_i)}$

在 $\red{t_i}$时刻会变成坏点。

输出格式

如果显示器不会坏掉，输出$\red{-1，}$否则输出显示器坏掉的时间

样例

输入样例1

2 3 2 5 

2 1 8 

2 2 8 

1 2 1 

1 3 4 

2 3 2

输出样例1

8

输入样例2

3 3 2 5 

1 2 2 

2 2 1 

2 3 5 

3 2 10 

2 1 100

输出样例2

-1

提示

对于$\red{50\%}$的数据满足，

$\red{1<=n，}$$\red{m<=50}$

对于$\red{100\%}$的数据满足，

$\red{1<=n，}$$\red{m<=500,1<=k<=min(n,m),1<=q<=n×}$ $\red{m}$