Alias

Ο Novak και ο Rafael παίζουν μια απλοποιημένη έκδοση του παιχνιδιού Alias. Ο Novak πρέπει να κάνει τον Rafael να μαντέψει μια λέξη χωρίς να την πει. Ο Rafael έχει ~n~ λέξεις στη βάση δεδομένων του μυαλού του και υπάρχουν ~m~ συνδέσεις μεταξύ ορισμένων λέξεων. Η σύνδεση μεταξύ των λέξεων ~x~ και ~y~, με το χρόνο ~t~, σημαίνει ότι αν ο Rafael θυμηθεί τη λέξη ~x~ ή την ακούσει, μετά από ~t~ χιλιοστά του δευτερολέπτου θα θυμηθεί και τη λέξη ~y~.

Ο Novak και ο Rafael θα παίξουν ~q~ γύρους. Σε κάθε γύρο, ο Novak θέλει να ξέρει: αν πει τη λέξη ~a~, μετά από πόσα χιλιοστά του δευτερολέπτου θα θυμηθεί για πρώτη φορά ο Rafael τη λέξη ~b~; Οι γύροι είναι ανεξάρτητοι.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~n\;(2 \le n \le 1\,000)~ και ~m\;(1 \le m \le 1\,000)~, τον αριθμό των λέξεων και τον αριθμό των συνδέσεων.

Κάθε μία από τις ακόλουθες m γραμμές περιέχει δύο διαφορετικές λέξεις ~x_i~ και ~y_i~ και έναν ακέραιο ~t_i\;(1 \le t_i \le 10^9)~, που περιγράφουν μια σύνδεση. Οι λέξεις αποτελούνται από το πολύ 20 πεζά γράμματα. Όλες οι λέξεις που έχει στη βάση δεδομένων του ο Rafael θα εμφανίζονται τουλάχιστον μία φορά. Είναι πιθανό να υπάρχουν πολλαπλές συνδέσεις μεταξύ κάποιων ζευγαριών λέξεων.

Η επόμενη γραμμή περιέχει έναν ακέραιο αριθμό ~q\;(1 \le q \le 1\,000)~, τον αριθμό των γύρων.

Κάθε μία από τις επόμενες ~q~ γραμμές περιέχει δύο διαφορετικές λέξεις ~a_i~ και ~b_i~, τη λέξη που θα πει ο Novak και τη λέξη που πρέπει να θυμηθεί ο Rafael στον i-οστό γύρο. Και οι δύο λέξεις εμφανίζονται στη βάση δεδομένων του Rafael.

Έξοδος

Στην έξοδο θα υπάρχουν ~q~ γραμμές. Στην i-οστή γραμμή εξόδου θα εμφανίζεται ο χρόνος για τον i-οστό γύρο, σε χιλιοστά του δευτερολέπτου, ή η λέξη "Roger", αν ο Rafael δεν θυμηθεί ποτέ τη λέξη.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 20 πόντων, ισχύει ~1 \le n \le 10~.
Σε δοκιμαστικές περιπτώσεις αξίας επιπλέον 20 πόντων, ισχύει ~1 \le n \le 100~.

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

input

3 2
novak goat 1
goat simulator 3
2
novak simulator
simulator goat

output

4
Roger

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

Στον πρώτο γύρο ο Novak θα πει τη λέξη novak. Μετά από 1 χιλιοστό του δευτερολέπτου, ο Rafael θα θυμηθεί τη λέξη goat και μετά από 3 ακόμη χιλιοστά του δευτερολέπτου την απαιτούμενη λέξη simulator. Στον δεύτερο γύρο, ο Novak θα πει τη λέξη simulator, αλλά ο Rafael δεν θα θυμηθεί τις άλλες λέξεις.

input

3 3
kile legend 4
legend beer 5
beer kile 6
2
kile beer
legend kile

output

9
11

input

4 5
rafael me 5
me ow 6
ow ausopenfinal 2012
ausopenfinal me 2
rafael ausopenfinal 2
3
rafael me
me rafael
ow me

output

4
Roger
2014