Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Description

Given a string (indexed from $1$) and $q$ queries, each query asks for the count of characters $\tt{l,u,o,g,uu}$ in the interval $[x,y]$ of the string.

Input Format

• The first line contains a string $s$.
• The second line contains an integer $q$.
• The next $q$ lines: Each line contains two space-separated integers $x$ and $y$.

Output Format

Output $q$ lines, each containing $5$ numbers representing the counts of $\tt{l,u,o,g,uu}$ respectively.

Samples

llouugulouugol
5
1 9
1 9
8 10
1 14
5 14

3 3 2 1 1
3 3 2 1 1
1 1 1 0 0
4 5 3 2 2
2 4 2 2 1

Data Range

• For $10\%$ of the data, $1\le q,|s|\le20$.
• For $90\%$ of the data, $q=|s|=10^6$.
• The string contains only the letters $\tt{l,u,o,g,u}$.
• It is guaranteed that $1 \le x \le y \le |s|$.