## DMOPC '21 Contest 4 P1 - Tree Shopping

View as PDF

Points: 7
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type

Alice is buying Christmas trees! The shopkeeper, for some reason, keeps the trees arranged in a weird layout. Each of the trees covers a triangular region in a coordinate plane where one side of the triangle is parallel to the x-axis and another side is parallel to the y-axis. The shop offers special Christmas offers, where the -th offer allows the customer to buy all trees covering the point . Alice wonders: for each offer, how many trees is she able to buy?

#### Input Specification

The first line contains integers and .

The next lines each contain integers , describing the coordinates of the vertices of the -th tree. Specifically, the -th tree covers the area bounded by the triangle with vertices .

The next lines each contain integers , the point included in the -th offer.

#### Output Specification

For each offer, output the answer on a new line.

#### Sample Input

2 5
-2 -3 -2 3 7 -3
-4 1 -4 -6 3 1
2 2
-4 1
1 -2
-2 -1
3 -5

#### Sample Output

0
1
1
2
0

#### Explanation

A diagram of the sample case is provided below: