Tourists

Υπάρχουν ~n~ πόλεις στην Ουτοπία, αριθμημένες από ~1~ έως ~n~. Υπάρχουν μόνο ~n - 1~ δρόμοι διπλής κατεύθυνσης που συνδέουν τις πόλεις. Το ταξίδι μεταξύ κάθε ζεύγους πόλεων είναι εφικτό μόνο με τη χρήση αυτών των δρόμων. Επειδή η Ουτοπία είναι πολλή όμορφη χώρα, υπάρχουν ~m~ τουρίστες, αριθμημένοι από ~1~ έως ~m~, οι οποίοι επισκέπτονται τώρα αυτή τη χώρα. Αρχικά, ο ~i~-οστός τουρίστας επισκέπτεται την πόλη ~a_i~. Είναι δυνατόν πολλοί τουρίστες να βρίσκονται στην ίδια πόλη. Σε αυτή την περίπτωση, μπορεί να ισχύει ότι ~a_i = a_j~ για ένα ζεύγος ~i~, ~j~ τέτοιο ώστε ~i \neq j~.

Κάθε τουρίστας έχει μια άποψη για το πόσο ενδιαφέρουσα είναι η τρέχουσα επίσκεψή του στην Ουτοπία, που αναπαρίσταται ως αριθμός. Αρχικά η άποψη κάθε τουρίστα είναι ~0~. Για να ενθαρρύνει για περισσότερες επισκέψεις, η κυβέρνηση της Ουτοπίας θέλει να αυξήσει την άποψη των τουριστών της χώρας, διοργανώνοντας εκδηλώσεις σε επιλεγμένες πόλεις. Όταν μια εκδήλωση διοργανώνεται στην πόλη ~c~, όλοι οι τουρίστες, οι οποίοι μένουν τότε εκεί, θα αυξήσουν την άποψη τους κατά ~d~, όπου ~d~ είναι μια τιμή που εξαρτάται από τον τύπο της εκδήλωσης.

Κάποιοι από τους τουρίστες έχουν προγραμματίσει να ταξιδέψουν μεταξύ των πόλεων κατά την παραμονή τους στην Ουτοπία. Παρόλο που το ταξίδι από τη μια πόλη στην άλλη διαρκεί ελάχιστα (χάρη στους αποτελεσματικούς δρόμους της Ουτοπίας), εξακολουθεί να είναι ταλαιπωρία και έτσι οδηγεί σε μια χαμηλότερη άποψη τουριστών. Για την ακρίβεια, ένας τουρίστας που ταξίδεψε σε ένα μονοπάτι από ~k~ δρόμους θα μειώσει την άποψή τους κατά ~k~ ( οι τουρίστες πάντα θα επιλέγουν το μικρότερο μονοπάτι μεταξύ δύο πόλεων).

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

Είσοδος

Η πρώτη γραμμή περιέχει τρεις ακεραίους ~n, m, q (2 \le n \le 200\,000,\,1 \le m,\,q \le 200\,000)~ - τον αριθμό των πόλεων, των τουριστών και των ερωτημάτων, αντίστοιχα.

Η δεύτερη γραμμή περιέχει ~m~ ακεραίους ~a_1 , a_2 , \cdots, a_m~ ~(1 \le a_i \le n)~, όπου κάθε ~a_i~ αναπαριστά την πόλη έναρξης από τον ~i~-οστό τουρίστα.

Οι επόμενες ~n - 1~ γραμμές περιέχουν ~2~ ακεραίους η κάθε μία: ~v_i~ και ~w_i~ ~(1 \le v_i, w_i \le n, v_i \neq w_i)~ υπονοώντας ότι υπάρχει δρόμος μεταξύ της πόλης ~v_i~ και της πόλης ~w_i~.

Οι επόμενες ~q~ γραμμές περιγράφουν τα ερωτήματα με τη σειρά που ζητούνται. Κάθε γραμμή έχει μία από τις ακόλουθες τρεις μορφές:

• Το γράμμα '~t~' ακολουθούμενο από τρεις ακεραίους ~f_i , g_i , c_i (1 \le f_i \le g_i \le m, 1 \le c_i \le n)~, που σημαίνει ότι όλοι οι τουρίστες με αριθμούς από ~f_i~ εώς ~g_i~ (κλειστό διάστημα) ταξιδεύουν στην πόλη ~c_i~. Αυτοί που βρίσκονται ήδη στην πόλη ~c_i~ δεν μετακινούνται και η άποψή τους δεν αλλάζει.

• Το γράμμα '~e~' ακολουθούμενο από δύο ακεραίους ~c_i, d_i (1 \le c_i \le n, 0 \le d_i \le 10^9)~, που σημαίνει ότι στην πόλη ~c_i~, διοργανώνεται μια εκδήλωση και αυξάνει την άποψη των τουριστών κατά ~d_i~.

• Το γράμμα '~q~' ακολουθούμενο από έναν ακέραιο ~v_i (1 \le v_i \le m)~, που αντιπροσωπεύει μια ερώτηση σχετικά με την τρέχουσα άποψη του τουρίστα ~v_i~.

Είναι εγγυημένο ότι υπάρχει τουλάχιστον ένα ερώτημα '~q~' στην είσοδο.

Έξοδος

Εκτυπώστε την απάντηση για όλα τα ερωτήματα '~q~', το καθένα σε ξεχωριστή γραμμή, με τη σειρά που ρωτήθηκαν.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~10~	~n, m, q \le 200~
~2~	~15~	~n, m, q \le 2\,000~
~3~	~25~	~m, q \le 2\,000~
~4~	~25~	Όχι ερωτήματα '~e~'.
~5~	~25~	Κανένας επιπλέον περιορισμός.

Παράδειγμα

input

8 4 11
1 4 8 1
6 4
6 3
3 7
6 5
5 1
1 2
1 8
q 4
t 3 4 5
t 2 2 7
q 4
e 5 10
e 1 5
q 4
t 1 1 5
t 2 2 1
q 1
q 2

output

0
-1
9
4
-7