Grid Reset
Contest: Pinely Round 4 (Div. 1 + Div. 2)
Difficulty rating: 2700
Tags: constructive algorithms, greedy, implementation

You are given a grid consisting of $$$n$$$ rows and $$$m$$$ columns, where each cell is initially white. Additionally, you are given an integer $$$k$$$, where $$$1 \le k \le \min(n, m)$$$.

You will process $$$q$$$ operations of two types:

- $$$\mathtt{H}$$$ (horizontal operation) — You choose a $$$1 \times k$$$ rectangle completely within the grid, where all cells in this rectangle are white. Then, all cells in this rectangle are changed to black.
- $$$\mathtt{V}$$$ (vertical operation) — You choose a $$$k \times 1$$$ rectangle completely within the grid, where all cells in this rectangle are white. Then, all cells in this rectangle are changed to black.

After each operation, if any rows or columns become completely black, all cells in these rows and columns are simultaneously reset to white. Specifically, if all cells in the row and column a cell is contained in become black, all cells in both the row and column will be reset to white.

Choose the rectangles in a way that you can perform all given operations, or determine that it is impossible.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains four integers $$$n$$$, $$$m$$$, $$$k$$$, and $$$q$$$ ($$$1 \le n, m \le 100$$$, $$$1 \le k \le \min(n, m)$$$, $$$1 \le q \le 1000$$$) — the number of rows and columns in the grid, the size of the operation rectangle, and the number of operations, respectively.

The second line of each test case contains a string $$$s$$$ of length $$$q$$$, consisting only of characters $$$\mathtt{H}$$$ and $$$\mathtt{V}$$$ — the sequence of operation types.

It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$1000$$$.

Output format:
For each test case, output a single integer $$$-1$$$ if it is impossible to perform all the operations.

Otherwise, output $$$q$$$ lines. Each line contains two integers $$$i$$$, $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$) — the coordinates of the top-left cell of the operation rectangle.

If there are multiple solutions, output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Illustration of example.

The first operation is horizontal. The operation rectangle starts at $$$(1,1)$$$ and is a $$$1 \times 3$$$ rectangle. After the operation, cells $$$(1,1)$$$, $$$(1,2)$$$, and $$$(1,3)$$$ become black.

The second operation is vertical. The operation rectangle starts at $$$(2,1)$$$ and is a $$$3 \times 1$$$ rectangle. After the operation, cells $$$(2,1)$$$, $$$(3,1)$$$, and $$$(4,1)$$$ become black. At this point, the first column becomes completely black, so all cells in the first column are reset to white.

The third operation is vertical. The operation rectangle starts at $$$(1,1)$$$ and is a $$$3 \times 1$$$ rectangle. After the operation, cells $$$(1,1)$$$, $$$(2,1)$$$, and $$$(3,1)$$$ become black.

The fourth operation is horizontal. The operation rectangle starts at $$$(2,3)$$$ and is a $$$1 \times 3$$$ rectangle. After the operation, cells $$$(2,3)$$$, $$$(2,4)$$$, and $$$(2,5)$$$ become black.

The fifth operation is horizontal. The operation rectangle starts at $$$(3,3)$$$ and is a $$$1 \times 3$$$ rectangle. After the operation, cells $$$(3,3)$$$, $$$(3,4)$$$, and $$$(3,5)$$$ become black.

The sixth operation is vertical. The operation rectangle starts at $$$(2,2)$$$ and is a $$$3 \times 1$$$ rectangle. After the operation, cells $$$(2,2)$$$, $$$(3,2)$$$, and $$$(4,2)$$$ become black. At this point, two rows and one column become completely black, so all cells in these rows and the column are reset to white.

Example input:
1
4 5 3 6
HVVHHV

Example output:
1 1
2 1
1 1
2 3
3 3
2 2

Editorial:
Hint 1
Perform horizontal operations only on the leftmost $$$k$$$ columns and vertical operations only on the topmost $$$k$$$ rows.
Hint 2
Prioritize operations that will lead to a reset.
Solution
Here is a strategy to ensure you can perform operations infinitely:
1. Perform horizontal operations only on the leftmost $$$k$$$ columns and vertical operations only on the topmost $$$k$$$ rows.
2. Prioritize operations that will lead to a reset. If multiple operations can cause a reset, perform any of them; if no operations can cause a reset, perform any available operation.
The correctness of this strategy is intuitive but not straightforward to prove.
Proof of Correctness
For a $$$n \times m$$$ grid, we define it to be in a horizontal state if its black cells can be covered by non-overlapping $$$1 \times m$$$ rectangles without gaps. Similarly, the grid is in a vertical state if its black cells can be covered by non-overlapping $$$n \times 1$$$ rectangles without gaps.
Our strategy ensures the grid always satisfies the following properties:
1. The $$$k \times k$$$ region in the top-left corner, the $$$(n-k) \times k$$$ region in the bottom-left corner, and the $$$k \times (m-k)$$$ region in the top-right corner are either in a horizontal state, vertical state, or both.
2. The top-left and bottom-left regions cannot both be purely in a vertical state; similarly, the top-left and top-right regions cannot both be purely in a horizontal state.
We will prove two points: first, when these properties are satisfied, there is always a valid operation; second, after performing operations according to our strategy, the grid still satisfies these properties.
Existence of Valid Operations
Assume the current operation is horizontal (the proof for vertical operations is similar). If the top-left and bottom-left regions cannot perform a horizontal operation, they must be completely black or in a purely vertical state. If one region is completely black, the other cannot be completely black or purely vertical, because that would have led to a reset earlier. According to the second property, the top-left and bottom-left regions cannot both be in a purely vertical state. Therefore, there is always a valid operation.
Maintaining the First Property
1. For the bottom-left and top-right regions, they always satisfy the first property. Proof: Consider the bottom-left region (the proof for the top-right region is similar). It starts as completely white, turning black row by row, maintaining a horizontal state. Once it is completely black, it resets column by column, maintaining a vertical state. Thus, it alternates between horizontal and vertical states.
2. For the top-left region, it always satisfies the first property. Proof: After coloring and before resetting, the top-left region still satisfies the first property. Suppose it is in a horizontal state before resetting (the proof for a vertical state is similar). Since it cannot reset vertically, it remains at least in a horizontal state after resetting. If it becomes completely black and resets horizontally (the proof for a vertical reset is similar), it remains in a horizontal state. Unless $$$k = 1$$$, rows and columns cannot reset simultaneously. Suppose both rows and columns can reset, and assume the current operation is horizontal in the top-left region (the proof for a vertical operation is similar). This means the top-left region was in a purely horizontal state before turning completely black. The row in the top-right region was completely black, while other rows were white, contradicting the second property before the operation.
Maintaining the Second Property
1. Assume the current operation is horizontal (the proof for vertical operations is similar) and causes a reset, the second property still holds. Proof: If the operation is in the bottom-left region, it was completely black before resetting. After resetting, the top-left region turns completely white, maintaining the second property. We previously proved that unless $$$k = 1$$$, rows and columns cannot reset simultaneously. If the horizontal operation is in the top-left region and columns reset, the top-left region was completely black before resetting. After resetting, the top-left region becomes vertical, while the bottom-left region turns white, maintaining the second property. If the horizontal operation is in the top-left region and rows reset, the top-left region remains unchanged, while the row in the top-right region turns white. If the top-right region's state changes and resets to a purely horizontal state (the only possible violation of the second property), the top-right region is completely black before resetting. Thus, the top-left region was not in a purely horizontal state before resetting. Since the top-left region remains unchanged, it cannot be in a purely horizontal state, maintaining the second property.
2. Assume the current operation is horizontal (the proof for vertical operations is similar) and does not cause a reset, the second property still holds. Proof: If the operation is in the bottom-left region, it remains in a horizontal state, maintaining the second property. If the operation is in the top-left region, the only possible violation of the second property is if the top-right region remains in a purely horizontal state while the top-left region becomes purely horizontal. This means the top-left region was completely white before the operation. In this case, we can choose to reset any completely black row in the top-right region. According to the strategy, we prioritize resets, leading to a contradiction. Thus, the second property still holds.