← 返回题目列表

Codeforces · 814/B

B. 一趟通往遐想的特快列车

中文机器翻译题面 查看原题

战国还记得小时候和小拉拉一起发现的神秘“彩色流星体”。尤其是其中一个夜晚,给她留下了深刻的印象,让她有一种幻想,自己所有的幻想都会实现。

那天晚上,战国构造了一个从 1 到 n 的整数排列 p1, p2, ..., pn,每个整数代表一种颜色,希望在即将到来的流星爆发中看到这些颜色。随后发生了两次令人难以置信的爆发,每次都有n个流星体,其颜色分别为整数序列a1,a2,...,an和b1,b2,...,bn。流星体的颜色也介于 1 和 n 之间,且两个序列不相同,即至少存在一个 i (1 ≤ i ≤ n),因此 ai ≠ bi 成立。

好吧,她几乎拥有了这一切 - 每个序列 a 和 b 都与战国排列中的 n - 1 个元素完全匹配。换句话说,恰好存在一个 i (1 ≤ i ≤ n) 使得 ai ≠ pi,并且恰好存在一个 j (1 ≤ j ≤ n) 使得 bj ≠ pj。

目前,战国能够通过天文记录恢复实际的颜色序列a和b,但她的愿望早已被遗忘。你要重建战国当晚可能发生的任何可能的排列。

输入

输入的第一行包含一个正整数 n (2 ≤ n ≤ 1 000) — 战国排列的长度,即两次流星同时爆发的长度。

第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ n) — 第一次流星爆发中的颜色序列。

第三行包含 n 个空格分隔的整数 b1, b2, ..., bn (1 ≤ bi ≤ n) — 第二次流星爆发中的颜色序列。至少存在一个 i (1 ≤ i ≤ n),使得 ai ≠ bi 成立。

输出

输出 n 个空格分隔的整数 p1, p2, ..., pn,表示战国可能具有的排列。如果有多个可能的答案,则输出其中之一。

输入保证这种排列存在。

示例

输入 #1

5
1 2 3 4 3
1 2 5 4 5

输出 #1

1 2 5 4 3

输入 #2

5
4 4 2 3 1
5 4 5 3 1

输出 #2

5 4 2 3 1

输入 #3

4
1 1 3 4
1 4 3 4

输出 #3

1 2 3 4

注意

在第一个示例中,1、2、5、4、3 和 1、2、3、4、5 都是可接受的输出。

在第二个示例中,5、4、2、3、1 是满足约束的唯一排列。