Klasika

Στην αρχή υπάρχει ένας κόμβος που συμβολίζεται ως 1 και αντιπροσωπεύει τη ρίζα ενός δέντρου. Το καθήκον σας είναι η υποστήριξη ερωτημάτων ~Q~ της φόρμας:

• Προσθήκη ~x\,y~ – προσθέτει έναν νέο κόμβο στο δέντρο ως παιδί του κόμβου ~x~. Ο κόμβος που προστέθηκε πρόσφατα και ο κόμβος ~x~ είναι συνδεδεμένοι με μια ακμή βάρους ~y~. Ο κόμβος που προστέθηκε πρόσφατα συμβολίζεται με αριθμό ίσο με τον αριθμό των κόμβων από τους οποίους αποτελείται το δέντρο μετά την προσθήκη του.
• Ερώτημα ~a\,b~ – βρίσκει το μεγαλύτερο μονοπάτι σε ένα δέντρο που ξεκινά από τον κόμβο ~a~ και τελειώνει σε κάποιον κόμβο του υποδέντρου του κόμβου ~b~ (που από μόνο του θεωρείται ότι βρίσκεται στο δικό του υποδέντρο). Το μήκος του μονοπατιού ορίζεται ως "αποκλειστικό ή" (exclusive or) (xor ή ⊗) των βαρών όλων των ακμών από τις οποίες αποτελείται το μονοπάτι.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~Q~ ~(1 \le Q \le 200\,000)~.

Η ~i~-οστή των επόμενων ~Q~ γραμμών περιέχει το ~i~-οστό ερώτημα του οποίου η μορφή αντιστοιχεί σε ένα από τα ερωτήματα. Οι τιμές ~x,\,a~ και ~b~ θα αναφέρονται σε έναν υπάρχοντα κόμβο εκείνη τη στιγμή και η τιμή ~y~ δεν θα είναι μεγαλύτερη από ~2^{30}~.

Έξοδος

Θα πρέπει να δώσετε μια απάντηση σε κάθε ερώτημα τύπου Query. Κάθε απάντηση θα πρέπει να τυπωθεί σε ξεχωριστή γραμμή με τη σειρά με την οποία εμφανίζονται τα αντίστοιχα ερωτήματα στην είσοδο.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	11	~Q \le 200~
2	22	~Q \le 2\,000~
2	33	Σε όλα τα ερωτήματα τύπου Query ισχύει ~b = 1~
4	44	Κανένας επιπλέον περιορισμός.

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

input

4
Add 1 5
Query 1 1
Add 1 7
Query 1 1

output

5
7

input

6
Add 1 5
Add 2 7
Add 1 4
Add 4 3
Query 1 1
Query 2 4

output

7
2

input

10
Add 1 4
Add 1 9
Add 1 10
Add 2 2
Add 3 3
Add 4 4
Query 4 2
Query 1 3
Add 6 7
Query 1 3

output

14
10
13