Có một lưới ô vuông vô hạn về phía trái, phải và lên trên (tất cả các ô có tọa độ $(x, y)$ với $x \in \mathbb{Z}, y \geq 0$ đều tồn tại). Ban đầu tất cả các ô đều màu trắng. Bạn cần xử lý $q$ truy vấn thuộc hai loại:

1. $y_i$ $l_i$ $r_i$: tô đen tất cả các ô $(x, y_i)$ với $l_i \leq x \leq r_i$. Nếu ô đó đã màu đen, màu của nó không thay đổi.
2. $l_i$ $r_i$: xét tất cả các ô có tọa độ $x$ nằm trong đoạn $[l_i, r_i]$. Tìm ô cao nhất sao cho tất cả các ô nằm ngay bên dưới nó đều là màu đen. Nói cách khác, bạn cần tìm $h$ lớn nhất sao cho $\exists x \in [l_i, r_i] \forall y \in [0, h)$ ô $(x, y)$ là màu đen.

Để bắt buộc xử lý các truy vấn trực tuyến (online), chúng được mã hóa bằng các câu trả lời trước đó.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $q$ ($1 \leq q \leq 10^5$) — số lượng truy vấn cần xử lý.

$q$ dòng tiếp theo chứa mô tả các truy vấn đã được mã hóa. Gọi $S$ là tổng các câu trả lời cho tất cả các truy vấn loại hai đã được xử lý cho đến thời điểm hiện tại.

Mỗi mô tả được định dạng là “1 $(y_i \oplus S)$ $(l_i \oplus S)$ $(r_i \oplus S)$” hoặc “2 $(l_i \oplus S)$ $(r_i \oplus S)$”. Đảm bảo rằng $0 \leq y_i \leq 2 \cdot 10^5$, $0 \leq l_i \leq r_i \leq 2 \cdot 10^5$. Lưu ý rằng các đảm bảo này được đưa ra trên các tham số sau khi giải mã, các số trong dữ liệu vào có thể không nằm trong phạm vi số nguyên 32-bit.

Đừng quên cộng câu trả lời mới vào $S$ sau mỗi truy vấn loại hai.

Dữ liệu ra

In ra câu trả lời cho tất cả các truy vấn loại hai trên các dòng riêng biệt.

Ví dụ

Dữ liệu vào 1

10
1 0 1 1
2 0 10
1 1 9 9
1 0 0 6
1 0 3 9
2 5 5
1 1 5 5
2 5 5
2 0 5
1 7 6 3

Dữ liệu ra 1

1
0
2
2

Ghi chú

Figure 1. Visualization of the grid operations