문제

어떤 문자열의 베개도(pillowity)는, 그 문자열에 연속된 형태로 포함된 PLW 부분 문자열의 개수로 정의된다.

예를 들어, PLWPLWPLWPPLLWW의 베개도는 이다.

길이 의 문자열 가 주어진다. 이 문자열에 대해, 다음 쿼리를 처리하는 프로그램을 작성하라.

• l r: 의 부분 문자열 에서, (번째와 번째 문자를 포함한다) P, L, W 이외의 문자를 모두 제거하여 만들어지는 문자열의 베개도를 구해 출력한다.

입력

첫 번째 줄에 문자열의 길이 과 쿼리의 개수 가 주어진다. ,

두 번째 줄의 길이 의 문자열 가 주어진다. 는 알파벳 대문자로만 이루어져 있다.

세 번째 줄부터 개의 줄에 걸쳐, 각 줄마다 쿼리가 주어진다.

출력

쿼리가 주어질 때마다, 한 줄에 하나씩 쿼리의 답을 출력한다.