Max on tree

Cho một cây có gốc có \(n\) đỉnh. Mỗi đỉnh có một mã định danh \(id\) và một trọng số \(w(id)\). Gốc của cây có định danh là \(r\). Có \(Q\) thao tác dạng:

• \(0\) \(p\) \(id\) \(w\): Thêm một đỉnh mới với định danh \(id\), trọng số \(w\) và nhận \(p\) làm nút cha;

• \(1\) \(id\) \(a\): Tìm \(min(a ∧ w)\) và \(max(a ∧ w)\) với \(w\) là trọng số của một đỉnh nào đó trên đường đi đơn từ \(id\) đến \(r\).

Input

• Dòng đầu ghi số đỉnh ban đầu và số thao tác: \(n\) \(Q\);

• Dòng thứ hai mô tả đỉnh gốc: \(r\) \(w(r)\);

• \(n − 1\) dòng tiếp theo, mỗi dòng mô tả một đỉnh của cây: \(id\) \(p\) \(w(id)\) là định danh, định danh của đỉnh cha, trọng số;

• \(Q\) dòng tiếp theo, mỗi dòng mô tả một thao tác, gồm \(3\) hoặc \(4\) số nguyên đã được mã hóa. Để giải mã, số \(s\) sẽ được thay bằng \(s ∧ premin ∧ premax\). Ở đây \(premin\), \(premax\) là kết quả trước đó hoặc \(0\) \(0\) nếu chưa có thao tác loại \(1\) nào.

Các định danh được đảm bảo khác nhau nhưng không nhất thiết tạo thành hoán vị của \([n]\). Dữ liệu đảm bảo hợp lệ.

Output

Với mỗi thao tác loại \(1\), in ra hai số trên một dòng.

Example

7 3
1 3
2 1 1
3 1 2
4 2 3
5 2 5
6 3 4
7 3 6
1 6 1
7 2 15 5
6 15 5

2 5
0 7

Scoring

• \(1 ≤ n, Q ≤ 10^5\); \(1 ≤ id, w, a < 2^{31}\);

• \(50\%\) số test có \(1 ≤ n, Q ≤ 5000\).