题目描述

风有一只小木箱，内部被划分为了 $n$ 行 $m$ 列的小格子，第 $i$ 行第 $j$ 列的小格子用 $(i,j)$ 表示。风将日记放在小木箱中。每一个小格子可以堆叠的放下至多 $k$ 份日记。风每次只能从小格子的最顶部取出日记，放入日记时，会放在某一个小格子的最顶端。

如果风希望取出被压在下面的日记，他需要先将上面的日记取出，再逐个放回。例如，某个小格子从底部至顶部，依次有编号为 $1,2,3,4,5$ 的五份日记，风希望取出编号为 $3$ 的日记，需要先依次取出编号为 $5,4$ 的两份日记，拿走编号为 $3$ 的日记后，再按照 $4,5$ 的顺序放回。我们称移走 $3$ 号日记需要移动 $2$ 份日记。

在接下来的 $t$ 天，风每一天都会写日记，第 $i$ 天撰写的日记编号为 $a_i$，将存放在 $(x_i,y_i)$ 中。如果 $(x_i,y_i)$ 已满，风需要从 $(x_i,y_i)$ 中先取走编号最小的日记并销毁，销毁后，将新的日记存放在 $(x_i,y_i)$ 顶部。如果存在多份编号最小的日记，销毁最靠上的一份。请问，每一天，风是否需要销毁日记？若需要，需要移动几份日记？

输入格式

第一行为四个正整数 $n,m,k,t$。

接下来 $t$ 行，每行三个正整数，第 $i$ 行为 $a_i,x_i,y_i$，表示第 $i$ 天日记编号为 $a_i$，存放在 $(x_i,y_i)$。

输出格式

输出 $t$ 行，每行一或两个整数，对于第 $i$ 行：

• 若第 $i$ 天不需要销毁日记，输出一行一个整数 $-1$
• 若第 $i$ 天需要销毁日记，输出一行两个整数，由空格隔开，分别表示销毁的日记编号和需要移动的日记份数

输入输出样例

输入 #1

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

输出 #1

-1
-1
-1
2 0
3 2

说明/提示

对于 $30\%$ 的测试数据，$n=m=1$；
对于另外 $30\%$ 的测试数据，$k=1$；
对于 $100\%$ 的测试数据，$1 \le n,m \le 100$，$1 \le k \le 50$，$1 \le t \le 2 \times 10^5$，$1 \le a_i \le 10^9$，$1 \le x_i \le n$，$1 \le y_i \le m$。

2 2 3 5
947956589 2 1
134384952 1 1
909730780 2 1
968939107 1 2
911600658 2 1

-1
-1
-1
-1
-1

1 1 1 10
788815286 1 1
357308086 1 1
674946890 1 1
715202285 1 1
479153228 1 1
811322816 1 1
334172953 1 1
45316599 1 1
827455176 1 1
903336898 1 1

-1
788815286 0
357308086 0
674946890 0
715202285 0
479153228 0
811322816 0
334172953 0
45316599 0
827455176 0