Alice định nghĩa một xâu kí tự được gọi là mật khẩu "an toàn" nếu xâu có độ dài ít nhất bằng 6 và xâu chứa ít nhất một chữ cái in hoa (A..Z), một chữ cái in thường (a..z), một chữ số (0..9).

Ví dụ: a1B2C3, tinHoc6 là hai mật khẩu "an toàn", còn a1B2C, a1b2c3, A1B2C3, tinHoc đều không phải là mật khẩu "an toàn".

Alice có một xâu kí tự ~S~ độ dài ~n~ và cần thực hiện ~q~ thao tác, mỗi thao tác thuộc một trong hai loại sau:

• Thao tác loại 1 có dạng: ~1~ ~i~ ~j~, trong đó ~1 ≤ i, j ≤ n~, sẽ thực hiện tráo hai kí tự ở vị trí thứ ~i~ và thứ ~j~ cho nhau;

• Thao tác loại 2 có dạng: ~2~ ~l~ ~r~, trong đó ~1 ≤ l ≤ r ≤ n~, yêu cầu kiểm tra xâu con của xâu ~S~ gồm các kí tự liên tiếp từ ~l~ đến ~r~ có phải là một mật khẩu "an toàn" hay không.

Yêu cầu: Cho xâu ~S~ và ~q~ thao tác, hãy giúp Alice thực hiện các thao tác trên xâu ~S~.

INPUT

Dòng đầu tiên chứa hai số nguyên dương ~n, q~ (~n, q ≤ 3 \times 10^5~);

Dòng thứ hai chứa một xâu độ dài ~n~, mỗi kí tự là chữ cái in hoa (A..Z) hoặc chữ cái in thường (a..z) hoặc chữ số (0..9);

Dòng thứ ~t~ (~1 ≤ t ≤ q~) trong ~q~ dòng tiếp theo chứa ba số nguyên mô tả thao tác.

OUTPUT

In ra một số dòng ứng với thao tác loại 2, ghi số ~1~ nếu xâu con tương ứng là mật khẩu "an toàn", ngược lại ghi số ~0~.

SAMPLE INPUT

10 5
Abba123456
2 1 10
2 1 5
2 2 10
1 1 5
2 2 10

SAMPLE OUTPUT

1
0
0
1

SUBTASKS