Restaurant Recommendation Rescue

Μια επίδοξη μουσικός, η K, λατρεύει να πηγαίνει για shabu-shabu! Πρόσφατα, έχει επισκεφθεί ~N~ εστιατόρια shabu-shabu, αριθμημένα από ~1~ έως ~N~, ακολουθώντας τον παρακάτω αλγόριθμο:

1. Η K διατηρεί μια διατεταγμένη λίστα προτάσεων, η οποία αρχικά περιέχει το εστιατόριο ~1~.
2. Την ~i~-οστή ημέρα, επισκέπτεται το επόμενο προτεινόμενο εστιατόριο στη λίστα της, το οποίο της προτείνει τα εστιατόρια ~R_i = \{r_{i,1}, \ldots, r_{i,\ell_i}\}~.
3. Η K προσθέτει το ~R_i~ στη λίστα των εστιατορίων που θα επισκεφθεί.
4. Η K επαναλαμβάνει τα βήματα 2-4 μέχρι να εξαντληθούν τα προτεινόμενα εστιατόρια.
5. Η K καταγράφει τον πίνακα ~A_0, \ldots, A_{N-1}~, όπου το ~A_i~ ισούται με τον αριθμό των εστιατορίων που της προτάθηκαν την ~(i+1)~-οστή ημέρα. Δηλαδή, ~A_i = |R_{i+1}|~.

Εγγυάται ότι ~\bigcup_{i=1}^{N} R_i = \{2, \ldots, N\}~ και ότι ~R_i \cap R_j = \emptyset~ για ~i \ne j~, δηλαδή κάθε εστιατόριο, εκτός από το πρώτο, θα προταθεί από ακριβώς ένα άλλο εστιατόριο.

Μόλις η K ολοκληρώσει τη λίστα της, ο φίλος της H, που του αρέσει να κάνει φάρσες, αποφασίζει να της παίξει μια φάρσα! Αντικαθιστά τον πίνακα ~A_0, \ldots, A_{N-1}~ με έναν άλλο πίνακα ~B_0, \ldots, B_{N-1}~. Η K πιστεύει ότι αυτός ο νέος πίνακας ~B_i~ μπορεί απλώς να είναι μια κυκλική μετατόπιση του αρχικού της πίνακα, γι' αυτό σας ζητά να προσδιορίσετε όλες τις δυνατές τιμές ~0 \le k < N~ για τις οποίες ισχύει ~A_i = B_{(i+k) \bmod N}~, για κάθε ~0 \le i < N~, για οποιαδήποτε έγκυρη έξοδο του αλγορίθμου της, ~A_0, \ldots, A_{N-1}~.

Επιπλέον, η K θα εκτελέσει στη συνέχεια ~Q~ πράξεις. Σε κάθε ~i~-οστή πράξη, ανταλλάσσει τα ~B_{x_i}~ και ~B_{y_i}~ και σας ζητά να κάνετε το ίδιο στον νέο πίνακα. Μπορείτε να βοηθήσετε την K να καταλάβει τη φάρσα του φίλου της;

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει δύο ακέραιους αριθμούς, ~N~ (~1 \le N \le 500\,000~) και ~Q~ (~0 \le Q \le 300\,000~).

Η επόμενη γραμμή περιέχει ~N~ μη αρνητικούς ακέραιους αριθμούς, χωρισμένους με κενά, ~B_0, B_1, \ldots, B_{N-1}~ (~0 \le B_i < N~), που αποτελούν την αρχική ακολουθία.

Καθεμία από τις επόμενες ~Q~ γραμμές περιέχει δύο ακέραιους αριθμούς, ~x_i~ και ~y_i~ (~0 \le x_i, y_i < N~ και ~x_i \ne y_i~), οι οποίοι υποδεικνύουν ότι πρέπει να ανταλλάξετε τα ~B_{x_i}~ και ~B_{y_i}~.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι διαθέσιμοι 25 βαθμοί:

Βαθμοί	Περιορισμοί	Επιπλέον περιορισμοί
3	~1 \le N \le 8~	~Q = 0~
7	~1 \le N \le 5000~	~Q = 0~
10	~1 \le N \le 500\,000~	~Q = 0~
5	~1 \le N \le 500\,000~	~0 \le Q \le 300\,000~

Έξοδος

Για καθέναν από τους ~Q+1~ πίνακες (συμπεριλαμβανομένου του αρχικού πίνακα ~B_0, \ldots, B_{N-1}~), έστω ~S = \{k_1, \ldots, k_m\}~ το σύνολο των ακεραίων ~0 \le k_j < N~ για τους οποίους υπάρχει μια έγκυρη έξοδος ~A_0, \ldots, A_{N-1}~ του αλγορίθμου της K, τέτοια ώστε ~A_i = B_{(i+k_j) \bmod N}~ για κάθε ~0 \le i < N~.

Εκτυπώστε σε μία γραμμή τους ακέραιους αριθμούς ~m~ και ~\sum_{i=1}^{m} k_i \bmod 998\,244\,353~, χωρισμένους με ένα κενό.

Ειδικότερα, αν ~S = \emptyset~, η έξοδός σας πρέπει να είναι 0 0.

Παράδειγμα

input

5 3
1 2 0 0 1
0 2
1 3
3 2

output

1 4
1 1
1 2
1 2

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

Ο πίνακας ~A~ είναι ~[1, 1, 2, 0, 0]~. Μπορεί να αποδειχθεί ότι αυτή είναι η μοναδική έγκυρη έξοδος του αλγορίθμου της K που αντιστοιχεί στον πίνακα ~B = [1, 2, 0, 0, 1]~. Μια πιθανή είσοδος για τον αλγόριθμο της K που παράγει αυτόν τον πίνακα ~A~ είναι:

~R_1 = \{2\}~

~R_2 = \{3\}~

~R_3 = \{4, 5\}~

~R_4 = \emptyset~

~R_5 = \emptyset~

Μετά την ανταλλαγή των ~B_0~ και ~B_2~, προκύπτει ο πίνακας:

~B = [0, 2, 1, 0, 1]~.

Μπορεί να αποδειχθεί ότι η μοναδική έγκυρη έξοδος του αλγορίθμου της K που αντιστοιχεί σε αυτόν τον πίνακα είναι ~A = [2, 1, 0, 1, 0]~.

Μια πιθανή είσοδος για τον αλγόριθμο της K που παράγει αυτόν τον πίνακα ~A~ είναι:

~R_1 = \{2, 3\}~

~R_2 = \{4\}~

~R_3 = \emptyset~

~R_4 = \{5\}~

~R_5 = \emptyset~

Συμβουλές για Python (μόνο CIW)

Συνιστάται να χρησιμοποιήσετε γρήγορη είσοδο (για παράδειγμα, sys.stdin.read()) και γρήγορη έξοδο (για παράδειγμα, sys.stdout.write()), αν επιχειρείτε να λύσετε το τελευταίο υποπρόβλημα.