H. Triangles
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ distinct lines in the plane. Each of them is either horizontal ($$$y=c$$$), vertical ($$$x=c$$$) or diagonal ($$$x+y=c$$$). You need to find the number of non-degenerate triangles such that each of their sides lies on some of the given lines. For example, there are $$$4$$$ such triangles in the following configuration:

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 3\,000$$$), the number of lines. Each of the next $$$n$$$ lines describes a single line as a character $$$d$$$ and an integer $$$c$$$ in the following way:

  • $$$d$$$ is equal to "H" if the line is horizontal; $$$c$$$ is an integer such that the line is described by the equation $$$y=c$$$;
  • $$$d$$$ is equal to "V" if the line is vertical; $$$c$$$ is an integer such that the line is described by the equation $$$x=c$$$;
  • $$$d$$$ is equal to "D" if the line is diagonal; $$$c$$$ is an integer such that the line is described by the equation $$$x+y=c$$$;
In each of these cases $$$0 \leq c \leq 3\,000$$$. All of the given lines are guaranteed to be distinct.
Output

Output a single integer, the total number of non-degenerate triangles with sides on the given lines.

Examples
Input
5
V 0
D 1
H 0
D 4
H 2
Output
4
Input
3
V 1
H 2
D 3
Output
0