402834: GYM100917 A Abstract Picture

Famous abstract painter Va Sya plans to start new painting. It will be composed as square with grid n × n, where each unit square is painted by some color.

Va Sya already defined the colors for some unit squares. Color of other squares does not matter for him.

For this work Va Sya is planning use the continuous technics: he paints whole row or whole column in some color. Moreover, each row and each column must be painted exactly once, so each unit square will be painted twice and its final color will be the last of two used colors.

Help Va Sya to find appropriate sequence of paints.

First line of the input contains one integer n — length of the painting side in units (1 ≤ n ≤ 3000).

Each of the next n lines contains n characters. If i-th character in j-th line equals to '?', it means that color of i-th cell in j-th row of painting does not matter. Otherwise it contains lowercase English letter from 'a' to 'z' inclusively, which represents the color of corresponding cell (it is well known that Va Sya uses only 26 colors).

Print 2n lines, i-th of those lines contains description of i-th paint in the following format:

«h y c» — row y is painted with color c;

«v x c» — column x is painted with color c.

Rows are numbered sequentially upside down, columns are numbered sequentially leftside right, so upper left corner is on intersection of row 1 and column 1. Each row and each column must be mentioned in the output exactly once.

You may assume that there exists at least one solution for the given input. If there are several correct solutions, print any of them.

3
ac?
ab?
?cz

h 1 p
h 3 q
v 2 c
h 2 b
v 1 a
v 3 z