Dãy tình yêu là dãy chỉ gồm hai ký tự < và 3. Khi áp dụng các phép biến đổi ma thuật lên dãy, các ký tự sẽ dần được thay thế bởi các "trái tim" (heart) - mỗi trái tim là một đối tượng có độ lớn (kích thước) là một số nguyên dương.

Quy tắc biến đổi ma thuật:

Các phép biến đổi sau được áp dụng liên tục và lặp lại cho đến khi không còn phép biến đổi nào có thể áp dụng. Ưu tiên áp dụng các phép biến đổi theo thứ tự từ trái sang phải trong dãy:

1. Tạo trái tim cơ bản: Nếu ký tự < đứng ngay liền trước ký tự 3, hai ký tự này sẽ biến thành một trái tim có độ lớn \(1\).

2. Gộp hai trái tim: Nếu hai trái tim đứng liền kề nhau (trái tim có độ lớn \(a\) đứng ngay trước trái tim có độ lớn \(b\)), chúng sẽ gộp thành một trái tim có độ lớn \(a + b\).

3. Mở rộng trái tim: Nếu một trái tim có độ lớn \(h\) có ký tự < đứng ngay liền trước và ký tự 3 đứng ngay liền sau (tức cấu trúc < [trái tim \(h\)] 3), ba phần tử này sẽ biến thành một trái tim có độ lớn \(h + 1\).

Kết quả cuối cùng: Sau khi không còn phép biến đổi nào có thể áp dụng, nếu dãy chỉ còn lại đúng một trái tim duy nhất, độ lớn của trái tim đó là kết quả. Nếu dãy còn lại nhiều hơn một phần tử (bao gồm ký tự hoặc nhiều trái tim), kết quả là \(0\).

Ví dụ chi tiết:

• <3 → trái tim độ lớn \(1\)
• <3<3 → <3 [tim 1] → [tim 1] [tim 1] → trái tim độ lớn \(2\)
• <<33 → < [tim 1] 3 → trái tim độ lớn \(2\)
• <<3<3<33 → < [tim 1] <3<33 → < [tim 1] < [tim 1] [tim 1] → < [tim 1] < [tim 2] → < [tim 1] [tim 2] < (không biến đổi thêm) → ... (tiếp tục) → trái tim độ lớn \(4\)

Bài toán:

Hân có thể xóa một số ký tự tùy ý (có thể không xóa ký tự nào) từ dãy ban đầu để tạo ra một dãy con (subsequence - giữ nguyên thứ tự tương đối của các ký tự còn lại). Sau đó áp dụng các phép biến đổi ma thuật lên dãy con này.

Mục tiêu: Tìm độ lớn lớn nhất của trái tim có thể tạo ra sau khi xóa và biến đổi.

Bạn phải trả lời \(Q\) truy vấn thuộc \(2\) loại sau:

• Loại 1: 1 l r - Với mỗi vị trí \(i\) trong đoạn \([l, r]\): nếu \(S_i =\) < thì gán \(S_i =\) 3, ngược lại gán \(S_i =\) < (đảo ký tự).

• Loại 2: 2 l r - Xét dãy con liên tiếp \(S[l..r]\) (từ vị trí \(l\) đến vị trí \(r\)). Hỏi độ lớn lớn nhất của trái tim mà Hân có thể tạo ra bằng cách chọn một dãy con (subsequence) từ \(S[l..r]\) và áp dụng các phép biến đổi ma thuật.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n \leq 10^{6}, 1 \leq q \leq 5 \times 10^{5})\) là độ dài xâu \(S\) và số lượng truy vấn.
• Dòng thứ hai chứa xâu \(S\) có độ dài \(n\), chỉ gồm các ký tự < và 3.
• \(Q\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(t\), \(l\) và \(r\) \((t \in \{1, 2\}, 1 \leq l \leq r \leq n)\) thể hiện một truy vấn.

Output

• Với mỗi truy vấn loại \(2\), in ra một số nguyên duy nhất là độ lớn của trái tim lớn nhất mà Hân có thể tạo ra từ dãy con của \(S[l..r]\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 5 \times 10^{3}\).
• Subtask \(2\) (\(20\%\) số điểm): \(q \leq 10\), không có truy vấn loại \(1\).
• Subtask \(3\) (\(20\%\) số điểm): Có tối đa \(10\) truy vấn loại \(2\).
• Subtask \(4\) (\(20\%\) số điểm): Không có truy vấn loại \(1\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

16 10
<3<3<3<<3<<<3<3<
1 2 13
2 2 16
1 14 16
1 5 16
2 2 8
2 1 13
2 2 14
2 1 16
1 5 14
2 1 14

10
4
8
8
10
12