상자

마틴에게는 1부터 n까지의 양의 정수로 번호가 붙은 n개의 상자가 있다. 각 상자에는 장난감이 하나씩 들어 있다. 장난감에도 1부터 n까지의 양의 정수 번호가 붙어 있으며, 처음에는 번호 i인 장난감이 번호 i인 상자에 들어 있다.

때때로 마틴은 m명의 친구 중 한 명을 불러 함께 논다. 만나면 친구가 상자에서 장난감을 꺼내 가지고 논다. 그동안 마틴은 상자 쪽에 더 관심이 있다. 둘이 지루해지면 친구가 장난감을 상자에 다시 넣는다. 하지만 꺼낸 상자에 반드시 그 장난감을 넣는 것은 아니다.

마틴은 m명의 친구 각자가 매번 같은 방식으로 장난감을 뒤섞는다는 것을 알아냈다. 더 정확히는, 친구마다 장난감을 상자에 되돌려 넣는 방식을 정하는 n개의 양의 정수 배열 p1, ..., pn이 있다. 이 배열에는 1부터 n까지의 양의 정수가 각각 정확히 한 번씩 나타난다. 친구는 모임이 끝날 때 번호 i인 상자에, 모임이 시작될 때 번호 pi인 상자에 있던 장난감이 들어가도록 장난감을 뒤섞는다. 배열에 1부터 n까지의 양의 정수가 각각 정확히 한 번씩 나타나므로, 모든 장난감이 상자에 돌아간 뒤에도 각 상자에는 다시 장난감이 정확히 하나씩 들어 있다.

마틴은 이제 다음과 같은 질문에 답하려고 한다. 처음에 번호 a인 상자에 있는 번호 a인 장난감이, 친구들과의 모임을 여러 번 거쳐 번호 b인 상자에 들어갈 수 있는가? 모임의 순서는 마틴이 원하는 친구를 원하는 순서로 부르면 된다. 같은 친구를 여러 번 불러도 되고 한 번도 부르지 않아도 된다. 마틴은 이런 질문 q개에 답하려고 한다.

첫째 줄에 양의 정수 n, m, q가 주어진다. 각각 상자(겸 장난감)의 수, 마틴의 친구 수, 질문의 수이다.

다음 m개 줄 중 k번째 줄에는 마틴의 k번째 친구가 장난감을 상자에 되돌려 넣을 때 쓰는 양의 정수 배열 p1, ..., pn이 주어진다. 이 배열에는 1부터 n까지의 양의 정수가 각각 정확히 한 번씩 나타난다.

다음 q개 줄에는 양의 정수 a와 b(1 ≤ a, b ≤ n)가 주어지며, 이는 질문을 나타낸다.

q개 줄에 주어진 질문의 답을 순서대로 출력한다. 해당 장난감을 원하는 상자에 넣을 수 있으면 DA, 그렇지 않으면 NE를 출력한다.

모든 부분문제에서 1 ≤ n, m ≤ 1000, 1 ≤ q ≤ 500 000이다.

첫 번째 예제에 대한 설명:

첫 번째 질문에서 번호 1인 장난감은 처음부터 번호 1인 상자에 있으므로 답은 바로 DA이다.

두 번째 질문에서 마틴이 친구를 몇 번 부르든 번호 1과 2인 상자의 내용물은 절대 바뀌지 않으므로 답은 NE이다.

세 번째 질문에서 모임이 끝날 때마다 번호 3과 4인 상자의 내용물이 서로 교환되므로, 모임을 한 번만 거쳐도 번호 3인 장난감이 번호 4인 상자에 들어가게 되어 답은 DA이다.