Place

Ο Mirko λατρεύει τα αυτοκίνητα και τελικά κατάφερε να ανοίξει το δικό του εργοστάσιο αυτοκινήτων! Το εργοστάσιο έχει ~N~ υπαλλήλους, καθένας από αυτούς έχει ακριβώς έναν ανώτερο (εκτός από τον Mirko - είναι εξ ορισμού ο ανώτερος όλων). Ο Mirko συμβολίζεται με τον αριθμό ~1~ και οι υπόλοιποι υπάλληλοι με τους αριθμούς ~2~ έως ~N~.
Κάθε εργαζόμενος μπορεί να αυξήσει ή να μειώσει τους μισθούς όλων των υφισταμένων του (τόσο των άμεσων υφισταμένων όσο και των χαμηλότερων στο δέντρο της ιεραρχίας). Ο ρόλος του Mirko είναι να αποτρέψει την κατάχρηση αυτής της εξουσίας, επομένως από καιρό σε καιρό θέλει να γνωρίζει τον μισθό ενός συγκεκριμένου υπαλλήλου.
Σας ζητά να γράψετε ένα πρόγραμμα που θα τον βοηθήσει να παρακολουθεί τις αλλαγές μισθών, δεδομένης μιας σειράς εντολών που περιγράφεται στην ενότητα εισόδου.
Παρατήρηση: ανά πάσα στιγμή, όλοι οι μισθοί θα είναι θετικοί ακέραιοι και θα ταιριάζουν σε τυπικό ακέραιο τύπο 32 bit (int σε C/C++, longint σε Pascal).

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο θετικούς ακέραιους ~N~ ~(1 \leq N \leq 500\,000)~, τον αριθμό των εργαζομένων και τον ~M\;(1 \leq M \leq 500\,000)~, τον αριθμό των μεταβολών του μισθού και τα ερωτήματα για μισθούς.
Οι επόμενες ~N~ γραμμές περιέχουν τις πληροφορίες για τους υπαλλήλους ~1,\;2,\;\ldots\;,\;N~ (αντίστοιχα): αρχικός μισθός και το αναγνωριστικό του άμεσου προϊσταμένου του. Παρατήρηση: Ο Mirko δεν έχει προϊστάμενο, οπότε η γραμμή του θα περιέχει μόνο τον αρχικό του μισθό.
Οι επόμενες ~M~ γραμμές περιέχουν ένα από τα ακόλουθα:

1. p ~A~ ~X~ - ο υπάλληλος \(Α\) αυξάνει (ή μειώνει σε περίπτωση αρνητικού ~X~) τον μισθό όλων των υφισταμένων του κατά το ποσό ~X~ ~(-10\,000 \leq X \leq 10\,000)~.
2. u ~A~ - Ο Μίρκο θέλει να μάθει τον μισθό του υπαλλήλου ~A~.

Έξοδος

Η έξοδος πρέπει να περιέχει μία γραμμή για κάθε ερώτημα "2" στην είσοδο - τον τρέχοντα μισθό του συγκεκριμένου υπαλλήλου.

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

input

2 3
5
3 1
p 1 5
u 2
u 1

output

8
5

input

5 5
4
2 1
6 1
7 1
3 4
u 3
p 1 -1
u 3
p 4 5
u 5

output

6
5
7

input

6 7
5
4 1
3 2
7 3
2 3
3 5
p 3 2
p 2 4
u 3
u 6
p 5 -2
u 6
u 1

output

7
9
7
5