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

Alice xây dựng trò chơi trên bàn có kích thước ~m \times n~. Một số ô trên bàn được đánh dấu là ô cấm (là ô không thể di chuyển vào), những ô còn lại là ô tự do (là ô có thể di chuyển vào). Khi bắt đầu chơi, Alice sẽ đặt một số quân mã hoặc quân tốt vào các ô tự do, mỗi ô đặt không quá một quân.

Nhiệm vụ của người chơi là tìm cách di chuyển tất cả các quân về cùng một ô. Độ khó của trò chơi là trên bàn có hỗn hợp nhiều quân và tại mỗi đơn vị thời gian tất cả các quân đều cùng phải di chuyển theo quy tắc (xem hình minh họa bên dưới mô tả quy tắc di chuyển). Trong quá trình di chuyển một ô có thể chứa nhiều quân, các quân có thể đi lại những ô đã đi nhưng không quân nào được đi vào ô cấm.

Yêu cầu: Hãy giúp Alice tính thời gian ít nhất để có thể di chuyển tất cả các quân về cùng một ô.

INPUT

Dòng đầu chứa hai số nguyên dương ~m~, ~n~ (~m \times n \le 2000~).

~m~ dòng tiếp theo, mỗi dòng chứa một xâu gồm ~n~ kí tự, trong đó:

• Kí tự ~.~ thể hiện ô trống (ô tự do),

• Kí tự ~\#~ thể hiện ô cấm (không được phép đi vào),

• Kí tự ~T~ thể hiện vị trí một quân tốt,

• Kí tự ~M~ thể hiện vị trí một quân mã.

OUTPUT

In ra một số ~t~ là thời gian ít nhất để di chuyển các quân về cùng một ô. Nếu không có cách di chuyển thỏa mãn, ghi ~-1~.

SAMPLE INPUT 1

2 5
M..T.
.....

SAMPLE OUTPUT 1

1

Giải thích: Có thể di chuyển các quân về ô ở hàng ~2~, cột ~3~.

SAMPLE INPUT 2

2 5
M...T
..#..

SAMPLE OUTPUT 2

-1

Giải thích: Mỗi đơn vị thời gian tất cả các quân đều phải di chuyển nhưng quân mã không thể di chuyển, do đó không tồn tại phương án di chuyển thỏa mãn.

SAMPLE INPUT 3

5 5
.....
M...M
.#...
.#..#
T..#T

SAMPLE OUTPUT 3

3

Giải thích: Có thể di chuyển các ô về hàng ~4~, cột ~4~.

SUBTASKS

Công ty của Alice có ~n~ nhân viên được tổ chức vào ~m~ phòng ban. Nhân viên ~i~ (~1 ≤ i ≤ n~) đang thuộc phòng ban ~d_i~, mỗi phòng ban có ít nhất ~2~ người.

Có ~s~ sự phản đối, sự phản đối thứ ~k~ là ~i_k, j_k~ cho biết nhân viên ~i_k~ phản đổi nhân viên ~j_k~. Một lần sắp xếp lại nhân sự, lãnh đạo công ty sẽ chọn từ mỗi phòng ban một nhân viên và chuyển nhân viên đó sang phòng ban khác, mỗi phòng ban sau khi chuyển một nhân viên đi sẽ chỉ nhận lại một nhân viên. Nhân viên ~i~ có thể xếp vào phòng ban ~d~, nếu những người ở lại phòng ban ~d~ phản đối nhân viên ~i~ không quá bán (cụ thể, nếu còn lại ~x~ người thì số người phản đối nhỏ hơn hoặc bằng ~\frac {x}{2}~).

Yêu cầu: Đếm số lượng cách sắp xếp nhân sự.

INPUT

Dòng đầu chứa ba số nguyên không âm ~n~, ~m~, ~s~ (~1 \le n \le 200~, ~1 \le m \le 10~, ~s \le \frac {n \times (n - 1)}{2}~).

Dòng thứ hai gồm ~n~ số nguyên ~d_1, d_2, ..., d_n~ (~1 \le d_i \le m~).

Dòng thứ ~k~ (~1 ≤ k ≤ s~) trong ~s~ dòng sau chứa hai số nguyên ~i_k, j_k~.

OUTPUT

Số cách sắp xếp, chia dư cho ~10^9 + 7~.

SAMPLE INPUT 1

4 2 0
1 1 2 2

SAMPLE OUTPUT 1

4

SAMPLE INPUT 2

4 2 1
1 1 2 2
3 1

SAMPLE OUTPUT 2

3

SUBTASKS