Description

Given $N$ triangles and $M$ lines. Each line is either parallel to the $x$ axis or parallel to the $y$ axis. For each of the $M$ lines, find how many triangles it passes through.

(A line passes through a triangle if and only if the line can split the triangle into two polygons whose areas are both greater than zero.)

Input Format

The first line contains a positive integer $N$, the number of triangles.

The next $N$ lines each contain three coordinates $(x_1,y_1)$, $(x_2,y_2)$, $(x_3,y_3)$, representing three points. These three points are not collinear and form a triangle. All coordinates are non-negative integers, and triangles may overlap.

The next line contains a positive integer $M$, the number of lines.

The next $M$ lines each contain a string x = c or y = c (note the spaces on both sides of the equals sign), describing a line. Here c is a non-negative integer.

Output Format

For each line, output one integer, the number of triangles it passes through.

3
1 0 0 2 2 2
1 3 3 5 4 0
5 4 4 5 4 4
4
x = 4
x = 1
y = 3
y = 1

0
1
1
2

4
2 7 6 0 0 5
7 1 7 10 11 11
5 10 2 9 6 8
1 9 10 10 4 1
4
y = 6
x = 2
x = 4
x = 9

3
2
3
2

Hint

Constraints

For $40\%$ of the testdata, $M \le 300$.

For another $40\%$ of the testdata, all triangle coordinates are $< 1000$.

For $100\%$ of the testdata, $2 \le N,M \le 10^5$, and $0 \le x_1,y_1,x_2,y_2,x_3,y_3 < 10^6$.

Translated by ChatGPT 5