Lady received a gift for her birthday — a network. The network contains $n$ nodes, numbered with integers from $1$ to $n$. Each node has a certain letter written on it; for a node with number $i$, we denote this letter as $s_i$.

Between some pairs of nodes, there are one-way connections. From each node, exactly one one-way connection originates. Let $x_i$ be the node number to which the connection from node $i$ leads. Note that $x_i$ can be equal to $i$ — in this case, it is considered that the connection from node $i$ leads to the same node.

Let $p_{i,0} = i$ and $p_{i,k} = p_{x_i, k-1}$. That is, $p_{i,k}$ is the node number where a token would end up if placed at node $i$ and moved $k$ times along the connections from the current node.

Lady created a matrix $a$ of size $n \times (3 \cdot n)$, where $a_{i,j} = s_{p_{i, j-1}}$. That is, the $i$-th row of matrix $a$ is a sequence of $3 \cdot n$ letters, where the first letter is $s_i$, the second letter is $s_{x_i}$, the third letter is $s_{x_{x_i}}$, and so on...

Lady has provided some rows of matrix $a$ and asks you to construct any network that corresponds to the known rows of matrix $a$.

Input

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^3$) — the number of nodes in the network.

The next $n$ lines contain the description of matrix $a$. Each line contains $3 \cdot n$ lowercase Latin letters, representing the corresponding row of matrix $a$, or a single symbol "?" if Lady did not provide the corresponding row.

It is guaranteed that there exists at least one network that satisfies the given conditions.

Output

In the first line, output a string $s$ of $n$ lowercase Latin letters — the letters written on the nodes of the network.

In the second line, output $n$ integers $x_1, x_2, \dots, x_n$ ($1 \le x_i \le n$) — the node numbers to which the connections from the corresponding nodes lead.

The matrix corresponding to this network must be equal to matrix $a$ in all rows that Lady provided.

If there are multiple correct answers, you are allowed to output any of them.

Subtasks

Let $q$ be the number of rows that Lady did not provide.

We call a network a set of pairs and single nodes if the network can be partitioned into nodes where the connection leads to themselves (i.e., $x_v = v$) and pairs of nodes $(a, b)$ such that $x_a = b$ and $x_b = a$.

We call a network a set of stars if the network can be partitioned into separate "stars", each consisting of a central node $v$ where the connection leads to itself (i.e., $x_v = v$) and a set of secondary nodes $y = \{y_1, y_2, \dots, y_k\}$ such that $x_{y_i} = v$ for $1 \le i \le k$. Note that stars in the network can have different sizes and consist of only one central node.

We call a network a tree rooted at node $v$ if the connection from node $v$ leads to itself (i.e., $x_v = v$) and for every other node, it is possible to reach node $v$ using the network connections (i.e., for every $1 \le i \le n$ there exists $k$ such that $p_{i,k} = v$).

We call a network a cycle if, starting at any node, it is possible to reach any other node using the network connections (i.e., for all $1 \le i, j \le n$ there exists $k$ such that $p_{i,k} = j$).

1. (10 points): $n \le 5, q = 0$;
2. (6 points): $n \le 300, q = 0, x_{x_i} = i$ for $1 \le i \le n$ (the network is a set of pairs and single nodes);
3. (6 points): $n \le 300, q = 0, x_{x_i} = x_i$ for $1 \le i \le n$ (the network is a set of stars);
4. (9 points): $n \le 300, q = 0, x_1 = 1$ and $x_i < i$ for $2 \le i \le n$ (the network is a tree rooted at node 1);
5. (9 points): $n \le 300, q = 0$, for all $1 \le i, j \le n$ there exists $k$ such that $p_{i,k} = j$ (the network is a cycle);
6. (13 points): $n \le 300, q = 0$;
7. (25 points): $n \le 300$;
8. (10 points): $n \le 2 \cdot 10^3, q = 0$;
9. (12 points): no additional constraints.

Examples

Input 1

4
abaaaaaaaaaa
baaaaaaaaaaa
aaaaaaaaaaaa
cccccccccccc

Output 1

abac
2 3 3 4

Input 2

3
axaxaxaxa
xxxxxxxxx
?

Output 2

axx
3 2 1

Note

In the first example, $x_1 = 2$ and $x_2 = 3$, so $p_{1,0} = 1, p_{1,1} = 2, p_{1,2} = 3$. Because $x_3 = 3$, all $p_{1,k}$ for $k \ge 3$ are also equal to 3. Accordingly, the second letter of the first row is $s_2$, and the third is $s_3$.

Below are the networks from the examples. The numbers in the corners denote node numbers, the letters denote the values written on the corresponding nodes, and the arrows denote one-way connections.

Network from the first example

Network from the second example