J. Tide Pool Islands
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$P$$$ be the interior of a simple polygon in the Cartesian plane. For a real number $$$h$$$, define $$$S_h = \{(x, y) \in P \mid y \gt h\}$$$.

Two subsets that intersect only at boundary points are not considered connected.

You are given $$$q$$$ values of $$$h$$$. For each value, find the number of connected components of $$$S_h$$$.

Input

There is only one test case in each test file.

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$), the number of vertices of the polygon and the number of queries, respectively.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$|x_i|, |y_i| \le 10^9$$$), the coordinates of the $$$i$$$-th vertex. The vertices are given in counterclockwise order along the boundary. It is guaranteed that they form a simple polygon and that all $$$y_i$$$ are pairwise distinct.

The $$$j$$$-th of the next $$$q$$$ lines contains one integer $$$h_j$$$ ($$$|h_j| \le 10^9$$$), the water level of the $$$j$$$-th query. It is guaranteed that $$$h_j$$$ differs from the $$$y$$$-coordinate of every vertex. The values $$$h_j$$$ are not necessarily distinct.

Output

For each query, output one integer on a separate line — the number of connected components of $$$S_{h_j}$$$.

Example
Input
7 4
0 0
6 2
5 12
4 6
3 14
2 4
1 10
-1
8
13
16
Output
1
3
1
0
Note

For $$$h = -1$$$, $$$S_h$$$ is the entire polygon $$$P$$$, so it has one connected component.

For $$$h = 8$$$, $$$S_h$$$ has $$$3$$$ connected components. For $$$h = 13$$$, $$$S_h$$$ has $$$1$$$ connected component. For $$$h = 16$$$, $$$S_h$$$ is empty and has no connected components.