Triangles and Lines Intersection

Given \(N\) triangles and \(M\) lines, where each line is either horizontal (parallel to the \(x\)-axis) or vertical (parallel to the \(y\)-axis), determine for each line how many triangles it crosses.

A line is said to cross a triangle if and only if it splits the triangle into two parts with strictly positive areas. In other words, for a horizontal line \(y=c\), the line crosses a triangle if and only if the triangle has at least one vertex with \(y>c\) and at least one vertex with \(yc\) and one with \(x<c\).

inputFormat

The first line contains two integers \(N\) and \(M\). The next \(N\) lines each contain six integers \(x_1\, y_1\, x_2\, y_2\, x_3\, y_3\), representing the coordinates of the vertices of a triangle. The following \(M\) lines each contain a character and an integer. The character is either H (for a horizontal line \(y=c\)) or V (for a vertical line \(x=c\)).

outputFormat

Output \(M\) lines, where the \(i\)-th line contains a single integer indicating the number of triangles crossed by the corresponding line.

sample

2 2
0 0 2 0 1 3
0 1 2 1 1 -1
H 1
V 1

2
2