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 \(1\) người quản lý trực tiếp (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 dụng 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.

Chú ý: Tại mọi thời điểm lương của một nhân viên là một số nguyên dương 32 bit (kiểu int trong C/C++, longint trong pascal).

Input

• Dòng đầu tiên ghi hai số nguyên dương \(N\) (\(N≤5 \times 10^5\)) và \(M\) (\(M\leq 5\times 10^5\)) 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ả \(M\) sự kiện lần lượt theo thời gian với một trong \(2\) loại
  • 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\) \((-10^4\leq X \leq 10^4)\).
  • Loại 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ự kiện loại 2 theo thứ tự

Example

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

8
5