34348번 - snupc 문자열 (Easy)

문제

알파벳 s,n,u,p,c로만 이루어진 문자열 $S$가 주어진다.

$f(1)=$ snupc, $f(2)=$ ssnnuuppcc와 같이 $f(k)$를 s,n,u,p,c 각 $k$개가 순서대로 연속하여 이어진 문자열로 정의하자. $f(0)$은 빈 문자열을 의미한다.

$Q$개의 쿼리가 주어질 때, 다음을 처리하는 프로그램을 작성하라.

• $l$ $r$: $S$의 $l$번째 문자부터 $r$번째 문자까지를 이은 새로운 문자열에 대해, $f(k)$가 부분 수열(Subsequence)로 등장하도록 하는 $k$의 최댓값을 출력한다.

문자열의 부분 수열이란, 원래 문자열에서 0ドル$개 이상의 문자를 제거하여 얻을 수 있는 문자열을 말한다. 단, 남은 문자의 순서는 바꿀 수 없으며, 연속할 필요는 없다. 예를 들어 abcde의 부분 수열은 ace,bd,a,abcde, 빈 문자열 등이 해당한다.

입력

첫째 줄에 문자열 $S$가 주어진다. $(1 \le |S| \le 100,000円)$

둘째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \le Q \le 5,000円)$

셋째 줄부터 $Q$개의 줄에 걸쳐, 쿼리에 대한 정보 $l,ドル $r$이 공백으로 구분되어 주어진다. $(1 \le l \le r \le |S|)$

입력으로 주어지는 모든 수는 정수이다.

출력

각 쿼리에 대한 결과를 한 줄에 하나씩 출력한다.

제한

힌트