| Pinely Round 4 (Div. 1 + Div. 2) |
|---|
| Закончено |
Вам дана сетка, состоящая из $$$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$$$) — количество строк и столбцов в сетке, сторона прямоугольника операции и количество операций, соответственно.
Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$q$$$, состоящую только из символов $$$\mathtt{H}$$$ и $$$\mathtt{V}$$$ — последовательность типов операций.
Гарантируется, что сумма $$$q$$$ по всем наборам входных данных не превосходит $$$1000$$$.
Для каждого набора входных данных выведите одно число $$$-1$$$, если невозможно выполнить все операции.
В противном случае выведите $$$q$$$ строк. Каждая строка должна содержать по два целых числа $$$i$$$, $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$) — координаты левой верхней клетки прямоугольника операций.
Если существует несколько решений, выведите любое из них.
14 5 3 6HVVHHV
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)$$$ становятся черными. В этот момент две строки и один столбец становятся полностью черными, поэтому все ячейки в этих строках и столбце сбрасываются в белые.
