Dãy tổ tiên trên cây

Ban đầu ta có một cây chỉ gồm một đỉnh mang chỉ số $1$ và trọng số $0$. Gọi $cnt$ là số đỉnh hiện có của cây (ban đầu $cnt=1$). Cây luôn được coi là có gốc tại đỉnh $1$.

Hãy xử lý $Q$ truy vấn thuộc hai loại:

• Loại 1 (tham số $R$, $W$): thêm một đỉnh mới mang chỉ số $cnt+1$ với trọng số $W$, và nối một cạnh giữa đỉnh $R$ và đỉnh mới này.
• Loại 2 (tham số $R$, $X$): in ra độ dài lớn nhất của một dãy đỉnh $v_1,v_2,\dots ,v_k$ thoả mãn đồng thời:
  1. $v_1=R$;
  2. mỗi đỉnh trong dãy là tổ tiên của đỉnh đứng ngay trước nó, tức $v_{t+1}$ là tổ tiên của $v_t$;
  3. tổng trọng số các đỉnh trong dãy không vượt quá $X$;
  4. với mọi cặp đỉnh liên tiếp $v_t$ và $v_{t+1}$ ta có $w[v_{t+1}]\ge w[v_t]$, đồng thời không tồn tại đỉnh nào nằm thực sự giữa $v_t$ và $v_{t+1}$ trên đường đi đơn nối chúng mà có trọng số $\ge w[v_t]$.

Dãy rỗng ($k=0$) luôn hợp lệ, nên đáp án của truy vấn loại 2 có thể bằng $0$.

Các truy vấn được đưa ra ở dạng mã hoá. Gọi $last$ là đáp án của truy vấn loại 2 gần nhất đã in ra, ban đầu $last=0$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $Q$: số truy vấn.
• Mỗi dòng trong $Q$ dòng tiếp theo có dạng type p q:
  • 1 p q: truy vấn loại 1 với $R=p\oplus last$ và $W=q\oplus last$.
  • 2 p q: truy vấn loại 2 với $R=p\oplus last$ và $X=q\oplus last$.

Ở đây $\oplus$ là phép XOR trên bit.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra đáp án trên một dòng riêng.

Ràng buộc

• $1\le Q\le 400000$
• $0\le p,q\le {10}^{18}$
• Dữ liệu đảm bảo $1\le R\le cnt$, $0\le W\le {10}^9$ và $0\le X\le {10}^{15}$.
• Dữ liệu đảm bảo có ít nhất một truy vấn loại 2.

Ví dụ