Xâu đối xứng

Xâu đối xứng là xâu đọc từ trái sang phải hay từ phải sang trái là như nhau. Ví dụ "abba", "a", "aa" là các xâu đối xứng. "abca", "aab", "ab" không phải là xâu đối xứng.

Cho số nguyên dương \(n\) và một xâu \(S = S_1 S_2 S_3 \ldots S_n\) gồm các chữ cái latin thường. Ký hiệu \(Sub[l, r]\) là xâu con từ vị trí \(l\) tới \(r\) của \(S\). Ví dụ, với \(n = 10\); \(S\) = "abacdcabaa" ta có \(Sub[2,5]\) = "bacd", \(Sub[9,10]\) = "aa", ...

Yêu cầu: cho \(q\) truy vấn, mỗi truy vấn là \(2\) số nguyên dương \([l_i, r_i]\), hãy xác định xâu \(Sub[l_i, r_i]\) có phải là xâu đối xứng hay không?

Input

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương \(n, q\).

• Dòng thứ \(2\) chứa xâu \(S\).

• \(q\) dòng cuối, dòng thứ \(i\) chứa \(2\) số nguyên dương \(l_i, r_i\) (\(1 \le l_i \le r_i \le n\) với mọi \(i = 1, 2, 3, \ldots, n\)).

Ràng buộc:

• Subtask 1 (40% số điểm): \(n \le 1000\), \(q = 1\), \(l_1 = 1\), \(r_1 = n\).

• Subtask 2 (30% số điểm): \(n, q \le 1000\).

• Subtask 3 (30% số điểm): \(n, q \le 3 \times 10^5\).

Output

In ra \(q\) dòng, dòng thứ \(i\) ghi đáp án câu trả lời cho truy vấn thứ \(i\). Đưa ra \(1\) trong trường hợp xâu \(Sub[l_i, r_i]\) là xâu đối xứng, đưa ra \(0\) trong trường hợp ngược lại.

Example 1

Input:

5 1
abcba
1 5

Output:

1

Example 2

Input:

10 4
abacdcabaa
9 10
8 10
4 6
1 9

Output:

1
0
1
1

Note

Ví dụ 1: có \(1\) truy vấn, \(Sub[1,5]\) = "abcba" là xâu đối xứng.

Ví dụ 2: có \(4\) truy vấn:

• Truy vấn 1: \(Sub[9,10]\) = "aa" là xâu đối xứng.

• Truy vấn 2: \(Sub[8,10]\) = "baa" không là xâu đối xứng.

• Truy vấn 3: \(Sub[4,6]\) = "cdc" là xâu đối xứng.

• Truy vấn 4: \(Sub[1,9]\) = "abacdcaba" là xâu đối xứng.