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 initially the toy with label i is 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 playing with them. Martin, meanwhile, is more interested in the boxes. Once they get bored, his friend puts the toys back into the boxes. However, he does not necessarily put every toy into the box it was taken from.

Martin has noticed that each of his m friends scrambles the toys the same way every time. More precisely, each friend has his own array of n positive integers p1, ..., pn that determines how he puts the toys back into the boxes. Every positive integer from 1 to n appears exactly once in this array. The friend scrambles the toys so that, at the end of the meeting, the box with label i contains the toy that was in the box with label pi at the start of the meeting. Since every positive integer from 1 to n appears exactly once in the array, after all the toys are back in the boxes, each box again contains exactly one toy.

Martin now wants to answer questions of the following form: is it possible for the toy with label a (which is initially in the box with label a) to end up in the box with label b through a sequence of meetups with his friends? A sequence of meetups means Martin can call whichever friends he wants, in any order. He can call a friend multiple times, or not at all. Martin wants to answer q such questions.

The first line contains positive integers n, m and q: the number of boxes (and toys), the number of Martin's friends, and the number of questions.

The k-th of the following m lines contains an array of positive integers p1, ..., pn used by Martin's k-th friend to put the toys back into the boxes. Every 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 ≤ a, b ≤ n) representing a question.

Print the answers to the given questions in q lines, in order: DA if it is possible to get the toy in question into the desired box, and NE otherwise.

In every subtask, 1 ≤ n, m ≤ 1000 and 1 ≤ q ≤ 500 000.

Clarification of the first example:

For the first question, the toy with label 1 is already initially in the box with label 1, so the answer is immediately DA.

For the second question, no matter how many times Martin calls his friend over, the boxes with labels 1 and 2 never change their contents, so the answer is NE.

For the third question, after each meetup the contents of boxes 3 and 4 are swapped, so after only one meetup the toy with label 3 ends up in the box with label 4 and the answer is DA.