Note: Giới hạn thời gian cho bài này là 4 giây và giới hạn bộ nhớ là 512MB.

Nông dân John có \(N\) \((2 \le N \le 2 \times 10^5)\) chiếc máy kéo, trong đó máy kéo thứ \(i\) chỉ có thể sử dụng trong khoảng thời gian \([l_i, r_i]\). Các khoảng thời gian của máy kéo có điểm đầu trái \(l_1 < l_2 < ... < l_n\) và điểm cuối phải \(r_1 \le r_2 \le ... \le r_n\). Một số máy kéo là đặc biệt.

Hai máy kéo \(i\) và \(j\) được gọi là kề nhau nếu \([l_i, r_i]\) và \([l_j, r_j]\) giao nhau. Nông dân John có thể chuyển từ một máy kéo sang bất kỳ máy kéo kề nhau nào. Một đường đi giữa hai máy kéo \(a\) và \(b\) bao gồm một chuỗi các lần chuyển, sao cho máy kéo đầu tiên trong chuỗi là \(a\), máy kéo cuối cùng là \(b\), và hai máy kéo liên tiếp trong chuỗi là kề nhau. Người ta đảm bảo rằng luôn có một đường đi giữa máy kéo \(1\) và máy kéo \(N\). Độ dài của một con đường là số lần chuyển (hoặc tương đương, số máy kéo trong đó trừ đi \(1\)).

Bạn được cho \(Q\) \((1 \le Q \le 2 \times 10^5)\) truy vấn, mỗi truy vấn chỉ định một cặp máy kéo \(a\) và \(b\) \((1 \le a < b \le N)\). Đối với mỗi truy vấn, hãy xuất ra hai số nguyên:

• Độ dài của đường đi ngắn nhất giữa máy kéo \(a\) và máy kéo \(b\).
• Số lượng máy kéo đặc biệt sao cho tồn tại ít nhất một đường đi ngắn nhất từ máy kéo \(a\) đến máy kéo \(b\) đi qua máy kéo đó.

Input

• Dòng đầu tiên là số \(N\) và \(Q\)
• Dòng thứ hai là xâu kí tự có độ dài \(2N\) chỉ bao gồm kí tự \('L'\) và \('R'\), biểu diễn cho thời điểm bắt đầu và kết thúc được xếp theo thứ tự. Với mọi tiền tố của xâu số lượng kí tự \('R'\) không vượt quá số lượng kí tự \('L'\), số lượng hai kí tự xuất hiện trong xâu bằng nhau. Vị trí của kí tự \('L'\) thứ \(i\) là biểu diễn cho thời gian máy thứ \(i\) có thể sử dụng, và vị trí của kí tự \('R'\) thứ \(i\) là biểu diễn cho thời gian máy thứ \(i\) không được sử dụng nữa.
• Dòng tiếp theo là xâu nhị phân đồ dài \(N\) thể hiện các máy kéo đặc biệt, \(s_i = 1\) nếu máy kéo thứ \(i\) là đặc biệt, và ngược lại.
• \(Q\) dòng tiếp theo gồm \(2\) số \(a\) và \(b\) thể hiện các truy vấn.

Output

• Gồm \(Q\) dòng, mỗi dòng là \(2\) số là đáp án của các truy vấn in theo thứ tự trong đề bài.

Scoring

• Subtask \(1\): \(N, Q \le 5000\).
• Subtask \(2\): Có tối đa \(10\) máy kéo đặc biệt.
• Subtask \(3\): Không có ràng buộc gì thêm

8 10
LLLLRLLLLRRRRRRR
11011010
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5

1 2
1 1
1 2
2 4
2 3
2 4
2 3
1 1
1 2
1 2