34ος ΠΔΠ Καμπ (κοινά)
VATRAXIA (vatraxia)

Το εργαστήριο FrogLab του ΕΜΠ κατασκευάζει γενετικά μεταλλαγμένα βατράχια για αποστολές διάσωσης σε λίμνες. Για να κατευθύνονται τα διασωστικά βατράχια στο σημείο διάσωσης, τοποθετούνται νούφαρα διαφορετικής ελαστικότητας στην σειρά. Συγκεκριμένα, υπάρχουν $N$ διατεταγμένα νούφαρα και το $i$-οστό εξ’αυτών έχει ελαστικότητα $a_i$. Αν ένα βατράχι αφεθεί στο νούφαρο $i$, τότε αυτό θα κάνει ένα άλμα μήκους $a_i$ και θα μεταφερθεί στο νούφαρο $j + a_j$ κ.ο.κ. Όταν το $j + a_j$ ξεπεράσει το $N$, θεωρούμε ότι το βατράχι έχει περάσει την ακολουθία με τα νούφαρα και έχει φτάσει στο σημείο διάσωσης.

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

$\texttt{0 p x}$
$\texttt{1 p}$

Στην μορφή $0$, οι επιστήμονες αλλάζουν το νούφαρο στην θέση $p$ με ένα άλλο ελαστικότητας $x$. Δηλαδή θέτουν $a_p = x$. Στην μορφή 1, αφήνουν ένα βατράχι στο νούφαρο $p$ και μετράνε το πλήθος των αλμάτων που αυτό κάνει μέχρι να φτάσει στο σημείο διάσωσης καθώς και το νούφαρο από το οπίο έγινε το τελευταίο άλμα.

Η ομάδα δοκιμών του εργαστηρίου αναθέτει σε εσάς την δουλειά να κατασκευάσετε μία προσομοίωση αυτής της διαδικασίας. Συγκεκριμένα, σας δίνονται οι αρχικές ελαστικότητες για να $N$ νούφαρα καθώς και τα $Q$ πειράματα που εκτελούνται. Στόχος σας είναι να εκτελέσετε επιτυχώς όλα τα $Q$ πειράματα, και για κάθε πείραμα μορφής $1$ να τυπώσετε το τελευταίο νούφαρο από το οποίο περνάει το βατράχι, καθώς και τον συνολικό αριθμό αλμάτων που κάνει.

Δεδομένα εισόδου (vatraxia.in)

Στην πρώτη γραμμή της εισόδου θα υπάρχει ένας θετικός ακέραιος $T$, το πλήθος των test cases. Σε καθένα από τα επόμενα $T$ test cases θα υπάρχουν στην πρώτη γραμμή δύο μη-αρνητικοί ακέραιοι $N$ και $Q$: το πλήθος των νουφάρων και το πλήθος των πειραμάτων που θα χρειαστεί να εκτελέσετε. Η δεύτερη γραμμή περιέχει $N$ θετικούς ακεραίους $a_1, a_2, \ldots, a_N$ που δηλώνουν τις αρχικές ελαστικότητες για τα $N$ νούφαρα. Τέλος, οι επόμενες $Q$ γραμμές της εισόδου περιέχουν από ένα πείραμα η καθεμία που έχει μία από τις μορφές παραπάνω.

Δεδομένα εξόδου (vatraxia.out)

Η έξοδος θα πρέπει να περιέχει τόσες γραμμές όσα είναι συνολικά τα πειράματα τύπου $1$. Κάθε γραμμή θα περιέχει δύο αριθμούς που δηλώνουν το νούφαρο από το οποίο έγινε το τελευταίο άλμα καθώς και το πλήθος αλμάτων μέχρι το βατράχι στο αντίστοιχο πείραμα $1$ να φτάσει στο σημείο διάσωσης.

Παράδειγμα αρχείου εισόδου-εξόδου:

vatraxia.in	vatraxia.out
1 8 5 1 1 1 1 1 2 8 2 1 1 0 1 3 1 1 0 3 4 1 2	8 7 8 5 7 3

Εξήγηση παραδείγματος: Στο πρώτο και μοναδικό test case του παραδείγματος υπάρχουν $8$ νούφαρα με αρχικές ελαστικότητες αυτές που φαίνονται στην 3η γραμμή. Γίνονται $5$ πειράματα.

Στο 1ο πείραμα αφήνουμε ένα βατράχι στο νούφαρο $1$. Αυτό το βατράχι ακολουθεί την διαδρομή $(1, 2, 3, 4, 5, 6, 8)$ προτού φτάσει στο σημείο διάσωσης. Άρα η 1η γραμμή εξόδου περιέχει το $8$ που είναι το τελευταίο νούφαρο από το οποίο διέρχεται, και το $7$ που είναι το πλήθος των αλμάτων που έκανε.
Στο 2ο πείραμα (που είναι της μορφής $0$) αλλάζουμε την ελαστικότητα στο νούφαρο $1$ στην τιμή $3$.
Στο 3ο πείραμα αφήνουμε πάλι ένα βατράχι στο νούφαρο $1$. Αυτή την φορά το νούφαρο $1$ έχει ελαστικότητα $3$ αντί για $1$, οπότε η διαδρομή που ακολουθεί το βατράχι είναι $(1, 4, 5, 6, 8)$. Πάλι το τελευταίο νούφαρο είναι το $8$, αλλά τώρα χρειάστηκαν συνολικά $5$ άλματα. Για αυτό τυπώνουμε $\texttt{8 5}$ στην δεύτερη γραμμή εξόδου.
Στο 4ο πείραμα αλλάζουμε την ελαστικότητα στο νούφαρο $3$ σε τιμή $4$.
Στο 5ο πείραμα αφήνουμε ένα βατράχι στο νούφαρο $2$. Αυτό ακολουθεί την διαδρομή $(2, 3, 7)$, οπότε χρειάζεται $3$ άλματα και το τελευταίο νούφαρο από το οποίο διέρχεται είναι το $7$. Άρα τυπώνουμε $\texttt{7 3}$ στην τελευταία γραμμή εξόδου.

Περιορισμοί

$1 \leq N \leq 100.000$,
$1 \leq Q \leq 100.000$,
Το συνολικό άθροισμα όλων των $N$ δε θα υπερβαίνει το $200.000$. Όμοια για το $Q$.
Ανά πάσα στιγμή θα είναι $1 \leq a_i \leq 100.000$ για κάθε $i$.

Subtasks

Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι $1 \leq N \leq 1.000$, $1 \leq Q \leq 1.000$ και το συνολικό άθροισμα των $N$ σε κάθε αρχείο δεν θα υπερβαίνει το $2.000$. Όμοια για το $Q$.
Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα ισχύουν οι αρχικοί περιορισμοί και επιπλέον θα υπάρχουν μόνο πειράματα τύπου $1$ στην είσοδο.