Giải bài trực tuyến

Hồi còn bé sherry thường chơi với bố 1 trò chơi có tên gọi là White Black :D

Bố có 1 mảnh giấy HCN thật dài cỡ 1 x N chia thành N ô vuông bé dàn thành hàng ngang. Ban đầu ô vuông nào cũng có màu trắng. Quy tắc chơi sẽ là mỗi bước bố có thể tô màu 1 đoạn các ô vuông từ ô L đến ô R cùng 1 màu ( có thể là màu đen hoạc màu trắng ) 1 lúc sau tờ giấy sẽ có rất nhiều ô đen trắng đan xen nhau và câu hỏi của bố dành cho sherry là có bao nhiêu ô vuông màu trắng liên tiếp ( sao cho số lượng các ô này là nhiều nhất )

sherry cũng thông minh lắm nên hôm nào cũng thắng ( tuy nhiên sherry chơi hơi chậm 1 chút ^^ ) Sao bạn không thử tham gia trò chơi này nhỉ :D

Input

Dòng 1: N (1 <= N <= 10000)

Dòng 2: M (1 <= M <= 100000) ( tổng số lần tô màu và số lần bố đố sherry )

M dòng tiếp theo: Mỗi dòng có dạng:

1 L R (1 <= L <= R <= N) tô các ô vuông từ L -> R màu trắng

2 L R (1 <= L <= R <= N) tô các ô vuông từ L -> R màu đen

3 đếm số lượng ô màu trắng liên tiếp dài nhất

Output

Gồm 1 số dòng tương ứng với các câu trả lời của sherry cho câu hỏi của bố

Example

Input:
6
7
2 1 2
2 4 5
3
1 3 4
3
1 1 1
3

Output:
1
2
2