Boxes

Martin has n boxes labeled with positive integers from 1 to n. Each box contains a toy. The toys are also labeled with positive integers from $1$ to $n$ and in such a way that initially the toy with label $i$ is contained in the box with label $i$.

From time to time, Martin calls one of his $m$ friends to come over and hang out. Once they meet up, his friend takes the toys out of the boxes and starts having fun with them. In the meantime, Martin is more interested in the boxes. Once they become bored, his friend puts the toys back into the boxes. However, he doesn’t necessarily put every toy in the box it was taken from.

Martin has noticed that each of his $m$ friends scrambles the toys in the same way each time. More precisely, each of his friends has his own array of $n$ positive integers $p_1,...,p_n$ which determines the way he will put the toys back into the boxes. Every positive integer from $1$ to $n$ appears exactly once in this array. His friend scrambles the toys in such a way that at the end of their meeting the box with label $i$ contains the toy that was in the box with label $p_i$ at the start of their meeting. Notice that, because every positive integer from $1$ to $n$ appears exactly once in the array, after all the toys are back in the boxes, each box will again have exactly one toy in it.

Martin is now interested in answering questions of the following form: he is wondering whether it is possible that the toy with label $a$ (which is initially in box with label $a$) can end up in the box with label $b$ via a sequence of meetups with his friends. A sequence of meetups means that Martin can call whichever friends he wants and in any order. He can call a friend multiple times, or not at all. Martin is interested in answering $q$ such questions.

Input

The first line contains positive integers $n,m(1\le n,m\le 1000)$ and $q(1\le q\le 5\cdot 10^5)$ — the number of boxes (also toys), the number of Martin’s friends and the number of questions, respectively.

The $k$-th of the following $m$ lines contains an array of positive integers $p_1,...,p_n$ that is used by Martin’s $k$-th friend for putting the toys back into the boxes. Each positive integer from $1$ to $n$ appears exactly once in the array.

Each of the following $q$ lines contains two positive integers $a$ and $b(1\le a,b\le n)$ which represent a question.

Output

In $q$ lines print the answer to the given qustions, in order: DA if it is possible to get the toy in question to the desired box, and NE otherwise.

Examples