豚のためのホッケーリンクは、頂点が $A_1,\ldots,A_n$ である凸多角形 $A$ の形をしています。頂点 $A_i$ には、番号 $i$ のゴールがあります。

リンク全体は、頂点が $B_1,\ldots,B_m$ である別の凸多角形 $B$ の内部に厳密に含まれています。多角形 $B$ は危険区域の境界を定めています。観客は $B$ の内部に入ることはできませんが、その境界上または $B$ の外側に立つことはできます。

ゴールはリンクの内側に向かって開いています。各ゴールの外側は、頂点 $A_i$ に接するリンクの 2 辺に沿って置かれた 2 枚の板からなる、小さな不透明な柵で保護されています。

点 $P$ にいる観客は、$A_i$ を始点として $P$ を通る半直線が、頂点 $A_i$ における多角形 $A$ の内角の内部またはその境界上にある場合、ゴール $i$ に入る得点を見ることができます。それ以外の場合、このゴールの保護柵が視界を遮ります。ゴール $i$ の柵が遮ることができるのはゴール $i$ の視界だけであり、他のゴールの見え方には影響しません。

豚の力と体重のため、得点が入ったゴールはすぐに壊れ、その後は使われません。すべてのゴールが壊れると試合は終了します。得点が入る順序は順列 $p_1,p_2,\ldots,p_n$ で与えられます。$k$ 回目の得点はゴール $p_k$ に入ります。

$k$ 回目の得点の前に、観客は場所を変えたいと考えています。$B$ の内部ではない有効な点 $P$ を 1 つ選び、そこに移動し、試合が終わるまでそこに留まります。$1$ から $n$ までの各 $k$ について独立に、最もよい点 $P$ を選んだ後に観客が見ることのできる、残りの得点（ゴール $p_k,\ldots,p_n$ に入るもの）の最大数を求めてください。

入力

最初の行には、テストケース数を表す整数 $T$（$1\le T\le 10^5$）が 1 つ含まれます。続いて $T$ 個のテストケースの説明が与えられます。

各テストケースの最初の行には、多角形 $A$ と $B$ の頂点数をそれぞれ表す 2 つの整数 $n,m$（$3\le n,m\le 5\cdot 10^5$）が含まれます。

続く $n$ 行には、それぞれ頂点 $A_i$ の座標を表す 2 つの整数 $x_i,y_i$ が含まれます。多角形 $A$ の頂点は反時計回りの順序で与えられます。

続く $m$ 行には、それぞれ頂点 $B_i$ の座標を表す 2 つの整数 $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

注記

2 番目のサンプルのテストケースを考えます。

最初の得点の前に、観客は例えば点 $(0,10)$ を選ぶことができます。この点からはゴール $1$ と $2$ に入る得点が見えるので、観客は今後の得点を $2$ 回見ることができます。

2 回目の得点の前には、ゴール $1$ はすでに壊れています。観客は多角形 $B$ の境界上にある点 $(-3.5,2.5)$ を選ぶことができます。この点からはゴール $2$ と $3$ に入る得点が見えるので、観客は再び今後の得点を $2$ 回見ることができます。

3 回目の得点の前には、ゴール $3$ と $4$ だけが残っています。これらの両方の得点を同時に見ることのできる有効な点はありません。しかし、観客は例えば $B$ の境界上の点 $(3,2)$ を選び、ゴール $4$ に入る得点を見ることができます。したがって、この時点の答えは $1$ です。

4 回目の得点の前には、ゴール $4$ だけが残っています。観客は点 $(3,2)$ に留まって最後の得点を見ることができます。したがって、答えはここでも $1$ です。

よって、2 番目のサンプルのテストケースの答えは $2,2,1,1$ です。