広い平原に $N$ 頭のヤギが散らばり、のんびり草を食べています。同じ位置に 2 頭以上のヤギはいません。ヤギは怠け者で移動せず、ときどきその場で向きを変えるだけです。実はすべてロボットであり、歩けず、その場で回転することしかできません。鼻は遠隔操作で点灯できる LED で、目は高性能カメラになっています。映像は遠隔でリアルタイムに確認でき、望む場面を保存できます。自分の鼻も見えます。また透視機能があるので、ヤギが重なって見えても何頭いるかを判別できます。水平方向の視野角は $180^\circ$ で、その $180^\circ$ の境界上にあるものも見えます。

位置関係によっては、一度に $N$ 頭すべてを見られるヤギもいれば、どの方向を向いても一度に全頭を見られないヤギもいます。例えば下図のような $0$ 番から $5$ 番までの 6 頭では、$5$ 番のヤギは一度に 6 頭すべてを見られますが、$2$ 番のヤギはどの方向を向いても一度に全頭を見られません。

特別な実験のため、それぞれ一度に $N$ 頭すべてを見られる異なる 2 頭と、残りから任意の 1 頭を選びます。選んだ 3 頭の鼻を点灯させ、どこからでも位置が分かるようにします。3 頭それぞれの目の映像を見て、点灯した 3 頭が同じ画面に映る場面を各ヤギについて 1 枚ずつ保存します。保存した 3 枚を順に見て、それぞれの画面で、点灯した 3 頭と、点灯した他の 2 頭の間（境界を含む）に見えるすべてのヤギに特別な印を付けます。この実験の目的は、$N$ 頭のうち 3 回すべて印を付けられたヤギの頭数を求めることです。

例えば、6 頭から選んだ 3 頭を赤い点で示すと、下図は各ヤギの視点で印を付けられたヤギを表します。（もちろん、これらの図自体が保存した映像ではありません。）この場合、3 回すべて印を付けられるヤギは $4$ 頭です。

この実験のため、次の 2 つの関数を実装してください。

• void init( int x[], int y[] )：最初に、1 回だけ呼び出される関数です。x と y は長さ $N$ の配列（ベクトル）です。ヤギの $x$ 座標を表す x[0..N-1] と $y$ 座標を表す y[0..N-1] が引数として与えられます。$i$ 番のヤギ（$0\le i\le N-1$）の位置は (x[i], y[i]) です。
• int count( int a, int b, int c )：与えられた 3 頭の座標 (x[a], y[a])、(x[b], y[b])、(x[c], y[c]) を使い、3 回すべて印を付けられるヤギの頭数を求めて返します。

実装の詳細

goat.cpp という名前のファイルを 1 つ提出してください。このファイルには次の関数を実装する必要があります。

void init( int x[], int y[] );
int count( int a, int b, int c );

これらの関数は上で説明したとおり動作しなければなりません。他の関数を作り内部で使っても構いません。提出したコードで入出力や他のファイルへのアクセスを行ってはいけません。

採点プログラムの例

与えられる採点プログラムは、次の形式で入力を読みます。

• 1 行目：$N\ Q$。$N$ はヤギの頭数、$Q$ はクエリの個数です。
• 続く $N$ 行の各行：$x\ y$。ヤギの位置の $x$ 座標と $y$ 座標です。
• 続く $Q$ 行の各行：$a\ b\ c$ ($a,b,c$)。3 頭のヤギの番号で、$0\le a,b,c\le N-1$ です。

採点プログラムは、各クエリについて条件を満たすヤギの頭数を 1 行ずつ出力します。

制約

• $3\le N\le 3000$
• $1\le Q\le 5\times10^6$
• すべてのヤギの $x$ 座標と $y$ 座標は $0$ 以上 $10^9$ 以下です。

小課題

1 (5 点)

• $N\le 500$, $Q\le 10^5$
• どの 3 点も同一直線上にありません。

2 (17 点)

• $N\le 500$, $Q\le 10^5$

3 (10 点)

• $N\le 500$
• どの 3 点も同一直線上にありません。

4 (8 点)

• $N\le 500$

5 (29 点)

• どの 3 点も同一直線上にありません。

6 (31 点)

• 追加の制約はありません。

入出力例

入力 1

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

出力 1

4
4
3

以下に例 1 の関数呼び出しとその結果を順に示します。