# Abstract Picture

Famous abstract painter Va Sya plans to start new painting. It will be composed as square with grid$n \times 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.

# Input

First line of the input contains one integer n — length of the painting side in units ($1 \leq n \leq 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).

# Output

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

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

«v xc» — 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.

# Example

Input

3
ac?
ab?
?cz

Output

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

# Solution

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 3e3 + 10;
const int M = 3e3 + 10;

int n, cnt;
char ch[N][N];
int cnth[N][30];
int cntv[N][30];
void readin()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%s", ch[i]);
    memset(cnth, 0, sizeof(cnth));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (ch[i][j] != '?')
                cnth[i][ch[i][j] - 'a']++;
            else 
                cnth[i][26]++;

    memset(cntv, 0, sizeof(cntv));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (ch[j][i] != '?')
                cntv[i][ch[j][i] - 'a']++;
            else 
                cntv[i][26]++;
}
deque<int> q;
int tag[2 * N]; char type[2 * N], color[2 * N];
bool check(char t, int tag, char c)
{
    if (t == 'h')
    {
        if (c == '?')
            return cnth[tag][26] == n;
        for (int i = 0; i < n; ++i)
            if (ch[tag][i] != '?' && ch[tag][i] != c)
                return false;
        return true;
    }
    else
    {
        if (c == '?')
            return cntv[tag][26] == n;
        for (int i = 0; i < n; ++i)
            if (ch[i][tag] != '?' && ch[i][tag] != c)
                return false;
        return true;
    }
    return false;
}
bool h[N], v[N];
inline void push(char t, int num, char c)
{
    ++cnt;
    type[cnt] = t;
    color[cnt] = c;
    tag[cnt] = num;
    q.push_back(cnt);
}

void solve()
{
    cnt = 0;
    while (cnt < 2 * n)
    {
        for (int i = 0; i < n; ++i)
            if (!h[i] && check('h', i, '?'))
                {
                    push('h', i, 'a');
                    h[i] = true;
                }
        for (int i = 0; i < n; ++i)
            if (!v[i] && check('v', i, '?'))
                {
                    push('v', i, 'a');
                    v[i] = true;
                } 

        for (int i = 0; i < n; ++i)
        {
            if (h[i])
                continue;
            bool flag = true;
            char now = '?';
            for (int j = 0; j < 26; ++j)
                if (cnth[i][j] > 0)
                {
                    now = j + 'a';
                    break;
                }
            if (now == '?')
                continue;
            if (check('h', i, now))
            {
                push('h', i, now);
                h[i] = true;

                for (int j = 0; j < n; ++j)
                {
                    int x = ch[i][j] - 'a';
                    if (ch[i][j] == '?')
                        x = 26;
                    cntv[j][x]--; cntv[j][26]++;
                    ch[i][j] = '?';
                }
                cnth[i][26] = n;
            }
        }
        for (int i = 0; i < n; ++i)
        {
            if (v[i])
                continue;
            bool flag = true;
            char now = '?';
            for (int j = 0; j < 26; ++j)
                if (cntv[i][j] > 0)
                {
                    now = j + 'a';
                    break;
                }
            if (now == '?')
                continue;
            if (check('v', i, now))
            {
                push('v', i, now);
                v[i] = true;

                for (int j = 0; j < n; ++j)
                {
                    
                    int x = ch[j][i] - 'a';
                    if (ch[j][i] == '?')
                        x = 26;
                    cnth[j][x]--; cnth[j][26]++;
                    ch[j][i] = '?';
                }
                cntv[i][26] = n;
            }
        }
        
    }
    
    while (!q.empty())
    {
        int t = q.back(); q.pop_back();
        printf("%c %d %c\n", type[t], tag[t] + 1, color[t]);
    }
}
int main()
{
    readin();
    solve();
    return 0;
}