울타리 기둥 칠하기

Farmer John의 소 $N$마리($1 \leq N \leq 10^5$)는 각자 목장을 둘러싼 울타리를 따라 매일 산책하기를 좋아한다. 소가 울타리 기둥 옆을 지나갈 때마다 기둥에 몸이 닿으므로, Farmer John은 기둥 페인트를 정기적으로 다시 칠해야 한다.

울타리는 $P$개의 기둥($4 \leq P \leq 2\cdot 10^5$, $P$는 짝수)으로 이루어진다. 각 기둥은 농장 지도 위의 서로 다른 2차원 점 $(x,y)$이다($0 \leq x, y \leq 10^9$). 기둥은 인접한 두 기둥과 수직 또는 수평 선분으로 이어지므로, 울타리는 변이 x축이나 y축에 평행한 다각형이다. 마지막 기둥은 첫 기둥과 이어져 목장을 둘러싸는 닫힌 고리를 이룬다. 울타리 선분은 끝점에서만 겹칠 수 있다. 각 기둥은 정확히 두 선분의 끝점이며, 한 끝점에서 만나는 두 선분은 항상 수직이다. 기둥의 위치가 주어지면 울타리의 모양은 하나로 정해진다.

각 소는 울타리 위에서 원하는 출발점과 도착점을 가진다. 이 점들은 기둥 위에 있을 수도, 기둥 사이에 있을 수도 있다. 소는 출발점에서 도착점까지 울타리를 따라 걷는다. 울타리가 닫힌 고리이므로 경로는 두 가지인데, 소는 게으르기 때문에 더 짧은 쪽으로 걷는다. 두 경로의 길이가 같은 경우는 없다.

소가 기둥을 지나가거나 기둥이 출발점 또는 도착점이면 그 기둥에 닿은 것으로 본다. Farmer John이 다음에 칠할 기둥을 정할 수 있도록, 각 기둥이 하루에 받는 접촉 횟수를 구하라.

첫 줄에 $N$과 $P$가 주어진다. 다음 $P$개의 줄에는 각각 기둥의 위치 $(x, y)$를 나타내는 정수 두 개가 주어진다. 기둥은 어떤 순서로든 주어질 수 있다. 다음 $N$개의 줄에는 각각 소 한 마리의 산책 출발점 $(x_1, y_1)$과 도착점 $(x_2, y_2)$를 나타내는 정수 네 개 $x_1$ $y_1$ $x_2$ $y_2$가 주어진다.

$P$개의 정수를 출력한다. 각 정수는 해당 기둥이 받은 접촉 횟수이다.