După ce FlaviuS a aflat într-un mod misterios că este ambidextru, acesta a definit o barcă de mărime $x$ ca fiind un șir de caractere care arată astfel:

De exemplu, o barcă de mărime $3$ arată așa: \\\___/// (_ apare de $3$ ori). FlaviuS a găsit pe lângă calitatea sa și un șir de $N$ caractere, $S$ format doar din caracterele \, _ și /. El își pune $Q$ întrebări de forma ($l$, $r$): Care este mărimea maximă a unei bărci care este un subșir al subsecvenței $S_l, S_{l+1} \dots, S_r$.

Un subșir se obține din alt șir prin ștergea elementelor și păstrarea ordinei acestora. De exemplu, \_ este un subșir al șirului \/_/, dar _\ nu este un subșir al șirului \/_/.

Date de intrare

Pe prima linie se găsesc două numere, $N$ și $Q$, reprezentând lungimea șirului, și numărul de întrebari pe care și le pune FlaviuS. Pe a doua linie se află șirul $S$. Următoarele $Q$ linii conțin câte două numere $l$ și $r$.

Date de ieșire

Pe linia $i$, $1 \leq i \leq Q$ se va afla un singur număr $x$, mărimea maximă a unei bărci.

Restricții și precizări

• $1 \leq N, Q \leq 10^6$
• $1 \leq l \leq r \leq N$ pentru fiecare întrebare
• Dacă la o interogare nu există nicio barcă în subsecvența aleasă, se va afișa $0$.

Exemplu

stdin

17 6
\_/\/_\___/_/\/_/
1 2
1 3
1 17
3 10
2 16
5 10

stdout

0
1
3
0
2
0

Explicație

La prima interogare, subsecvența este \_, așadar nu este nicio barcă.

La a doua interogare, subsecvența este \_/, așadar există o barcă de lungime $1$.

La a treia interogare, subsecvența este tot șirul. Există o barcă de lungime $3$ formată din caracterele de pe pozițiile $1, 4, 7, 8, 9, 10, 11, 13, 17$. O barcă de lungime $3$ arată astfel: \\\___///