Một công ty có \(n\) người đánh số từ \(1\) tới \(n\), người thứ \(i\) có lương là \(w_i\) (\(w_i \leq 10^{18}\)). Tổng giám đốc công ty được đánh số \(1\), từ người thứ \(2\) tới \(n\) có đúng \(1\) thủ trưởng trực tiếp của mình. Tại ngày \(i\) quản lý người \(j\) nếu tồn tại dãy \(i = x_1, x_2, ..., x_k = j\) sao cho người \(x_l\) là thủ trưởng trực tiếp của người \(x_{l+1}\). Cơ cấu tổ chức đảm bảo rằng không tồn tại hai người \(a, b\) mà người \(a\) quản lý người \(b\) đồng thời người \(b\) quản lý người \(a\).

Mỗi người được quyền tăng/giảm lương của tất cả mọi người trong quyền quản lý của mình. Bạn cần viết một chương trình quản lý lương xử lý hai tác vụ:

• p A x: Người A tăng lương của tất cả những người trong quyền quản lý của mình thêm x đồng (x có thể âm, \(-10^9 \leq x \leq 10^9\))
• u A: Cho biết lương của người A

Input

• Dòng 1: Chứa hai số nguyên dương \(n, m \leq 10^5\) trong đó \(m\) là số tác vụ
• \(n\) dòng tiếp, dòng \(i\) chứa lương khởi điểm và số hiệu thủ trưởng của người \(i\). Riêng với người 1, dòng lương ứng sẽ chỉ có lương khởi điểm
• \(m\) dòng tiếp, mỗi dòng chứa một tác vụ

Output

• Với mỗi tác vụ loại u, in ra kết quả trên một dòng

Example

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

7
9
7
5