在无限的二维平面上有 $n$ 颗闪亮的星星。第 $i$ 颗星星可以看作位于 $(x_i, y_i)$ 的点。保证没有两颗星星位于同一位置。

每颗星星都会发出相同的互不相交的光照区域。每个光照区域都以角度的形式给出。现在你需要计算，对于每一颗星星，它被其他星星照亮的次数。

注意，星星不会遮挡光线。

输入格式

第一行包含两个整数 $n, k$ ($1 \le n \le 10^5, 1 \le k \le 10$)，分别表示星星的数量和光照区域的数量。

接下来的 $n$ 行描述平面上的所有星星。其中第 $i$ 行包含两个整数 $x_i, y_i$ ($0 \le x_i, y_i \le 50000$)，描述星星的坐标。

接下来的 $k$ 行描述所有的光照区域。其中第 $i$ 行包含两个整数 $l_i, r_i$ ($0 \le l_i \le r_i < 180$)，描述一个被照亮的区域。角度的计算从正 $x$ 轴开始，并按顺时针方向旋转。

保证任意两个不同的角度区间互不相交。

输出格式

输出一行，包含 $n$ 个整数，表示每颗星星被照亮的次数。

样例

输入 1

4 2
0 0
4 5
2 4
1 5
0 45
120 150

输出 1

1 1 1 0