Μπουντρούμια (dungeons)

Ο Ροβέρτος σχεδιάζει ένα νέο παιχνιδι στον υπολογιστή. Στο παιχνίδι υπάρχει ένας ήρωας, ~n~ αντίπαλοι και ~n + 1~ μπουντρούμια. Οι αντίπαλοι είναι αριθμημένοι από το ~0~ μέχρι το ~n - 1~ και τα μπουντρούμια είναι αριθμημένα από το ~0~ μέχρι το ~n~. Ο ~i~-οστός αντίπαλος ( ~0 \le i \le n - 1)~ βρίσκεται στο μπουντρούμι ~i~ και έχει δύναμη ~s[i]~. Δεν υπάρχει αντίπαλος στο μπουντρούμι ~n~.

Ο ήρωας ξεκινά μπαίνοντας στο μπουντρούμι ~x~, έχοντας δύναμη ~z~. Κάθε φορά που ο ήρωας μπαίνει σε ένα μπουντρούμι ~i~ ( ~0 \le i \le n - 1~), έρχεται αντιμέτωπος με τον αντίπαλο ~i~, με αποτέλεσμα ένα από τα πιο κάτω:

• Αν η δύναμη του ήρωα είναι μεγαλύτερη ή ίση από την δύναμη ~s[i]~ του αντιπάλου, τότε ο ήρωας κερδίζει. Αυτό θα έχει ως αποτέλεσμα να αυξηθεί η δύναμη του ήρωα κατά ~s[i]~ (~s[i] \ge 1~). Σε αυτή την περίπτωση ο ήρωας συνεχίζει πηγαίνοντας στο μπουντρούμι ~w[i]~ (~w[i] > i~).
• Σε διαφορετική περίπτωση, ο ήρωας χάνει. Αυτό θα έχει ως αποτέλεσμα να αυξηθεί η δύναμη του ήρωα κατά ~p[i]~ (~p[i] \ge 1~). Σε αυτή την περίπτωση ο ήρωας συνεχίζει πηγαίνοντας στο μπουντρούμι ~l[i]~.

Προσέξτε ότι το ~p[i]~ μπορεί να είναι μικρότερο, ίσο ή μεγαλύτερο από το ~s[i]~. Επίσης, το ~l[i]~ μπορεί να είναι μικρότερο, ίσο ή μεγαλύτερο από το ~i~. Ανεξάρτητα από το αποτέλεσμα της μονομαχίας, ο αντίπαλος παραμένει στο μπουντρούμι ~i~ και διατηρεί δύναμη ~s[i]~.

Το παιχνίδι τελειώνει όταν η ήρωας βρεθεί στο μπουντρούμι ~n~.

Μπορεί να αποδειχθεί ότι το παιχνίδι τελειώνει μετά από έναν πεπερασμένο αριθμό μονομαχιών, ανεξάρτητα από το αρχικό μπουντρούμι και τη δύναμη του ήρωα.

Ο Ροβέρτος σας ζητάει να ελέγξετε το παιχνίδι του εκτελώντας ~q~ προσομοιώσεις. Σε κάθε προσομοίωση, ο Ροβέρτος καθορίζει ένα αρχικό μπουντρούμι ~x~ και μία αρχική δύναμη ~z~. Στόχος σας είναι να βρείτε, για κάθε προσομοίωση, τη δύναμη του ήρωα όταν τελειώσει το παιχνίδι.

Λεπτομέρειες υλοποίησης

Πρέπει να υλοποιήσετε τις παρακάτω συναρτήσεις:

void init(int n, int[] s, int[] p, int[] w, int[] l)

• ~n~: το πλήθος των αντιπάλων.

• ~s~, ~p~, ~w~, ~l~: πίνακες μήκους ~n~. Για ~0 \le i \le n - 1~:

  • ~s[i]~ είναι η δύναμη του αντιπάλου ~i~. Είναι επίσης η δύναμη που θα κερδίσει ο ήρωας αν νικήσει τον αντίπαλο ~i~.
  • ~p[i]~ είναι η δύναμη που θα κερδίσει ο ήρωας αν χάσει από τον αντίπαλο ~i~.
  • ~w[i]~ είναι το μπουντρούμι που θα μπει ο ήρωας αν νικήσει τον αντίπαλο ~i~.
  • ~l[i]~ είναι το μπουντρούμι που θα μπει ο ήρωας αν χάσει από τον αντίπαλο ~i~.

• Αυτή η συνάρτηση καλείται ακριβώς μία φορά, πριν κληθεί η συνάρτηση simulate (βλ. παρακάτω).

int64 simulate(int x, int z)

• ~x~: το αρχικό μπουντρούμι που μπαίνει ο ήρωας.
• ~z~: η αρχική δύναμη του ήρωα.
• Αυτή η συνάρτηση πρέπει να επιστρέψει τη δύναμη του ήρωα όταν τελειώσει το παιχνίδι, υποθέτοντας ότι ο ήρωας ξεκινά το παιχνίδι μπαίνοντας στο μπουντρούμι ~x~ έχοντας δύναμη ~z~.
• Αυτή η συνάρτηση καλείται ακριβώς ~q~ φορές.

Παράδειγμα

Έστω η ακόλουθη κλήση:

init(3, [2, 6, 9], [3, 1, 2], [2, 2, 3], [1, 0, 1])

Το παραπάνω σχήμα απεικονίζει αυτή την κλήση. Κάθε τετράγωνο δείχνει ένα μπουντρούμι. Για τα μπουντρούμια ~0~, ~1~ και ~2~, οι τιμές ~s[i]~ και ~p[i]~ υποδεικνύονται μέσα στα τετράγωνα. Τα κόκκινα βέλη δείχνουν πού πηγαίνει ο ήρωας μετά τη νίκη σε μια μονομαχία, ενώ τα μαύρα βέλη δείχνουν πού πηγαίνει ο ήρωας μετά από ήττα.

Έστω ότι ο βαθμολογητής καλεί την simulate(0, 1).

Το παιχνίδι εξελίσσεται ως εξής:

Επομένως, η συνάρτηση θα πρέπει να επιστρέψει 24.

Έστω ότι ο βαθμολογητής καλεί την simulate(2, 3).

Το παιχνίδι εξελίσσεται ως εξής:

Επομένως, η συνάρτηση θα πρέπει να επιστρέψει 25.

Περιορισμοί

• ~1 \le n \le 400\,000~
• ~1 \le q \le 50\,000~
• ~1 \le s[i], p[i] \le 10^7~ (για κάθε ~0 \le i \le n - 1~)
• ~0 \le l[i], w[i] \le n~ (για κάθε ~0 \le i \le n - 1~)
• ~w[i] > i~ (για κάθε ~0 \le i \le n - 1~)
• ~0 \le x \le n - 1~
• ~1 \le z \le 10^7~

Υποπροβλήματα

1. (~11~ βαθμοί) ~n \le 50\,000~, ~q \le 100~, ~s[i]~, ~p[i] \le 10\,000~ (για κάθε ~0 \le i \le n - 1)~
2. (~26~ βαθμοί) ~s[i]~ = ~p[i]~ (για κάθε ~0 \le i \le n - 1~)
3. (~13~ βαθμοί) ~n \le 50\,000~, όλοι οι αντίπαλοι έχουν την ίδια δύναμη, δηλαδή ~s[i]~ = ~s[j]~ για κάθε ~0 \le i, j \le n - 1~.
4. (~12~ βαθμοί) ~n \le 50\,000~, υπάρχουν το πολύ ~5~ διακριτές τιμές μεταξύ όλων των τιμών ~s[i]~.
5. (~27~ βαθμοί) ~n \le 50\,000~
6. (~11~ βαθμοί) Χωρίς επιπλέον περιορισμούς.

Υποδειγματικός βαθμολογητής

Ο υποδειγματικός βαθμολογητής διαβάζει την είσοδο ως εξής:

• γραμμή ~1~: ~n~ ~q~
• γραμμή ~2~: ~s[0]~ ~s[1] ... s[n - 1]~
• γραμμή ~3~: ~p[0]~ ~p[1] ... p[n - 1]~
• γραμμή ~4~: ~w[0]~ ~w[1] ... w[n - 1]~
• γραμμή ~5~: ~l[0]~ ~l[1] ... l[n - 1]~
• γραμμή ~6~ + ~i~ ( ~0 \le i \le q - 1~): ~x~ ~z~ για την ~i~-οστή κλήση της simulate.

Ο υποδειγματικός βαθμολογητής τυπώνει τις απαντήσεις ως εξής:

• γραμμή ~1~ + ~i~ ( ~0 \le i \le q - 1~) : η τιμή που επιστρέφει η ~i~-οστή κλήση της simulate.