Mirko yêu thích xe ô tô và cuối cùng gia đình của anh ta cũng sở hữu được một nhà máy săn xuất ô tô. Nhà máy có \(N\) nhân viên, mỗi nhân viên có đúng một người quản lý (ngoại trừ Mirko – anh ta là cấp trên của tất cả). Mirko là nhân viên số 1, những người khác đánh số từ 2 đến \(N\).

Mỗi nhân viên có thể tăng hoặc giảm lương cho tất cả những người mà anh ta quản lý (trực tiếp hoặc thông qua một dãy cấp trên). Mirko không muốn cấp dưới lạm quyền hạn nên anh ta muốn biết mức lương cụ thể của một nhân viên cụ thể ở một thời điểm nào đó. Viết chương trình thực hiện điều này.

Input:

• Dòng 1: chứa 2 số nguyên dương \(N\) và \(M ( N ≤ 500000, M ≤ 500000)\) trong đó \(M\) là số lượng các thời điểm xảy ra sự kiện.

• \(N\) dòng tiếp theo, dòng thứ \(i\) mô tả mức lương khởi đầu và người quản lý trực tiếp của nhân viên \(i\). Chú ý rằng vì Mirko lãnh đạo toàn bộ nên ở dòng này chỉ có mức lương khởi đầu.

• \(M\) dòng tiếp theo mô tả sự kiện lần lượt theo thời gian với một trong 2 loại:

1. \(P\) \(A\) \(X\) nhân viên A tăng (hoặc giảm nếu \(X < 0\)) lương của toàn bộ cấp dưới của mình một lượng \(X (-10000 ≤ X ≤ 10000)\).

2. \(u\) \(A\) Mirko muốn biết lương của nhân viên \(A\).

Output

• In ra các câu trả lời của sựu kiện loại 2 theo thứ tự.

Sample Input

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

Sample Output

8
5