为您提供一个由 $$$n$$$ 行和 $$$m$$$ 列组成的网格,其中每个单元格最初都是白色的。此外,还会给您一个整数 $$$k$$$,其中 $$$1 \le k \le \min(n, m)$$$。
您将处理两种类型的 $$$q$$$ 操作:
- $$$\mathtt{H}$$$(水平运算)— 您选择一个完全位于网格内的 $$$1 \times k$$$ 矩形,该矩形中的所有单元格均为白色。然后,该矩形中的所有单元格都变为黑色。
- $$$\mathtt{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$$$,仅由字符$$$\mathtt{H}$$$和$$$\mathtt{V}$$$组成——操作类型的序列。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$1000$$$。
输出
对于每个测试用例,如果不可能执行所有操作,则输出单个整数 $$$-1$$$。
否则,输出 $$$q$$$ 行。每行包含两个整数 $$$i$$$, $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$)——操作矩形左上角单元格的坐标。
如果有多个解,则输出其中任意一个。
示例
输入 #1
1 4 5 3 6 HVVHHV
输出 #1
1 1 2 1 1 1 2 3 3 3 2 2
注意
示例说明。
第一个操作是水平操作。操作矩形从 $$$(1,1)$$$ 开始,是一个 $$$1 \times 3$$$ 矩形。操作后,单元格 $$$(1,1)$$$、$$$(1,2)$$$ 和 $$$(1,3)$$$ 变为黑色。
第二个操作是垂直的。操作矩形从 $$$(2,1)$$$ 开始,是一个 $$$3 \times 1$$$ 矩形。操作后,单元格 $$$(2,1)$$$、$$$(3,1)$$$ 和 $$$(4,1)$$$ 变为黑色。此时,第一列变为全黑,因此第一列中的所有单元格都重置为白色。
第三个操作是垂直的。操作矩形从 $$$(1,1)$$$ 开始,是一个 $$$3 \times 1$$$ 矩形。操作后,单元格 $$$(1,1)$$$、$$$(2,1)$$$ 和 $$$(3,1)$$$ 变为黑色。
第四个操作是水平操作。操作矩形从 $$$(2,3)$$$ 开始,是一个 $$$1 \times 3$$$ 矩形。操作后,单元格 $$$(2,3)$$$、$$$(2,4)$$$ 和 $$$(2,5)$$$ 变为黑色。
第五个操作是水平操作。操作矩形从 $$$(3,3)$$$ 开始,是一个 $$$1 \times 3$$$ 矩形。操作后,单元格 $$$(3,3)$$$、$$$(3,4)$$$ 和 $$$(3,5)$$$ 变为黑色。
第六个操作是垂直的。操作矩形从 $$$(2,2)$$$ 开始,是一个 $$$3 \times 1$$$ 矩形。操作后,单元格 $$$(2,2)$$$、$$$(3,2)$$$ 和 $$$(4,2)$$$ 变为黑色。此时,两行一列变成全黑,因此这些行和列中的所有单元格都重置为白色。