Chuyển vàng

Có một cây có gốc. Mỗi đỉnh chứa một lượng vàng: đỉnh $i$ có $a_i$ tấn vàng với giá $c_i$ mỗi tấn. Ban đầu cây chỉ gồm một đỉnh gốc đánh số $0$, chứa $a_0$ tấn vàng giá $c_0$ mỗi tấn.

Có $q$ truy vấn, mỗi truy vấn thuộc một trong hai loại:

1. Thêm đỉnh $i$ (với $i$ là chỉ số của truy vấn) làm con của đỉnh $p_i$; đỉnh $i$ chứa $a_i$ tấn vàng giá $c_i$ mỗi tấn. Dữ liệu đảm bảo $c_i>c_{p_i}$.
2. Cho đỉnh $v_i$, xét đường đi đơn từ $v_i$ tới gốc. Ta cần mua $w_i$ tấn vàng từ các đỉnh trên đường đi này sao cho tổng số tiền phải trả là nhỏ nhất. Nếu tổng lượng vàng trên đường đi không đủ $w_i$ tấn, ta mua hết những gì có thể.

Khi mua $x$ tấn vàng ở một đỉnh, lượng vàng còn lại của đỉnh đó giảm đi $x$ (dĩ nhiên không thể mua nhiều hơn lượng vàng đỉnh đó đang có). Với mỗi truy vấn loại 2, hãy tính lượng vàng thực sự mua được và số tiền phải trả.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $q$, $a_0$, $c_0$.
• $q$ dòng tiếp theo, dòng thứ $i$ mô tả truy vấn thứ $i$:
  • "1 $p_i$ $a_i$ $c_i$": thêm đỉnh $i$ làm con của đỉnh $p_i$.
  • "2 $v_i$ $w_i$": mua $w_i$ tấn vàng trên đường đi từ $v_i$ tới gốc $0$.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra một dòng gồm hai số nguyên: lượng vàng mua được và số tiền tối thiểu phải trả.

Ràng buộc

• $1\le q\le 3·{10}^5$
• $1\le a_0,c_0<{10}^6$
• Với truy vấn loại 1: $0\le p_i<i$; $1\le a_i,c_i<{10}^6$; đảm bảo đỉnh $p_i$ tồn tại và $c_i>c_{p_i}$.
• Với truy vấn loại 2: $0\le v_i<i$; $1\le w_i<{10}^6$; đảm bảo đỉnh $v_i$ tồn tại.
• Dữ liệu đảm bảo có ít nhất một truy vấn loại 2.

Ví dụ