Lady 收到了一份生日礼物——一个网络。该网络包含 $n$ 个节点，编号从 $1$ 到 $n$。每个节点上都写有一个字母，对于编号为 $i$ 的节点，我们将该字母记为 $s_i$。
节点之间存在一些单向连接。每个节点恰好有一条指向某个节点的单向连接。设编号为 $i$ 的节点的连接指向编号为 $x_i$ 的节点。注意，$x_i$ 可以等于 $i$——在这种情况下，认为从编号为 $i$ 的节点出发的连接指向其自身。
设 $p_{i,0} = i$ 且 $p_{i,k} = p_{x_i, k-1}$。也就是说，$p_{i,k}$ 是将一枚棋子放置在编号为 $i$ 的节点上，并沿着连接移动 $k$ 次后，棋子所在的节点编号。
Lady 创建了一个大小为 $n \times (3 \cdot n)$ 的矩阵 $a$，其中 $a_{i,j} = s_{p_{i, j-1}}$。即矩阵 $a$ 的第 $i$ 行是一个长度为 $3 \cdot n$ 的字母序列，其中第一个字母为 $s_i$，第二个字母为 $s_{x_i}$，第三个字母为 $s_{x_{x_i}}$，以此类推。
Lady 公布了矩阵 $a$ 的部分行，并请求你构建一个符合已知行的网络。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^3$)，表示网络中的节点数量。
接下来的 $n$ 行描述了矩阵 $a$。每一行包含 $3 \cdot n$ 个小写拉丁字母，表示矩阵 $a$ 的对应行；如果 Lady 没有公布该行，则该行为一个字符“?”。
保证至少存在一个符合给定条件的网络。
输出格式
第一行输出一个包含 $n$ 个小写拉丁字母的字符串 $s$，表示写在网络节点上的字母。
第二行输出 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($1 \le x_i \le n$)，表示从对应节点出发的连接所指向的节点编号。
该网络对应的矩阵必须在 Lady 公布的所有行上与矩阵 $a$ 完全一致。
如果存在多个正确的答案，输出其中任意一个即可。
子任务
设 $q$ 为 Lady 未公布的行数。
我们将网络称为“对与单点集”，如果网络可以拆分为自环节点（即 $x_v = v$）和节点对 $(a, b)$（满足 $x_a = b$ 且 $x_b = a$）。
我们将网络称为“星形集”，如果网络可以拆分为若干个“星”，每个星由一个自环主节点 $v$（即 $x_v = v$）和一组从属节点 $y = \{y_1, y_2, \dots, y_k\}$ 组成，满足 $x_{y_i} = v$（对于 $1 \le i \le k$）。注意，网络中的星可以有不同的大小，也可以仅由一个主节点组成。
我们将网络称为“以 $v$ 为根的树”，如果 $v$ 是一个自环节点（即 $x_v = v$），且对于每个其他节点，都可以通过网络连接到达节点 $v$（即对于每个 $1 \le i \le n$，存在某个 $k$ 使得 $p_{i,k} = v$）。
我们将网络称为“环”，如果从任何节点出发都可以到达任何其他节点（即对于所有 $1 \le i, j \le n$，存在某个 $k$ 使得 $p_{i,k} = j$）。
- (10 分): $n \le 5, q = 0$;
- (6 分): $n \le 300, q = 0, x_{x_i} = i$ (网络为对与单点集);
- (6 分): $n \le 300, q = 0, x_{x_i} = x_i$ (网络为星形集);
- (9 分): $n \le 300, q = 0, x_1 = 1$ 且 $x_i < i$ (对于 $2 \le i \le n$，网络为以 $1$ 为根的树);
- (9 分): $n \le 300, q = 0$, 对于所有 $1 \le i, j \le n$ 存在某个 $k$ 使得 $p_{i,k} = j$ (网络为环);
- (13 分): $n \le 300, q = 0$;
- (25 分): $n \le 300$;
- (10 分): $n \le 2 \cdot 10^3, q = 0$;
- (12 分): 无附加限制。
样例
样例 1
4 abaaaaaaaaaa baaaaaaaaaaa aaaaaaaaaaaa cccccccccccc
abac 2 3 3 4
样例 2
3 axaxaxaxa xxxxxxxxx ?
axx 3 2 1
说明
在第一个样例中，$x_1 = 2$ 且 $x_2 = 3$，因此 $p_{1,0} = 1, p_{1,1} = 2, p_{1,2} = 3$。由于 $x_3 = 3$，所有 $k \ge 3$ 的 $p_{1,k}$ 也等于 $3$。相应地，第一行的第二个字母为 $s_2$，第三个字母为 $s_3$。
下方展示了样例中的网络。角落里的数字表示节点编号，字母表示写在对应节点上的值，箭头表示单向连接。
第一个样例的网络
第二个样例的网络