Có \(n\) người đứng ở các vị trí \(1\) đến \(n\). Ivor dần học các phép đổi chỗ hai đoạn rời nhau cùng độ dài: phép \((l,r,\text{len})\) đổi đồng thời hai đoạn \([l,l+\text{len}-1]\) và \([r,r+\text{len}-1]\). Sau mỗi phép đã học, có thể dùng các phép đã biết với thứ tự bất kỳ, số lần bất kỳ, và không bắt buộc dùng hết. Sự kiện 1 x hỏi vị trí nhỏ nhất và lớn nhất mà người \(x\) có thể đứng; sự kiện 2 l r len thêm một phép đổi chỗ.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n,q\le2\cdot10^5\)). Mỗi sự kiện là 1 x (\(1\le x\le n\)) hoặc 2 l r len, trong đó \(1\le\text{len}\le n\), \(l+\text{len}-1<r\), và \(r+\text{len}-1\le n\).

Dữ liệu ra

Với mỗi sự kiện loại 1, in vị trí nhỏ nhất và lớn nhất của người được hỏi.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(9\) điểm: \(n,q\le5\).
2. \(14\) điểm: \(n,q\le15\).
3. \(22\) điểm: \(n,q\le1000\).
4. \(11\) điểm: \(n\le4000\).
5. \(17\) điểm: \(n\le10000\).
6. \(37\) điểm: không có ràng buộc thêm.

Ví dụ

5 3
2 3 4 1
1 5
1 3

5 5
3 4

9 2
2 1 7 2
1 2

2 8

Nguồn

COCI 2025/2026 - Vòng 4, bài Magija.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.