"Chào mừng đến với BUỔI DIỄN! Các bạn sắp được chứng kiến màn ảo thuật ngoạn mục đầu tiên của pháp sư Ivor." Đó là cách Ivor tưởng tượng lời giới thiệu cho tiết mục đầu tiên của mình. Nhưng trước hết, cậu cần chuẩn bị.

Ivor sẽ mời ~n~ tình nguyện viên và xếp họ thành một hàng trên sân khấu. Ở đầu bên trái là người ~1~, bên phải người ~1~ là người ~2~, bên phải người ~2~ là người ~3~, v.v.

Mỗi trò ảo thuật mà Ivor học được có dạng ~l~ ~r~ ~len~. Với một trò như vậy, Ivor có thể đổi chỗ hai đoạn rời nhau có cùng độ dài: đoạn ~[l, l+len-1]~ và đoạn ~[r, r+len-1]~. Hai đoạn được gọi là rời nhau nếu chúng không có tình nguyện viên nào chung.

Ivor thường tự hỏi: với một người cho trước có số hiệu ~x~, vị trí nhỏ nhất và lớn nhất mà người đó có thể đứng là bao nhiêu, nếu Ivor được phép dùng các trò đã học theo bất kỳ thứ tự nào và lặp lại bao nhiêu lần tùy ý? Cậu cũng không bắt buộc phải dùng hết tất cả các trò đã học.

Có ~q~ sự kiện mô tả quá trình chuẩn bị của Ivor, gồm hai loại:

• Sự kiện dạng ~1~ ~x~: hãy trả lời câu hỏi của Ivor dựa trên các trò mà cậu đã học tới thời điểm đó.
• Sự kiện dạng ~2~ ~l~ ~r~ ~len~: Ivor vừa học thêm một trò mới.

Nhiệm vụ của bạn là giúp Ivor và trả lời tất cả các sự kiện loại thứ nhất.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~.

Mỗi trong ~q~ dòng tiếp theo mô tả một sự kiện theo một trong hai dạng sau:

• ~1~ ~x~: hỏi vị trí nhỏ nhất và lớn nhất mà người ~x~ có thể đứng.
• ~2~ ~l~ ~r~ ~len~: thêm phép đổi chỗ hai đoạn ~[l, l+len-1]~ và ~[r, r+len-1]~.

Output

Sau mỗi sự kiện loại ~1~, in ra hai số là vị trí nhỏ nhất và vị trí lớn nhất mà người được hỏi có thể đứng, cách nhau bởi một dấu cách.

Ràng buộc

• ~1 \le n, q \le 2 \cdot 10^5~
• Với truy vấn loại ~1~: ~1 \le x \le n~
• Với truy vấn loại ~2~: ~1 \le len \le n~
• Với truy vấn loại ~2~: ~l + len - 1 < r~
• Với truy vấn loại ~2~: ~r + len - 1 \le n~

Chấm điểm

• Subtask 1 (9 điểm): ~n, q \le 5~
• Subtask 2 (14 điểm): ~n, q \le 15~
• Subtask 3 (22 điểm): ~n, q \le 1000~
• Subtask 4 (11 điểm): ~n \le 4000~
• Subtask 5 (17 điểm): ~n \le 10000~
• Subtask 6 (37 điểm): Không có ràng buộc bổ sung.

Sample Input 1

5 3
2 3 4 1
1 5
1 3

Sample Output 1

5 5
3 4

Sample Input 2

9 2
2 1 7 2
1 2

Sample Output 2

2 8

Giải thích

• Ví dụ 2: Ivor đã học phép đổi chỗ hai đoạn ~[1, 2]~ và ~[7, 8]~. Vì vậy vị trí nhỏ nhất mà người ~2~ có thể đứng là ~2~, còn vị trí lớn nhất là ~8~.