G. Беззубик
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Запрещенная дружба — Джон Пауэлл, Как приручить дракона

Пусть $$$n, m, a, b$$$ — положительные целые числа, при этом $$$a \leq b$$$. Беззубик рисует на сетке песка размером $$$n \times m$$$, которая изначально вся белая. За один ход он может сделать следующее:

  • Выбрать любую текущую белую клетку и закрасить её в черный, если у неё не более одной черной клетки среди соседей по сторонам.

Поскольку он очень привередлив в своем искусстве, Беззубик считает некоторые клетки в сетке нужными, и эти клетки должны в конечном итоге стать черными. Из клеток, которые не являются нужными, он также считает некоторые из них особенными. Клетка имеет значение $$$b$$$, если она особенная, и $$$a$$$ в противном случае. Ни одна особенная клетка не граничит с нужной клеткой по стороне.

Пусть $$$P$$$ — сумма значений всех клеток в сетке, которые не являются нужными. Поскольку Беззубик очень привередлив в своем искусстве, он хочет сделать некоторое количество ходов так, чтобы:

  • Каждая из нужных клеток стала черной после завершения всех ходов,
  • Общая стоимость клеток, которые закрашены в черный (включая нужные клетки), составила не менее $$$\frac{2}{3} \cdot P$$$.

Вычислите любую последовательность ходов, которые мог бы сделать Беззубик. Гарантируется, что входные данные сгенерированы таким образом,что все нужные клетки во входных данных могут быть закрашены в черный цвет после некоторого количества ходов. Более того, можно показать, что для заданных ограничений всегда существует подходящая последовательность ходов.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит четыре целых числа $$$n$$$, $$$m$$$, $$$a$$$ и $$$b$$$ ($$$1 \leq n, m \leq 2 \cdot 10^3, 1 \leq n \cdot m \leq 2 \cdot 10^3, 1 \leq a \leq b \leq 5 \cdot 10^5$$$) — размеры сетки и значения неособенных и особенных клеток соответственно.

$$$i$$$-я из следующих $$$n$$$ строк содержит строку $$$s_i$$$ — строку из ровно $$$m$$$ символов, изображающую $$$i$$$-ю строку.

  • $$$j$$$-й символ равен '#', если клетка в $$$(i, j)$$$ нужная.
  • $$$j$$$-й символ равен 'x', если клетка в $$$(i, j)$$$ особенная.
  • В противном случае $$$j$$$-й символ равен '.'.
Гарантируется, что ни одна нужная клетка не соседствует с особенной клеткой.

Гарантируется, что входные данные сгенерированы таким образом,что все нужные клетки во входных данных могут быть закрашены в черный цвет после некоторого количества ходов.

Гарантируется, что сумма значений $$$(nm)^2$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^6$$$.

Выходные данные

Для каждого набора выведите следующее.

В первой строке выведите количество ходов $$$op$$$ ($$$0 \leq op \leq n \cdot m$$$), которые вы хотите сделать.

Для каждого из $$$op$$$ ходов выведите строку, содержащую два целых числа $$$i, j$$$ ($$$1 \leq i \leq n, 1 \leq j \leq m$$$), указывая, что вы хотите закрасить клетку $$$(i, j)$$$ в черный цвет.

Пример
Входные данные
3
3 3 1 5
#..
...
..x
2 3 1 2
...
xxx
3 5 8 9
x.x.x
.x.x.
x.#.x
Выходные данные
6
1 1
3 1
3 2
3 3
2 3
1 3
3
2 1
2 2
2 3
10
1 1
1 2
1 3
2 2
2 5
1 5
3 5
2 4
3 3
3 1
Примечание

В первом наборе есть нужная клетка в верхнем левом углу и особенная клетка в нижнем правом углу. Используя операции в примере вывода, мы получим следующую сетку:

Из клеток, которые не являются нужными, есть $$$7$$$ неособенных клеток стоимостью $$$1$$$ каждая и $$$1$$$ особенная клетка стоимостью $$$5$$$, так что $$$P = 12$$$. Таким образом, нам нужно закрасить клетки с общей стоимостью не менее $$$\frac{2}{3} \cdot 12 = 8$$$; данная последовательность ходов достигает стоимости $$$10$$$.

Во втором наборе нет нужных клеток, но есть три особенные клетки в нижнем ряду клеток. Используя операции в примере вывода, мы получим следующую сетку:

Есть $$$3$$$ неособенные клетки стоимостью $$$1$$$ каждая и $$$3$$$ особенные клетки стоимостью $$$2$$$, так что $$$P = 9$$$. Таким образом, нам нужно закрасить клетки с общей стоимостью не менее $$$\frac{2}{3} \cdot 9 = 6$$$; данная последовательность ходов достигает стоимости $$$6$$$.

В третьем наборе есть одна нужная клетка в $$$(3, 3)$$$ и $$$7$$$ особенных клеток. Используя операции в примере вывода, мы получим следующую сетку:

Из клеток, которые не нуждаются, есть $$$7$$$ неособенных клеток стоимостью $$$8$$$ каждая и $$$7$$$ особенных клеток стоимостью $$$9$$$, так что $$$P = 7 \cdot 8 + 7 \cdot 9 = 119$$$. Таким образом, нам нужно закрасить клетки с общей стоимостью не менее $$$\frac{2}{3} \cdot 119 = 79 \frac{1}{3}$$$; данная последовательность ходов достигает стоимости $$$87$$$.