Cho đồ thị gồm ~n~ đỉnh được đánh số từ ~1~ đến ~n~, ban đầu chưa có cạnh nào.

Một nhóm bạn gồm ~m~ người đang chơi một trò chơi trên đồ thị này. Mỗi người lần lượt chọn một dãy hoán vị ~p_1,p_2,...,p_n~ gồm ~n~ phần tử, sau đó thêm các cạnh nối một chiều từ đỉnh ~p_i~ đến đỉnh ~i~. Vì vậy đồ thị có tổng cộng \(m×n\) cạnh.

Sau đó, các bạn trong nhóm lại đố nhau ~q~ câu hỏi, mỗi câu hỏi yêu cầu kiểm tra xem có tồn tại đường đi từ đỉnh ~u~ đến đỉnh ~v~ hay không. Lưu ý rằng đường đi có thể đi qua một đỉnh nhiều lần.

Input

• Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~q~ ~(1 \le n,m \le 1000; \; 1 \le q \le 5.10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng chứa một dãy hoán vị độ dài ~n~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ ~(1 \le u,v \le n)~ mô tả câu hỏi.

Output

• Với mỗi câu hỏi, in ra trên một dòng: ~\text{DA}~ nếu có tồn tại đường đi, ngược lại in ~\text{NE}~.

Samples

Sample Input 1

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

Sample Output 1

DA
NE
DA

Sample Input 2

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

Sample Output 2

DA
DA
NE
NE

Sample Input 3

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

Sample Output 3

DA
NE

Scoring

• Subtask ~1~ với ~30\%~ số điểm: ~m=1~
• Subtask ~2~ với ~30\%~ số điểm: ~n,m,q \le 100~
• Subtask ~3~ với ~40\%~ số điểm: Không còn ràng buộc gì thêm

Clarification

• Trong ví dụ đầu tiên, với hoán vị ~\{1,2,4,3\}~, tiến hành thêm các cạnh nối một chiều: \(1→1\), \(2→2\), \(4→3\), \(3→4\).