题目描述

题目译自 XXVII Olimpiada Informatyczna – Eliminacje do IOI Miasta partnerskie

在拜托西亚和比特西亚两国之间多年的外交冷淡关系之后，两国决定通过加强两国城市之间的联系来改善关系。

拜托西亚有 $n$ 个城市，比特西亚也有 $n$ 个城市。两国政府希望为它们建立友好城市关系，即为拜托西亚的每个城市指定一个且仅一个来自比特西亚的友好城市，反之亦然：为比特西亚的每个城市指定一个且仅一个来自拜托西亚的友好城市。

友好城市之间将频繁交换信息，因此这些城市的邮政编码是否合适至关重要。拜托西亚的每个城市都有一个唯一的邮政编码，为整数。比特西亚的情况类似，但可能出现拜托西亚的某个城市与比特西亚的某个城市具有相同邮政编码的情况。民意调查专家预测，如果拜托西亚邮政编码为 $a_{i}$ 的城市与比特西亚邮政编码为 $b_{j}$ 的城市建立合作关系，则该举措将增加这两个城市居民的幸福感，增加值为 $a_{i} \oplus b_{j}$。这里 $\oplus$ 表示异或操作（XOR）：$x \oplus y$ 的第 $i$ 位为 $1$，当且仅当 $x$ 和 $y$ 的第 $i$ 位中恰好有一个为 $1$。

两国政府现在正在考虑如何将城市配对。这并不容易，因为对于每对选定的城市，至少有一个城市必须感到满意，即对于该城市来说，没有其他选择能比当前配对带来更大的幸福感增加。

请编写一个程序，检查是否存在满足居民要求的友好城市配对方案，如果存在，则找到任意一个这样的配对方案。

输入格式

输入数据的第一行包含一个整数 $n$ $(1 \leq n \leq 50000)$，表示每个国家的城市数量。

第二行包含 $n$ 个不同的整数 $a_{1}, a_{2}, \ldots, a_{n}$ $(0 \leq a_{i} \leq 10^{18})$，表示拜托西亚各个城市的邮政编码。

第三行包含 $n$ 个不同的整数 $b_{1}, b_{2}, \ldots, b_{n}$ $(0 \leq b_{i} \leq 10^{18})$，表示比特西亚各个城市的邮政编码。

输出格式

如果无法分配友好城市，使得每对城市中至少有一个城市感到满意，则输出 NIE。

否则，第一行输出 TAK。随后在下一行输出 $n$ 个整数：第 $i$ 个数字为 $m_{i}$，表示拜托西亚编号为 $i$ 的城市与比特西亚编号为 $m_{i}$ 的城市建立友好关系。

如果存在多个正确答案，你的程序可以输出其中任意一个。

3
2 5 4
3 5 1

TAK
2 1 3

3
2 5 1
3 5 1

NIE

2
1 1123438534808147
0 2462061299839

TAK
2 1

附加样例

1. $n=2$，$a_{i}=b_{i}=i$ $(i=1,2,\ldots,n)$，答案为 TAK；
2. $n=50000$，$a_{i}=b_{i}=i$ $(i=1,2,\ldots,n)$，答案为 NIE。

数据范围与提示

详细子任务附加限制及分值如下表所示。

如果你的程序仅第一行输出正确，仍可获得该测试 $50\%$ 的分数。请注意，你的程序仍需符合内存和时间限制。