考虑一个包含 $n$ 个顶点的无向图。图的 $k$-染色仅仅是指给每个顶点分配 $k$ 种颜色中的一种。没有其他限制——即使两个顶点由一条边相连，它们也可以具有相同的颜色。

给定两种 $k$-染色方案 $s$ 和 $t$。你希望一步步地将初始染色 $s$ 转换为最终染色 $t$。在每一步中，每个顶点可以将其颜色更改为其某个邻居的颜色，或者保持其当前颜色不变。

形式化地，你需要寻找一个 $k$-染色序列 $C_0, C_1, C_2, \ldots, C_\ell$，满足 $C_0 = s$，$C_\ell = t$，并且对于每个 $x$，$C_i(x)$ 满足以下条件之一：

• $C_{i-1}(x)$；或
• $C_{i-1}(y)$，其中 $(x, y)$ 是图中的一条边

保证输入的图是连通的且无自环。请判断是否能够构造出这样一个序列，如果存在，输出其中任意一个。该序列不需要是最短的，只要使用的步数不超过 $20\,000$ 步即可。

例如，假设你需要从左侧的初始染色开始，最终达到右侧的最终染色：

一种解决方案如下：

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$。其中 $n$ 是顶点数，$m$ 是边数，$k$ 是颜色数（$1 \le n, k \le 100$，$0 \le m \le \binom{n}{2}$）。输入的第二行包含 $n$ 个整数，每个整数均在区间 $[0, k - 1]$ 内，表示初始染色方案。输入的第三行包含 $n$ 个整数，每个整数均在区间 $[0, k - 1]$ 内，表示最终染色方案。接下来的 $m$ 行每行包含两个整数 $x_i$ 和 $y_i$，表示图中的一条边（$1 \le x_i, y_i \le n$）。

输入的图是连通的。图中没有自环或重边。

输出格式

如果不存在这样的序列，输出 Impossible。否则，输出一行或多行，描述一个染色序列 $C_0, C_1, C_2, \ldots, C_\ell$（$\ell \le 20\,000$）。每行包含用单个空格分隔的 $n$ 个整数，描述染色方案。第一行表示初始染色方案，最后一行表示最终染色方案。

你最多可以使用 $20\,000$ 步，因此输出最多包含 $20\,001$ 行。

样例

输入格式 1

6 6 2
0 1 0 1 1 1
1 0 0 0 1 0
1 2
2 3
3 5
5 4
4 6
6 5

输出格式 1

0 1 0 1 1 1
1 1 0 1 0 1
1 1 0 0 1 0
1 0 0 0 1 0

样例

输入格式 2

1 0 2
0
1

输出格式 2

Impossible

在样例 1 中，在展示的每步转换中，每个顶点要么保持其之前的颜色，要么复制一个邻居之前的颜色。在样例 2 中，唯一的顶点没有邻居，无法从颜色 0 变为颜色 1。