题目描述

题目译自 XXV Olimpiada Informatyczna — I etap Plan metra

Bajtazar 到字节城旅行，决定全程搭乘地铁。他从火车站（旁边有个地铁站）下车后，去自动售票机买票。票价表显示，从火车站到机场的乘车免费，其他线路的票价等于起点站到终点站的距离。为了方便初来乍到的乘客，售票机旁列出了从火车站和机场到其他所有站的票价清单。

Bajtazar 还了解到，地铁有 $n$ 个站，通过 $n-1$ 条长度为正的隧道连接成一个简洁网络（足以从任意站到达另一站）。有了这些信息，他想推算出站之间的连接关系，或者判断数据是否有误。

输入格式

输入的第一行是一个正整数 $n$ ($n \geq 2$)，表示字节城地铁站的数量。站编号从 $1$ 到 $n$，火车站是 $1$ 号站，机场是 $n$ 号站。

第二行包含 $n-2$ 个整数 $d_2, d_3, \ldots, d_{n-1}$（范围 $[1, 1000000]$），第 $i$ 个数表示从火车站到 $i$ 号站的票价（即路径长度）。

第三行格式相同，包含 $l_2, l_3, \ldots, l_{n-1}$，表示从机场到各站的票价。

输出格式

如果无法根据 Bajtazar 的信息构造出站间连接网络，输出一行 NIE。

否则，第一行输出 TAK，接下来 $n-1$ 行描述站间连接。每行包含三个整数 $a, b, c$，表示 $a$ 号站和 $b$ 号站通过长度为 $c$ 的隧道连接。若有多个正确答案，输出任意一个即可。

样例

输入

7
6 6 2 2 1
5 3 5 1 4

输出

TAK
1 5 2
5 7 1
5 2 4
7 3 3
1 4 2
1 6 1

下图展示了与 Bajtazar 信息一致的连接网络，并标出了隧道长度。

附加样例

• $n=1000$, $d_i = 1000-i$, $l_i = i-1$；
• $n=1000$, $d_i = l_i = i-1$；
• $n=500000$，随机生成，答案为 NIE。

数据范围与提示

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