Migrated from Lutece 2284 白给的几何题4

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

左上角为(x1,y1),右下角为(x2,y2)的矩形，存在n条直线将矩形分成n+1块，保证无交点。

存在m个坐标，最终询问每个块里有多少个坐标

Input

多组输入

对于每组输入，第一行n,m,x1,y1,x2,y2

接下n行，每行两个数字表示这条直线和上边界的交点以及和下边界的交点。

再接下来m行，表示每个点。

读入n=0时结束

Output

对于每组输入，输出格式如下

0 : num1

1 : num2.....

表示在第几块中的点有多少个。

Samples

5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
 5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10
0

0: 2
1: 1
2: 1
3: 1
4: 0
5: 1

0: 2
1: 2
2: 2
3: 2
4: 2

Constraints

点如果恰好在线上计算入靠右的区间

Note

x,y<=100000;

n,m<=5000

Resources

2019 UESTC ACM Training for math and geometry