돼지들을 위한 하키 경기장은 꼭짓점이 $A_1,\ldots,A_n$인 볼록 다각형 $A$ 모양이다. 꼭짓점 $A_i$에는 번호가 $i$인 골대가 있다.

경기장 전체는 꼭짓점이 $B_1,\ldots,B_m$인 또 다른 볼록 다각형 $B$의 내부에 엄밀히 포함된다. 다각형 $B$는 위험 구역의 경계를 이룬다. 관중은 $B$의 내부에 있을 수 없지만, 그 경계나 $B$의 외부에는 서 있을 수 있다.

골대는 경기장 안쪽을 향해 열려 있다. 각 골대의 바깥쪽에는 꼭짓점 $A_i$에 인접한 경기장의 두 변을 따라 놓인 두 개의 판으로 이루어진 작은 불투명 울타리가 있다.

점 $P$에 있는 관중은 $A_i$에서 시작하여 $P$를 지나는 반직선이 다각형 $A$의 꼭짓점 $A_i$에서의 내각 내부 또는 그 경계에 놓여 있으면 골대 $i$에 들어가는 골을 볼 수 있다. 그렇지 않으면 이 골대의 보호 울타리가 시야를 가린다. 골대 $i$의 울타리는 골대 $i$의 시야만 가릴 수 있으며 다른 골대의 가시성에는 영향을 주지 않는다.

돼지들의 힘과 무게 때문에 골이 들어간 골대는 즉시 부서져 더 이상 사용되지 않는다. 모든 골대가 부서지면 경기가 끝난다. 골이 들어가는 순서는 순열 $p_1,p_2,\ldots,p_n$으로 주어진다. $k$번째 골은 골대 $p_k$에 들어간다.

$k$번째 골이 들어가기 전에 관중은 위치를 바꾸려 한다. $B$의 내부가 아닌 곳에서 유효한 점 $P$ 하나를 선택하고, 그곳으로 이동한 뒤 경기가 끝날 때까지 머문다. $1$부터 $n$까지의 각 $k$에 대해 독립적으로, 최선의 점 $P$를 선택했을 때 관중이 남은 골들(골대 $p_k,\ldots,p_n$에 들어가는 골들) 중 볼 수 있는 골의 최대 개수를 구하여라.

입력

첫 번째 줄에는 테스트 케이스의 개수인 정수 $T$ ($1\le T\le 10^5$)가 주어진다. 이어서 $T$개의 테스트 케이스 설명이 주어진다.

각 테스트 케이스의 첫 번째 줄에는 각각 다각형 $A$와 $B$의 꼭짓점 개수인 두 정수 $n$, $m$ ($3\le n,m\le 5\cdot 10^5$)이 주어진다.

다음 $n$개의 줄에는 각각 꼭짓점 $A_i$의 좌표인 두 정수 $x_i$, $y_i$가 주어진다. 다각형 $A$의 꼭짓점은 반시계 방향 순서로 주어진다.

다음 $m$개의 줄에는 각각 꼭짓점 $B_i$의 좌표인 두 정수 $z_i$, $v_i$가 주어진다. 다각형 $B$의 꼭짓점은 반시계 방향 순서로 주어진다.

다각형의 모든 꼭짓점 좌표는 절댓값이 $10^9$ 이하인 정수이다. 두 다각형 모두 엄밀히 볼록하며 다각형 $A$ 전체가 다각형 $B$의 내부에 엄밀히 포함됨이 보장된다.

각 테스트 케이스의 마지막 줄에는 $1$부터 $n$까지의 수로 이루어진 순열 $p_1,p_2,\ldots,p_n$이 주어진다. 이는 골이 들어가는 골대의 순서이다.

모든 테스트 케이스에 걸친 $n$의 합은 $5\cdot 10^5$ 이하이며, 모든 테스트 케이스에 걸친 $m$의 합도 $5\cdot 10^5$ 이하임이 보장된다.

출력

각 테스트 케이스마다 $n$개의 정수를 출력하여라. $k$번째 정수는 관중이 $k$번째 골 전에 최선의 유효한 점 $P$를 선택했을 때 볼 수 있는 앞으로의 골의 최대 개수와 같아야 한다.

예제

입력 1

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 1
2 2 1 1

참고

두 번째 예제 테스트 케이스를 살펴보자.

첫 번째 골 전에 관중은 예를 들어 점 $(0,10)$을 선택할 수 있다. 이 점에서는 골대 $1$과 $2$에 들어가는 골이 보이므로 관중은 앞으로의 골 2개를 볼 수 있다.

두 번째 골 전에는 골대 $1$이 이미 부서져 있다. 관중은 다각형 $B$의 경계에 있는 점 $(-3.5,2.5)$를 선택할 수 있다. 이 점에서는 골대 $2$와 $3$에 들어가는 골이 보이므로 관중은 다시 앞으로의 골 2개를 볼 수 있다.

세 번째 골 전에는 골대 $3$과 $4$만 남아 있다. 두 골을 동시에 볼 수 있는 유효한 점은 없다. 하지만 관중은 예를 들어 $B$의 경계에 있는 점 $(3,2)$를 선택하여 골대 $4$에 들어가는 골을 볼 수 있다. 따라서 이 시점의 답은 $1$이다.

네 번째 골 전에는 골대 $4$만 남아 있다. 관중은 점 $(3,2)$에 그대로 머물러 마지막 골을 볼 수 있다. 따라서 답은 역시 $1$이다.

그러므로 두 번째 예제 테스트 케이스의 답은 $2,2,1,1$이다.