A. Monster Battle
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Monsters are magical creatures endowed with special powers, and they like to battle each other. Each Monster is of one of three types: Fire, Water or Grass. When two Monsters battle each other, one of them will win according to the following rules:

  • A Fire Monster will always defeat a Grass Monster.
  • A Water Monster will always defeat a Fire Monster.
  • A Grass Monster will always defeat a Water Monster.
  • If two Monsters of the same type battle each other, it is possible for either one of them to win.

There are $$$N$$$ Monsters numbered $$$1 \ldots N$$$. You are given the type of each Monster $$$i$$$. You wish to perform $$$Q$$$ operations, where the $$$j$$$-th operation is the following:

  • Consider that the Monster $$$L_j \ldots R_j$$$ (where $$$1 \leq L_j \leq R_j \leq N$$$) are standing in a line from left to right, in order of number. Two Monsters are considered adjacent if there is no Monster standing between them. Any two adjacent Monster may battle each other, and the Monster who loses the battle will leave the line. (Notice that this may cause two Monster in the line to start being adjacent.)

    Eventually, after some number of battles, there will only be one Monster remaining. You wish to find the number of Monster who could be the last remaining Monster. That is, you wish to count the number of Monster $$$i$$$ such that there is at least one valid sequence of battles and outcomes of battles by which $$$i$$$ is the last remaining Monster.

Input

The first line contains a single integer $$$N$$$, the number of Monster.

The second line contains a string $$$A$$$ of $$$N$$$ characters without spaces, where the $$$i$$$-th character is F, W, or G, depending on whether the $$$i$$$-th Monster is Fire type, Water type, or Grass type, respectively.

The third line contains a single integer $$$Q$$$, the number of operations to be performed.

The next $$$Q$$$ lines describe these operations. The $$$j$$$-th of these lines contains two space-separated integers $$$L_j$$$ and $$$R_j$$$, which have the meaning explained above.

Output

You should print $$$Q$$$ lines of output. The $$$j$$$-th of these lines should consist of a single integer, which is the number of Monster that could be the last remaining Monster in operation $$$j$$$.

Scoring

The test data for this problem is divided into multiple subtasks. In order to pass a subtask, your submitted program must solve every test case within that subtask correctly and within the time and memory limits.

You will be awarded the points allocated to a subtask if at least one submission you make during the contest passes that subtask. You do not need to combine your solutions for multiple subtasks into a single submission.

Please keep in mind that the subtasks are not necessarily arranged in increasing order of difficulty. We encourage you to try as many subtasks as possible.

Constraints

In all test data, it is guaranteed that:

  • $$$1 \leq N \leq 100\:000$$$.
  • $$$A_i =$$$ F, W, or G for all $$$1 \leq i \leq N$$$.
  • $$$1 \leq Q \leq 100\:000$$$.
  • $$$1 \leq L_j \leq R_j \leq N$$$, for all $$$1 \leq j \leq Q$$$.

Subtasks

Constraint for Subtasks 1-9

You only have to perform one operation, and this operation covers all the Monster. In other words, $$$Q = 1$$$, $$$L_1=1$$$, $$$R_1=N$$$.

  • Subtask 1 (4 points) There are only Fire Monster.
  • Subtask 2 (5 points) There are no Grass Monster.
  • Subtask 3 (6 points) $$$N = 3$$$.
  • Subtask 4 (6 points) $$$N \leq 35$$$. Further, there are at most $$$2$$$ pairs of adjacent Monster who are of different types.
  • Subtask 5 (7 points) $$$N \leq 35$$$.
  • Subtask 6 (7 points) $$$N \leq 80$$$.
  • Subtask 7 (14 points) $$$N \leq 400$$$.
  • Subtask 8 (13 points) $$$N \leq 1500$$$.
  • Subtask 9 (16 points) $$$N \leq 10^5$$$.

Constraint for Subtasks 10-11

There may be multiple operations.

  • Subtask 10 (6 points) There are no Grass Monsters.
  • Subtask 11 (16 points) No additional constraints.
Examples
Input
7
FFWGWFG
2
1 2
2 4
Output
2
2
Input
5
FWGFW
1
1 5
Output
4
Input
35
FWFWFWWWFWWFWWFFWFWWFWWWWFWFWWWFWWW
1
1 35
Output
23
Note

Example 1

In this example, there are two operations.

  • Consider the first operation. Initially, the line contains Monster $$$[1, 2]$$$. Both of them are Fire type, so in a battle between them, it is possible for either one to win. Therefore, both Monster $$$1$$$ and $$$2$$$ can be the last remaining Monster and the answer is $$$2$$$.
  • Consider the second operation. Here, the line initially contains Monster $$$[2, 3, 4]$$$, and they have types Fire, Water and Grass respectively. It is possible for Monster $$$2$$$ and $$$4$$$ to be the last remaining Monster, so the answer is $$$2$$$.

    Here is one possible sequence of battles by which Monster $$$2$$$ can be the last remaining Monster:

    • Initially, the line contains all the Monster $$$[2, 3, 4]$$$. Monster $$$3$$$ and Monster $$$4$$$ can battle. As Monster $$$3$$$ is of Water type and Monster $$$4$$$ is of Grass type, Monster $$$4$$$ will win and Monster $$$3$$$ will leave the line.
    • Now, the remaining Monster in the line are $$$[2, 4]$$$. Monster $$$2$$$ and Monster $$$4$$$ can battle. As Monster $$$2$$$ is of Fire type and Monster $$$4$$$ is of Grass type, Monster $$$2$$$ will win and Monster $$$4$$$ will leave the line.
    • Monster $$$2$$$ is the last remaining Monster.

    Here is one possible sequence of battles by which Monster $$$4$$$ can be the last remaining Monster:

    • Initially, the line contains all the Monster $$$[2, 3, 4]$$$. Monster $$$2$$$ and Monster $$$3$$$ can battle. As Monster $$$2$$$ is of Fire type and Monster $$$3$$$ is of Water type, Monster $$$3$$$ will win and Monster $$$2$$$ will leave the line.
    • Now, the remaining Monster in the line are $$$[3, 4]$$$. Monster $$$3$$$ and Monster $$$4$$$ can battle. As Monster $$$3$$$ is of Water type and Monster $$$4$$$ is of Grass type, Monster $$$4$$$ will win and Monster $$$3$$$ will leave the line.
    • Monster $$$4$$$ is the last remaining Monster.

    There is no such sequence of battles by which Monster $$$3$$$ can be the last remaining Monster.

This example is valid for subtask 11.

Example 2

In this example, there is only one operation which covers all the Monster. It is possible for the Monster $$$1$$$, $$$2$$$, $$$3$$$ and $$$5$$$ to be the last remaining Monster, so the answer is $$$4$$$.

Here is one possible sequence of battles by which Monster $$$1$$$ is the last remaining Monster:

  • Initially, the line contains all the Monster $$$[1, 2, 3, 4, 5]$$$. Monster $$$3$$$ and Monster $$$2$$$ can battle. As Monster $$$3$$$ is of Grass type and Monster $$$2$$$ is of Water type, Monster $$$3$$$ will win and Monster $$$2$$$ will leave the line.
  • Now, the remaining Monster in the line are $$$[1, 3, 4, 5]$$$. Monster $$$4$$$ and Monster $$$5$$$ can battle. As Monster $$$4$$$ is of Fire type and Monster $$$5$$$ is of Water type, Monster $$$5$$$ will win and Monster $$$4$$$ will leave the line.
  • Now, the remaining Monster in the line are $$$[1, 3, 5]$$$. Monster $$$3$$$ and Monster $$$5$$$ can battle. As Monster $$$3$$$ is of Grass type and Monster $$$5$$$ is of Water type, Monster $$$3$$$ will win and Monster $$$5$$$ will leave the line.
  • Now, the remaining Monster in the line are $$$[1, 3]$$$. Monster $$$1$$$ and Monster $$$3$$$ can battle. As Monster $$$1$$$ is of Fire type and Monster $$$3$$$ is of Grass type, Monster $$$1$$$ will win and Monster $$$3$$$ will leave the line.
  • Monster $$$1$$$ is the last remaining Monster.

Similar to this, for each Monster $$$2$$$, $$$3$$$ or $$$5$$$ it is possible to find such a sequence of battles and outcomes of battles such that that Monster will be the last remaining Monster. For Monster $$$4$$$, it is impossible to find such a sequence.

This example is valid for subtasks 5, 6, 7, 8, 9 and 11.

Example 3

This example is valid for subtasks 2, 5, 6, 7, 8, 9, 10 and 11.