Вася — художник-абстракционист. Он хочет нарисовать новую картину. Планируется, что картина будет иметь форму квадрата, разбитого на несколько квадратиков поменьше — итого n × n квадратиков, каждый из которых будет иметь свой собственный цвет.
Вася нарисовал эскиз, из которого видно, в какой цвет должен быть покрашен каждый квадратик. Для некоторых из них цвет задан единственным образом, остальные же могут быть покрашены в любой цвет, поскольку эти квадратики не влияют на смысл, который Вася хочет вложить в эту картину.
Есть одна сложность для написания самой картины. Вася хочет выполнить работу в особой технике рисования, которую он назвал техникой непрерывного мазка. Эта техника заключается в том, что за один взмах кистью в некоторый цвет закрашивается одна строчка или один столбик из квадратиков. Каждая строчка и столбец должны быть покрашены ровно один раз — то есть, в итоге каждый квадратик будет покрыт ровно двумя слоями краски. При этом каждый квадратик будет иметь цвет верхнего слоя краски.
Помогите Васе определить последовательность совершения мазков, чтобы претворить его замысел в реальность.
В первой строке дано число n — размер картины (1 ≤ n ≤ 3000).
В следующих n строках содержится по n символов в каждой — описание эскиза Васи. i-ый символ в j-ой строке задает цвет i-го квадратика j-ой строки будущей картины. Символами от «a» до «z» задаются цвета квадратиков, которые нужно покрасить в один конкретный цвет. Символ «?» означает, что цвет данного квадратика не важен и его можно покрасить в любой цвет.
Выведите 2n строк, каждая из которых задает мазок в формате:
«h y c» — закрасить строку y в цвет c;
«v x c» — закрасить столбец x в цвет c.
Строки и столбцы нумеруются начиная с 1 слева-направо и сверху-вниз. Каждая строка и каждый столбец должны упоминаться ровно один раз.
Гарантируется, что решение всегда существует. Если возможных решений несколько — выведите любое из них. Смотрите примеры для более точного понимания.
3
ac?
ab?
?cz
h 1 p
h 3 q
v 2 c
h 2 b
v 1 a
v 3 z
