JOI decided to keep some fish.

He went to a pet shop near his house, where $N$ fish were for sale. The $i$-th fish has a length of $L_i$ cm and a color of either red, green, or blue. JOI decided to keep one or more of these $N$ fish at home.

There is something to be careful about when keeping fish. If you keep a large fish and a small fish together, the large fish will eat the small fish. Specifically, if the length of fish $X$ is at least twice the length of fish $Y$, then $X$ will eat $Y$ if they are kept together. Therefore, such a pair of fish cannot be kept together.

JOI is curious about how many possible combinations of colors of the fish he can keep. Two combinations of colors are considered different if the number of fish of at least one color (red, green, or blue) is different. Given the lengths and colors of the fish sold at the pet shop, he wants to find the number of possible combinations of colors of the fish he can keep.

Task

Given the lengths and colors of the fish sold at the pet shop, write a program that outputs the number of possible combinations of colors of the fish JOI can keep.

Constraints

• $1 \le N \le 500\,000$
• $1 \le L_i \le 1\,000\,000\,000$

Input

Read the following from standard input:

• The first line contains an integer $N$, representing the number of fish sold at the pet shop.
• The $(1+i)$-th line ($1 \le i \le N$) contains an integer $L_i$ and a character $C_i$ separated by a space. The character $C_i$ is one of 'R', 'G', or 'B'. This indicates that the $i$-th fish has a length of $L_i$ cm, and if $C_i$ is 'R', the color is red; if $C_i$ is 'G', the color is green; and if $C_i$ is 'B', the color is blue.

Output

Output the number of possible combinations of colors of the fish JOI can keep on a single line.

Subtasks

• 10% of the points are awarded for test cases where $N \le 100$.
• 30% of the points are awarded for test cases where $N \le 2000$.

Examples

Input 1

4
10 R
4 G
8 B
5 B

Output 1

6

Note 1

The 1st fish eats the 2nd fish, so they cannot be kept together. The same applies to the 1st and 4th fish, and the 2nd and 3rd fish. Therefore, the possible color combinations are: "1 red", "1 green", "1 blue", "1 red and 1 blue", "1 green and 1 blue", and "2 blue", for a total of 6 combinations.

Input 2

10
26 B
10 B
16 G
20 R
6 R
5 G
13 G
40 R
8 R
33 R

Output 2

13