Byteasar 得到了一台新电脑，并正在学习如何编程。一个程序是一系列指令，为了方便起见，指令共有 $k$ 种，编号从 $1$ 到 $k$。某些指令对是可交换的，即如果它们在程序中相邻（无论顺序如何），交换它们会得到一个行为相同的等价程序。其余不具备此性质的指令对被称为不可交换的。目前，Byteasar 编写了两个长度均为 $n$ 的程序，他想知道这两个程序是否等价。请帮帮他！

输入格式

标准输入的第一行包含三个整数 $n$，$k$ 和 $m$，用空格分隔，分别表示程序的指令长度、电脑的指令种类数以及不可交换的指令对数量。

接下来的 $m$ 行指定了这些对：每行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le k$)，用空格分隔，表示编号为 $a$ 和 $b$ 的指令对是不可交换的。你可以假设每对指令在输入中最多出现一次。

最后两行总结了这两个程序：每行包含一个由 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le k$) 组成的序列，用空格分隔，表示相应程序中连续的指令编号。

输出格式

在标准输出的唯一一行中，如果输入的两个程序等价，则打印一个单词：TAK（波兰语中的“是”）；如果不等价，则打印 NIE（波兰语中的“否”）。

样例

输入格式 1

5 3 1
2 3
1 1 2 1 3
1 2 3 1 1

输出格式 1

TAK

说明

第一个样例的解释：以下交换序列将第一个程序转换为第二个程序：(2,3), (4,5), (3,4)，其中 $(i, i + 1)$ 表示交换当前程序中第 $i$ 个和第 $(i + 1)$ 个指令（即在之前的交换之后）。

输入格式 2

3 3 1
2 3
1 2 3
3 2 1

输出格式 2

NIE

样例评分测试

1ocen: $n = 50, k = 50, m = 1$; 程序: $(1, 2, \dots, 49, 50)$ 和 $(50, 49, \dots, 2, 1)$; 答案: NIE。

2ocen: $n = 99\,999, k = 3, m = 1$; 不可交换指令: 1 和 2, 程序: $(1, 2, 3, 1, 2, 3, \dots, 1, 2, 3)$ 和 $(3, 1, 2, 3, 1, 2, \dots, 3, 1, 2)$; 答案: TAK。

3ocen: $n = 100\,000, k = 1000, m = 50\,000$; 程序: $(13, 13, 13, \dots, 13)$ 和 $(37, 37, 37, \dots, 37)$; 答案: NIE。

评分

测试集由以下子集组成。在每个子集中，可能包含多个测试组。所有测试均满足以下条件：$1 \le n \le 100\,000$，$1 \le k \le 1000$，$0 \le m \le 50\,000$。