Από εδώ και από εκεί

Πρόβλημα

Στην προσπάθειά της να συμμετάσχει στα πάντα, η Αγγελική κατέληξε να πρέπει να βρίσκεται ταυτόχρονα σε πάρα πολλές εκδηλώσεις. Προφανώς δεν μπορεί να είναι σε όλες ταυτόχρονα, οπότε αναγκαστικά θα πρέπει να μετακινείται πέρα δόθε. Για καλή ή κακή της τύχη, οι δρόμοι που ενώνουν τα μέρη στα οποία πρέπει να βρίσκεται σχηματίζουν ένα δέντρο. Προκειμένου να ελαχιστοποιήσει τις χαμένες διαδρομές, κάθε φορά που πρέπει να πάει από τον προορισμό α στον β επισκέπτεται και όλους τους ενδιάμεσους προορισμούς στο μονοπάτι από το α στο β. Κάθε φορά που επισκέπτεται έναν κόμβο u, πρέπει να μείνει σε αυτόν χρόνο τουλάχιστον ~t_u~. Και επειδή δεν της αρέσει καθόλου να χάνει χρόνο, θέλει κάθε φορά να ξέρει ποιος είναι ο μέγιστος χρόνος που χρειάζεται να μείνει σε κάποιο μέρος. Καθώς η μέρα εξελίσσεται, ο χρόνος αυτός μπορεί να αλλάξει.

Προκειμένου να οργανωθεί, η Αγγελική έχει φτιάξει ένα δέντρο με ~n~ κορυφές (τα ~n~ μέρη στα οποία θα έπρεπε να βρίσκεται). Σε κάθε κορυφή έχει αναθέσει μια τιμή, έστω ~t_i~, τον χρόνο που θα πρέπει να αφιερώσει σε εκείνη την τοποθεσία αν περάσει από αυτή. Για να μπορεί κάθε φορά να οργανώσει κατάλληλα τις μετακινήσεις της, η Αγγελική πρέπει να εκτελεί τα ακόλουθα ερωτήματα:

• Να ανανεώνει την τιμή του κόμβου ~s~ στην τιμή ~x~
• Να βρίσκει τη μέγιστη τιμή στο μονοπάτι μεταξύ 2 κόμβων ~a~ και ~b~

Μορφή Εισόδου

Η πρώτη γραμμή της εισόδου θα περιέχει 2 ακέραιους αριθμούς, τον αριθμό ~n~ των κόμβων και τον αριθμό ~q~ των ερωτημάτων που θα χρειαστεί να εκτελέσει η Αγγελική. Η επόμενη γραμμή θα περιέχει ~n~ ακεραίους, ~t_1, t_2, ..., t_n~ χωρισμένους ανά 2 με ένα κενό, τον αρχικό χρόνο που έχει υπολογιστεί ότι θα χρειαστεί να ξοδέψει σε κάθε κόμβο. Ακολουθούν ~n-1~ γραμμές οι οποίες προσδιορίζουν τις ακμές. Κάθε γραμμή περιέχει 2 ακεραίους ~a, b~ οι οποίοι δηλώνουν ότι υπάρχει ακμή μεταξύ των κορυφών ~a~ και ~b~. Τέλος, υπάρχουν ~q~ γραμμές που αντιστοιχούν στα ερωτήματα. Τα ερωτήματα έχουν μία από τις 2 μορφές:

• ~1 s x~: Άλλαξε την τιμή του κόμβου ~s~ στην τιμή ~x~ (~s~, ~x~ ακέραιοι)
• ~2 a b~: Υπολόγισε την μέγιστη τιμή στο μονοπάτι από τον κόμβο ~a~ στον κόμβο ~b~

Μορφή Εξόδου

Το πρόγραμμα θα πρέπει να εκτυπώνει, σε μία γραμμή, τις απαντήσεις στα ερωτήματα τύπου 2. Η γραμμή θα πρέπει να τελειώνει με χαρακτήρα newline

Περιορισμοί

• ~1\le n, q\le 2*10^5~
• ~1\le a, b, s\le n~
• ~1\le t_i, x \le 10^9~

Παράδειγμα

Είσοδος

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

Έξοδος

4 3