Una pista de hockey para cerdos tiene la forma de un polígono convexo $A$ con vértices $A_1,\ldots,A_n$. En el vértice $A_i$ hay una portería numerada $i$.

La pista se encuentra completamente y estrictamente dentro de otro polígono convexo $B$ con vértices $B_1,\ldots,B_m$. El polígono $B$ delimita una zona peligrosa: no se permite que un espectador esté dentro de $B$, pero puede situarse en su frontera o fuera de $B$.

Las porterías están abiertas hacia el interior de la pista. Por el exterior, cada portería está protegida por una pequeña valla opaca formada por dos paneles colocados a lo largo de los dos lados de la pista incidentes en el vértice $A_i$.

Un espectador situado en el punto $P$ puede ver un gol marcado en la portería $i$ si la semirrecta que parte de $A_i$ y pasa por $P$ se encuentra dentro del ángulo interior del polígono $A$ en el vértice $A_i$, o en su frontera. En caso contrario, la valla protectora de esta portería bloquea la visión. La valla de la portería $i$ solo puede bloquear la visión de la portería $i$ y no afecta a la visibilidad de las demás porterías.

Debido a la fuerza y la masa de los cerdos, una portería en la que se marca un gol se rompe inmediatamente y deja de utilizarse. El partido termina cuando todas las porterías están rotas. El orden en el que se marcan los goles viene dado por una permutación $p_1,p_2,\ldots,p_n$: el $k$-ésimo gol se marca en la portería $p_k$.

Antes del $k$-ésimo gol, el espectador quiere cambiar de ubicación: elegir un punto válido $P$ fuera del interior de $B$, desplazarse hasta él y permanecer allí hasta el final del partido. De forma independiente para cada $k$ de $1$ a $n$, determina el número máximo de goles entre los restantes (en las porterías $p_k,\ldots,p_n$) que el espectador podrá ver tras elegir el mejor punto posible $P$.

Entrada

La primera línea contiene un entero $1\le T\le 10^5$: el número de casos de prueba. A continuación se dan las descripciones de los $T$ casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n$ y $m$ ($3\le n,m\le 5\cdot 10^5$): el número de vértices de los polígonos $A$ y $B$, respectivamente.

Cada una de las siguientes $n$ líneas contiene dos enteros $x_i$ e $y_i$: las coordenadas del vértice $A_i$. Los vértices del polígono $A$ se dan en sentido antihorario.

Cada una de las siguientes $m$ líneas contiene dos enteros $z_i$ y $v_i$: las coordenadas del vértice $B_i$. Los vértices del polígono $B$ se dan en sentido antihorario.

Todas las coordenadas de los vértices de los polígonos son enteros cuyo valor absoluto no supera $10^9$. Se garantiza que ambos polígonos son estrictamente convexos y que el polígono $A$ se encuentra completamente y estrictamente dentro del polígono $B$.

La última línea de cada caso de prueba contiene una permutación $p_1,p_2,\ldots,p_n$ de los números de $1$ a $n$: el orden de las porterías en las que se marcan los goles.

Se garantiza que la suma de $n$ entre todos los casos de prueba no supera $5\cdot 10^5$, y que la suma de $m$ entre todos los casos de prueba no supera $5\cdot 10^5$.

Salida

Para cada caso de prueba, imprime $n$ enteros: el $k$-ésimo entero debe ser igual al número máximo de goles futuros que el espectador puede ver si elige el mejor punto válido posible $P$ antes del $k$-ésimo gol.

Ejemplos

Entrada 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

Salida 1

1 1 1
2 2 1 1

Nota

Consideremos el segundo caso de prueba del ejemplo.

Antes del primer gol, el espectador puede elegir, por ejemplo, el punto $(0,10)$. Desde este punto se ven los goles en las porterías $1$ y $2$, por lo que el espectador puede ver $2$ goles futuros.

Antes del segundo gol, la portería $1$ ya está rota. El espectador puede elegir el punto $(-3.5,2.5)$, situado en la frontera del polígono $B$. Desde este punto se ven los goles en las porterías $2$ y $3$, por lo que el espectador puede volver a ver $2$ goles futuros.

Antes del tercer gol, solo quedan las porterías $3$ y $4$. No existe ningún punto válido desde el que ambos goles sean visibles a la vez. Sin embargo, el espectador puede elegir, por ejemplo, el punto $(3,2)$ en la frontera de $B$ y ver el gol en la portería $4$. Por tanto, la respuesta para este momento es $1$.

Antes del cuarto gol, solo queda la portería $4$. El espectador puede permanecer en el punto $(3,2)$ y ver el último gol. Por tanto, la respuesta también es $1$.

Así, para el segundo caso de prueba del ejemplo, las respuestas son $2,2,1,1$.