网格重置

时间限制：2 秒
空间限制：256 MB

你有一个 $n$ 行 $m$ 列的网格，初始所有格子都是白色的。此外，给你一个整数 $k$，满足 $1 \le k \le \min(n, m)$。

你要处理 $q$ 个操作，操作有两种类型：

• H（水平操作）：在网格内选择一个 $1 \times k$ 的矩形，要求矩形内所有格子都是白色。然后将矩形内所有格子变为黑色。
• V（垂直操作）：在网格内选择一个 $k \times 1$ 的矩形，要求矩形内所有格子都是白色。然后将矩形内所有格子变为黑色。

每次操作后，如果存在某些行或列全部变为黑色，则这些行和列中的所有格子同时被重置为白色。具体来说，如果某行完全变黑，该行所有格子变白；如果某列完全变黑，该列所有格子变白。

请你选择每次操作的矩形位置，使得所有操作都能被成功执行；如果无法完成所有操作，则报告不可能。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试数据组数。

每组数据的第一行包含四个整数 $n, m, k, q$（$1 \le n, m \le 100$，$1 \le k \le \min(n, m)$，$1 \le q \le 1000$），分别表示行数、列数、矩形尺寸和操作次数。

第二行包含一个长度为 $q$ 的字符串 $s$，仅由字符 H 和 V 组成，表示操作序列。

保证所有测试数据的 $q$ 之和不超过 $1000$。

输出格式

对于每组数据，如果无法执行所有操作，输出一行 -1。

否则，输出 $q$ 行，每行包含两个整数 $i, j$（$1 \le i \le n$，$1 \le j \le m$）—— 第 $i$ 个操作所选矩形的左上角坐标。

如果存在多种方案，输出任意一种即可。

样例输入

1
4 5 3 6
HVVHHV

样例输出

1 1
2 1
1 1
2 3
3 3
2 2

样例解释

1. H 操作：选择 $(1,1)$ 放置 $1\times 3$，$(1,1),(1,2),(1,3)$ 变黑。
2. V 操作：选择 $(2,1)$ 放置 $3\times 1$，$(2,1),(3,1),(4,1)$ 变黑。此时第 $1$ 列全黑，重置该列所有格子为白。
3. V 操作：选择 $(1,1)$ 放置 $3\times 1$，$(1,1),(2,1),(3,1)$ 变黑。
4. H 操作：选择 $(2,3)$ 放置 $1\times 3$，$(2,3),(2,4),(2,5)$ 变黑。
5. H 操作：选择 $(3,3)$ 放置 $1\times 3$，$(3,3),(3,4),(3,5)$ 变黑。
6. V 操作：选择 $(2,2)$ 放置 $3\times 1$，$(2,2),(3,2),(4,2)$ 变黑。此时第 $2$ 行、第 $3$ 行和第 $2$ 列全黑，重置这些行和列的所有格子为白。