Martin 有 $n$ 个标有 $1$ 到 $n$ 正整数的盒子。每个盒子里都有一个玩具。玩具也标有 $1$ 到 $n$ 的正整数，初始时，标号为 $i$ 的玩具在标号为 $i$ 的盒子里。

Martin 偶尔会叫他的 $m$ 个朋友中的一个过来聚会。聚会时，朋友会把玩具从盒子里拿出来玩。在此期间，Martin 更关心盒子。当他们玩腻了之后，朋友会把玩具放回盒子里。但是，他并不一定把每个玩具放回它原来所在的盒子里。

Martin 注意到他的 $m$ 个朋友中，每个人每次打乱玩具的方式都是固定的。更准确地说，每个朋友都有一个属于他自己的包含 $n$ 个正整数的数组 $p_1, \dots, p_n$，这决定了他将玩具放回盒子的方式。这个数组中 $1$ 到 $n$ 的每个正整数恰好出现一次。朋友打乱玩具的方式是：在聚会结束时，标号为 $i$ 的盒子里装的是聚会开始时在标号为 $p_i$ 的盒子里的玩具。注意，由于 $1$ 到 $n$ 的每个正整数在数组中恰好出现一次，因此当所有玩具放回盒子后，每个盒子里将再次恰好有一个玩具。

Martin 现在想回答以下形式的问题：他想知道通过一系列与朋友的聚会，标号为 $a$ 的玩具（初始时在标号为 $a$ 的盒子里）是否可能最终出现在标号为 $b$ 的盒子里。一系列聚会意味着 Martin 可以按任意顺序呼叫他想要的任何朋友。他可以多次呼叫同一个朋友，也可以一次都不呼叫。Martin 需要回答 $q$ 个这样的问题。

输入格式

第一行包含正整数 $n, m$ 和 $q$，分别表示盒子的数量（也是玩具的数量）、Martin 的朋友数量以及问题的数量。

接下来的 $m$ 行，第 $k$ 行包含一个正整数数组 $p_1, \dots, p_n$，用于 Martin 的第 $k$ 位朋友将玩具放回盒子。数组中 $1$ 到 $n$ 的每个正整数恰好出现一次。

接下来的 $q$ 行，每行包含两个正整数 $a$ 和 $b$ ($1 \le a, b \le n$)，表示一个问题。

输出格式

按顺序输出 $q$ 行问题的答案：如果玩具可以到达目标盒子，输出 DA，否则输出 NE。

数据范围

在每个子任务中，均满足 $1 \le n, m \le 1000, 1 \le q \le 500\,000$。

样例

输入 1

4 1 3
1 2 4 3
1 1
1 2
3 4

输出 1

DA
NE
DA

输入 2

4 2 4
2 1 3 4
1 2 4 3
2 1
3 4
1 4
2 3

输出 2

DA
DA
NE
NE

输入 3

6 2 2
2 1 4 5 3 6
3 2 4 1 5 6
1 5
6 3

输出 3

DA
NE

说明

第一个样例的说明： 对于第一个问题，标号为 $1$ 的玩具初始时已经在标号为 $1$ 的盒子里，所以答案直接为 DA。 对于第二个问题，注意无论 Martin 呼叫他的朋友多少次，标号为 $1$ 和 $2$ 的盒子的内容都不会改变，所以答案为 NE。 对于第三个问题，注意每次聚会后，标号为 $3$ 和 $4$ 的盒子的内容都会交换，因此仅经过一次聚会，标号为 $3$ 的玩具就会出现在标号为 $4$ 的盒子里，所以答案为 DA。