Dominik rất thích chơi với những khối lập phương đỏ và xanh có kích thước khác nhau.

Cậu quyết định xây các tòa tháp theo hai quy tắc đặc biệt:

• Một khối nằm ngay trên một khối khác thì không được cùng màu với khối bên dưới nó.
• Mọi khối nằm phía trên một khối nào đó đều phải có kích thước nhỏ hơn khối đó.

Dominik mở hộp đồ chơi của mình, trong đó có đúng ~n~ khối lập phương. Với mỗi ~i~ từ ~1~ tới ~n~, cậu có đúng ~1~ khối kích thước ~i~, và khối đó mang một trong hai màu đỏ hoặc xanh.

Sau một lúc thì Dominik chán xây tháp và nghĩ ra ~q~ câu hỏi. Trong câu hỏi thứ ~j~, cậu cho hai số ~l~ và ~r~ rồi muốn biết số tòa tháp ít nhất cần dựng sao cho:

• chỉ sử dụng các khối có kích thước từ ~l~ tới ~r~,
• mọi tòa tháp đều tuân theo hai quy tắc ở trên,
• mỗi khối có kích thước nằm trong đoạn ~[l, r]~ đều phải được dùng đúng một lần.

Hãy giúp Dominik trả lời các câu hỏi đó.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~, với ~1 \le n, q \le 10^5~.

Dòng thứ hai chứa một xâu ~s~, trong đó ký tự ~s_i~ biểu diễn màu của khối có kích thước ~i~. Mỗi ký tự của xâu là ~\texttt{P}~ hoặc ~\texttt{C}~.

~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l_i~ và ~r_i~, với ~1 \le l_i \le r_i \le n~.

Output

In ra ~q~ dòng, mỗi dòng là đáp án cho một truy vấn tương ứng.

Chấm điểm

• Subtask ~1~ (~23~ điểm): ~1 \le n, q \le 10~
• Subtask ~2~ (~38~ điểm): ~1 \le n, q \le 1000~
• Subtask ~3~ (~25~ điểm): Có nhiều nhất ~20~ khối màu xanh.
• Subtask ~4~ (~24~ điểm): Không có ràng buộc bổ sung.

Sample Input ~1~

7 4
PPCPPCC
1 7
1 5
3 7
4 5

Sample Output ~1~

3
3
2
2

Sample Input ~2~

6 2
CCCCCC
1 6
2 5

Sample Output ~2~

6
4

Sample Input ~3~

16 1
PPPCPCCCCCCPPPPP
1 16

Sample Output ~3~

6

Giải thích

• Ví dụ ~2~: Tất cả các khối đều cùng màu, nên bất kỳ tòa tháp nào chứa từ ~2~ khối trở lên đều vi phạm quy tắc. Vì vậy mỗi tòa tháp chỉ có đúng ~1~ khối, và đáp án cho mỗi truy vấn đơn giản là số lượng kích thước trong đoạn hỏi, tức ~r - l + 1~.