Kutije

Ο Martin έχει n κουτιά με θετικούς ακέραιους αριθμούς από το 1 έως το n. Κάθε κουτί περιέχει ένα παιχνίδι. Τα παιχνίδια επισημαίνονται επίσης με θετικούς ακέραιους αριθμούς από το 1 έως το n, με τέτοιο τρόπο ώστε αρχικά το παιχνίδι με την ετικέτα i να περιέχεται στο κουτί με την ετικέτα i.

Κάθε τόσο, ο Μάρτιν τηλεφωνεί σε έναν από τους φίλους του για να έρθει και να κάνουν παρέα. Μόλις συναντηθούν, ο φίλος του βγάζει τα παιχνίδια από τα κουτιά και αρχίζει να παίζει μαζί τους. Στο μεταξύ, ο Μάρτιν ενδιαφέρεται περισσότερο για τα κουτιά. Μόλις βαρεθούν, ο φίλος του ξαναβάζει τα παιχνίδια στα κουτιά. Ωστόσο, δεν βάζει απαραίτητα κάθε παιχνίδι στο κουτί από το οποίο το πήρε.

Ο Μάρτιν έχει παρατηρήσει ότι κάθε ένας από τους φίλους του ανακατεύει τα παιχνίδια με τον ίδιο τρόπο κάθε φορά. Πιο συγκεκριμένα, κάθε φίλος του έχει τη δική του σειρά από n θετικούς ακέραιους ~p_1,\;\ldots,\;p_n~ που καθορίζει τον τρόπο με τον οποίο θα ξαναβάλει τα παιχνίδια στα κουτιά. Κάθε θετικός ακέραιος από το 1 έως το ~n~ εμφανίζεται ακριβώς μία φορά σε αυτόν τον πίνακα. Ο φίλος του ανακατεύει τα παιχνίδια με τέτοιο τρόπο ώστε στο τέλος της συνάντησής τους το κουτί με την ετικέτα ~i~ περιέχει το παιχνίδι που υπήρχε στο κουτί με την ετικέτα ~p_i~ στην αρχή της συνάντησής τους. Παρατηρήστε ότι, επειδή κάθε θετικός ακέραιος από το 1 έως το ~n~ εμφανίζεται ακριβώς μία φορά στον πίνακα, αφού όλα τα παιχνίδια επιστρέψουν στα κουτιά, κάθε κουτί θα περιέχει πάλι ακριβώς ένα παιχνίδι.

Ο Martin ενδιαφέρεται τώρα να απαντήσει σε ερωτήσεις της ακόλουθης μορφής: αναρωτιέται εάν είναι εφικτό το παιχνίδι με την ετικέτα ~a~ (το οποίο αρχικά βρίσκεται στο κουτί με την ετικέτα ~a~) να καταλήξει στο κουτί με την ετικέτα ~b~ μέσω μιας ακολουθίας συναντήσεων με τους φίλους του. Μια σειρά συναντήσεων σημαίνει ότι ο Martin μπορεί να καλέσει όποιους φίλους θέλει και με οποιαδήποτε σειρά. Μπορεί να καλέσει έναν φίλο πολλές φορές ή και καθόλου. Ο Martin ενδιαφέρεται να απαντήσει σε ~q~ τέτοιες ερωτήσεις.

Είσοδος

Η πρώτη γραμμή περιέχει τους θετικούς ακέραιους ~n,\;m~ και ~q~ - τον αριθμό των κουτιών (επίσης των παιχνιδιών), τον αριθμό των φίλων του Martin και τον αριθμό των ερωτήσεων, αντίστοιχα.

Η ~k~-οστή εκ των ακόλουθων ~m~ γραμμών περιέχει έναν πίνακα θετικών ακεραίων ~p_1,\;\ldots, p_n~ που χρησιμοποιείται από τον ~k~-οστό φίλο του Martin για να βάλει τα παιχνίδια πίσω στα κουτιά. Κάθε θετικός ακέραιος από το 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	15	~m = 1~
2	10	~1 \le n, m, q \le 100~. Επιπλέον, για κάθε ερώτηση για την οποία η απάντηση είναι DA, υπάρχει μια ακολουθία από δύο το πολύ συναντήσεις που επιτυγχάνουν το επιθυμητό αποτέλεσμα.
3	10	~1 \le n, m, q \le 100~
4	35	Κανένας επιπλέπον περιορισμός.

Παραδείγματα

input

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

output

DA
NE
DA

Επεξήγηση του 1ου παραδείγματος:

Για την πρώτη ερώτηση, το παιχνίδι με την ετικέτα 1 βρίσκεται ήδη αρχικά στο κουτί με την ετικέτα 1, οπότε η απάντηση είναι αμέσως DA.

Για τη δεύτερη ερώτηση, παρατηρήστε ότι όσες φορές κι αν ο Μάρτιν καλεί τον φίλο του, τα κουτιά με τις ετικέτες 1 και 2 δεν αλλάζουν ποτέ το περιεχόμενό τους, οπότε η απάντηση είναι ΝΕ.

Για την τρίτη ερώτηση, παρατηρήστε ότι μετά από κάθε συνάντηση, τα περιεχόμενα των κουτιών 3 και 4 ανταλλάσσονται, επομένως μετά από μία μόνο συνάντηση το παιχνίδι με την ετικέτα 3 θα βρεθεί στο κουτί με την ετικέτα 4 και η απάντηση είναι DA.

input

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

output

DA
DA
NE
NE

input

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

output

DA
NE