Through Another Maze Darkly

Υπάρχει ένας λαβύρινθος ο οποίος σχηματίζεται ενώνοντας ~N~ δωμάτια μέσω ~N-1~ διαδρόμων. Τα δωμάτια είναι αριθμημένα από το ~1~ έως το ~N~ και κάθε δωμάτιο το σχήμα ενός κύκλου. Οι διάδρομοι έχουν τους ακόλουθους περιορισμούς:

• Κάθε διάδρομος σχηματίζει μια σύνδεση μεταξύ δύο μοναδικών δωματίων.

• Κάθε ζεύγος δωματίων ενώνεται από ένα ακριβώς μονοπάτι συνδεδεμένων διαδρόμων.

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

• Περιστρέψτε το λέιζερ του δωματίου σύμφωνα με τη φορά του ρολογιού μέχρι να δείξε προς έναν άλλον διάδρομο.

• Ακολουθήστε το λέιζερ του δωματίου και διασχίστε τον διάδρομο.

• Επαναλάβετε τα προηγούμενα δύο βήματα επ' αόριστον.

Δημιουργήσατε ~Q~ ερωτήματα για να ερευνήσετε αυτή τη στρατηγική. Για κάθε ερώτημα, σας δίνεται ένας ακέραιος ~K~ και ξεκινάτε στο δωμάτιο ~1~. Καθορίστε το τελικό δωμάτιο αφού διασχίσετε ακριβώς ~K~ διαδρόμους. Όλα τα λέιζερ θα γυρίσουν ξανά στον αρχικό τους προσανατολισμό μετά από κάθε ερώτημα.

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους ~N~ και ~Q~ (~2~ ~\le~ ~N~ ~\le~ ~800\,000~, ~1~ ~\le~ ~Q~ ~\le~ ~800\,000~).

Οι επόμενες ~N~ γραμμές περιγράφουν τη διάταξη του λαβύρινθου, με την ~i~-οστη από αυτές τις γραμμές να περιγράφει το δωμάτιο ~i~. Συγκεκριμένα, περιέχει έναν ακέραιο ~k~, τον αριθμό των διαδρόμων που συνδέονται με το δωμάτιο ~i~, ακολουθούμενο από ~k~ ακέραιους ~c_1~, ~c_2~, ..., ~c_k~, που δηλώνουν τα δωμάτια στα οποία οδηγούν αυτοί οι ~k~ διάδρομοι με δεξιόστροφη σειρά (με τη φορά του ρολογιού). Τέλος, το λέιζερ του δωματίου ~i~ αρχικά δείχνει προς τον διάδρομο που οδηγεί στο δωμάτιο ~c_1~.

Οι τελικές ~Q~ φραμμές περιγράφουν ένα ερώτημα, με κάθε γραμμή να περιέχει έναν ακέραιο ~K~ (~1~ ~\le~ ~K~ ~\le~ ~10^{15}~).

Βαθμολογία

Για ~4~ από τους ~25~ διαθέσιμους βαθμούς, ο ~i~-οστος διάδρομος σχηματίζει μια σύνδεση μεταξύ του δωματίου ~i~ και ~i + 1~

Για επιπλέον ~4~ από τους ~25~ διαθέσιμους βαθμούς, ~N~ ~\le~ ~2\,000~ και ~Q~ ~\le~ ~2\,000~.

Για επιπλέον ~12~ από τους ~25~ διαθέσιμους βαθμούς, ~Q = 1~.

Έξοδος

Εκτυπώστε ~Q~ γραμμές απαντώντας στα ερωτήματα με τη σειρά.

Παράδειγμα

input

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

output

2
1
2
4
2
3

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

Αυτή είναι η αρχική κατάσταση του λαβύρινθου.

Σύμφωνα με την στρατηγική θα επισκευτούμε τα παρακάτω δωμάτια με τη σειρά:

~1~,~2~,~1~,~2~,~4~,~2~,~3~,...