#P18104. Hockey Hog

Hockey Hog

Hockey Hog

豪猪们的冰球场是一个严格凸多边形 AA,顶点依次为 A1,…,AnA_1,\ldots,A_n。每个顶点 AiA_i 处有一个编号为 ii 的球门。

冰球场完全位于另一个严格凸多边形 BB 的内部,BB 的顶点为 B1,…,BmB_1,\ldots,B_m。BB 围出的内部是危险区域,观众不能站在其中,但可以站在 BB 的边界上或外部。

球门朝向球场内部。每个球门的外侧有两块不透明挡板,分别沿该顶点相邻的两条球场边放置。

位于 PP 的观众能看到向球门 ii 打进的球,当且仅当从 AiA_i 出发、经过 PP 的射线位于多边形 AA 在 AiA_i 处的内角内部或内角边界上。否则,该球门的挡板会遮住视线。球门 ii 的挡板只影响对球门 ii 的观察,不影响其他球门。

由于豪猪力量太大,每个球门在被打进一个球后就会立即损坏,之后不再使用。所有球门均损坏后,比赛结束。进球顺序由排列 p1,p2,…,pnp_1,p_2,\ldots,p_n 给出:第 kk 个球打进球门 pkp_k。

在第 kk 次进球前,观众可以重新选择一个合法位置 PP,随后一直留在该位置直到比赛结束。

对于每个 k=1,2,…,nk=1,2,\ldots,n,独立地求出:若在第 kk 次进球前选择最佳位置,最多能看到之后打进球门 pk,pk+1,…,pnp_k,p_{k+1},\ldots,p_n 的多少个球?

输入格式

第一行一个整数 TT(1≤T≤1051\le T\le10^5),表示测试组数。

每组数据的第一行包含两个整数 n,mn,m(3≤n,m≤5×1053\le n,m\le5\times10^5)。

接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示 AiA_i 的坐标。顶点按逆时针顺序给出。

接下来 mm 行,每行两个整数 zi,viz_i,v_i,表示 BiB_i 的坐标。顶点同样按逆时针顺序给出。

所有坐标的绝对值均不超过 10910^9。保证 A,BA,B 都严格凸,且 AA 完全位于 BB 的严格内部。

最后一行是 1,2,…,n1,2,\ldots,n 的一个排列 p1,p2,…,pnp_1,p_2,\ldots,p_n。

保证所有测试组的 ∑n≤5×105\sum n\le5\times10^5,且 ∑m≤5×105\sum m\le5\times10^5。

输出格式

对于每组数据输出一行 nn 个整数。第 kk 个数表示在第 kk 次进球前选择位置后,最多能看到的剩余进球数。

样例

2
3 4
1 1
3 1
1 3
0 0
4 0
4 4
0 4
3 2 1
4 3
-1 2
1 2
2 4
-2 4
0 -1
6 5
-6 5
1 2 3 4
1 1 1
2 2 1 1

在第二组数据中:

  • 第一次进球前,可站在 (0,10)(0,10),看到球门1、2的两次进球。
  • 第二次进球前,球门1已经损坏。可站在 BB 边界上的 (−3.5,2.5)(-3.5,2.5),看到球门2、3的两次进球。
  • 第三次进球前,只剩球门3、4,无法在合法位置同时看到两者。站在 BB 边界上的 (3,2)(3,2) 可看到球门4。
  • 第四次进球前,仍可站在 (3,2)(3,2) 看到最后一次进球。