Byteasar 是米达斯国王的皇家工程师，他受命建造一座迷宫。这座迷宫本应是一座博物馆，其房间内陈列着珍贵的展品。实际上，它是一个敲诈游客的陷阱，其唯一目的就是为本已庞大的皇家国库敛财。

迷宫由房间和连接它们的走廊组成。其中一个房间是迷宫的入口，并已作了相应标记。在每个房间中，进入该房间的走廊会分叉，从而产生两条出口走廊：左侧和右侧；每一条都可能被封锁，在这种情况下无法通行。奇怪的是，尽管走廊会分叉，但它们从不汇合。每位进入迷宫的游客都会得到一个设备，该设备会记录他们经过的每条走廊的费用。费用取决于已支付的金额以及当前选择的是左侧还是右侧。具体来说，走左侧走廊的费用恰好等于目前为止已支付的总金额，而走右侧走廊的费用等于目前为止已支付的总金额加上一个杜卡特（ducat）。

显然，这种复杂的收费结构旨在掩盖真实成本。但这给游客带来了极大的不便，以至于希腊委员会最终强迫米达斯国王减轻这一负担。狡猾的国王同意只向游客提供以下问题的答案：从入口到达房间 $x$ 所需的最小杜卡特数量，是否也足以从入口到达房间 $y$？

输入格式

标准输入的第一行包含一个正整数 $n$，表示迷宫中的房间数量。房间编号从 $1$ 到 $n$，其中 $1$ 号房间是入口。接下来的 $n$ 行描述了迷宫；第 $i$ 行包含两个整数 $l_i, r_i$ ($0 \le l_i, r_i \le n$)，由单个空格分隔。如果 $l_i > 0$，则离开 $i$ 号房间的左侧走廊通往 $l_i$ 号房间。如果 $l_i = 0$，则离开 $i$ 号房间的左侧走廊被封锁。$r_i$ 的含义类似，但它涉及离开 $i$ 号房间的右侧走廊。从 $1$ 号房间出发，可以到达任何其他房间。

下一行包含一个正整数 $z$，表示需要回答的查询数量。接下来的 $z$ 行指定了这些查询；第 $i$ 行包含两个整数 $x_i, y_i$ ($1 \le x_i, y_i \le n$)，由单个空格分隔。这些查询编码了问题：“从入口到达 $x_i$ 号房间所需的最小杜卡特数量，是否也足以从入口到达 $y_i$ 号房间？”

输出格式

标准输出应包含 $z$ 行，第 $i$ 行包含一个单词：如果第 $i$ 个查询的答案为肯定，则输出 TAK（波兰语中的“是”），否则输出 NIE（波兰语中的“否”）。

样例

样例输入 1

12
3 9
0 4
2 5
0 0
6 0
7 8
0 0
0 0
10 12
11 0
0 0
0 0
6
11 8
8 6
11 7
1 2
4 10
3 3

样例输出 1

NIE
TAK
TAK
TAK
NIE
TAK

说明

下图描绘了上述样例中的迷宫：房间用圆圈标记，进入给定走廊所需的杜卡特数量写在中间的方框中。穿过迷宫的可能路线是从上到下的，尽可能选择左侧或右侧的出口走廊。例如，到达 $11$ 号房间需要 $1 + 1 + 2 = 4$ 个杜卡特；这个数量不足以到达 $8$ 号房间，后者需要 $0 + 1 + 1 + 3 = 5$ 个杜卡特（请注意，这是样例中的第一个查询）。

子任务

测试集由以下子集组成。在每个子集中，可能包含多个测试组。