你在当铺经营着一家生意兴隆的店铺。你将某些商品摆放在橱窗里展示给街上的行人。有时你会多次展示同一种商品。为简便起见，我们将展示的商品视为一个数值序列，其中数值代表所展示商品的类型。

例如，你的展示序列可能是： $1\ 2\ 6\ 2\ 7\ 9\ 8\ 5$

在你最近度假回来后，发现员工通过移动商品彻底打乱了展示顺序。天哪！例如，上面的展示序列可能被重排为： $2\ 6\ 1\ 2\ 9\ 7\ 5\ 8$

你担心这会导致混乱并吓跑回头客。但你没有时间把商品移回原来的位置。

作为折中方案，你将在橱窗里放置分隔符，将展示的商品划分为若干连续的组。每一组都应该是你首选排列中对应位置商品类型的一种重排。

更准确地说，令 $a_1, \dots, a_N$ 表示第一个序列，$b_1, \dots, b_N$ 表示第二个序列。如果 $b_i, b_{i+1}, \dots, b_j$ 是 $a_i, a_{i+1}, \dots, a_j$ 的一种重排，你就可以在 $i, i+1, \dots, j$ 周围放置分隔符。你不需要在序列的开头或结尾放置分隔符。注意，如果 $a_i = b_i$，则可以仅使用这单个索引 $i$ 形成一个组。

对于上述序列，你可以在三个位置放置分隔符 $\#$，如下所示： $2\ 6\ 1\ \#\ 2\ \#\ 7\ 9\ \#\ 5\ 8$

将该序列划分为超过四个满足此属性的组是不可能的。

给定这两个序列，确定如何将新序列划分为尽可能多的组。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 300\,000$)，表示两个序列的长度。 下一行包含 $N$ 个整数 $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$)，表示原始序列。 下一行包含 $N$ 个整数 $b_1, \dots, b_N$ ($1 \le b_i \le 10^9$)，表示重排后的序列。值 $b_1, \dots, b_N$ 是 $a_1, \dots, a_N$ 的一种重排。

输出格式

输出带有有效且尽可能多的分隔符（#）的重排后序列。

如果有多种可能的解决方案，输出其中任意一种即可。

样例

样例输入 1

8
1 2 6 2 7 9 8 5
2 6 1 2 9 7 5 8

样例输出 1

2 6 1 # 2 # 9 7 # 5 8

样例输入 2

4
1 1 2 1
2 1 1 1

样例输出 2

2 1 1 # 1

样例输入 3

3
1 2 5
2 5 1

样例输出 3

2 5 1