UFO 침공

UFO의 대한민국 침공이 시작됐다! 총 $N$대의 UFO가 대한민국 영공에 침입했고, $i$번째 UFO는 정수 좌표 $(x_i, y_i)$에서 포착되었다. UFO는 관측된 시점 이후 1초마다 순간이동하며, $i$번째 UFO는 1초마다 $(dx_i, dy_i)$만큼 이동한 다른 정수 좌표로 옮겨 간다. 같은 위치에 여러 UFO가 있을 수도 있다.

대한민국 공군은 UFO를 격파하기 위해 $x$축 또는 $y$축에 평행한 직선형 레이저 빔을 설치하려고 한다. 빔은 축에 평행하게 무한히 뻗어 나가며, 빔 위를 지나간 UFO는 즉시 파괴된다. UFO는 순간이동으로 움직이므로, 순간이동 전 위치와 순간이동 후 위치 사이에 빔이 놓여 있으면 그 UFO는 파괴되지 않는다.

레이저는 UFO가 관측된 즉시 가동되어 정수 시간 $T$초 동안 작동한다. 그리고 $T$초에 UFO가 순간이동하기 직전에 작동을 멈춘다.

다만 지금 가동할 수 있는 레이저 빔은 하나뿐이어서, $Q$명의 작전 참모가 각자 빔을 설치할 위치를 하나씩 제시했다. 영공을 지키기 위해, 각 참모가 제시한 위치에 빔을 가동했을 때 빔이 멈추기 전까지 파괴할 수 있는 UFO의 수를 구하라.

첫째 줄에 UFO의 수 $N$, 작전 참모의 수 $Q$, 레이저 빔의 작동 시간 $T$가 공백으로 구분되어 주어진다. ($1 \le N, Q \le 100\,000$, $1 \le T \le 10^9$)

이후 $N$개의 줄에 $i$번째 UFO의 초기 위치 $x_i$, $y_i$와 순간이동 거리 $dx_i$, $dy_i$가 공백으로 구분되어 주어진다. ($0 \le x_i, y_i \le 100\,000$, $-100\,000 \le dx_i, dy_i \le 100\,000$)

이후 $Q$개의 줄에 $i$번째 작전 참모가 제시한 레이저 위치가 다음 형식 중 하나로 주어진다.

• 1 $q_i$: 직선 $y = q_i$ 위에 레이저 빔을 가동하는 경우 ($0 \le q_i \le 100\,000$)
• 2 $q_i$: 직선 $x = q_i$ 위에 레이저 빔을 가동하는 경우 ($0 \le q_i \le 100\,000$)

$Q$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 작전 참모가 제시한 위치에 레이저 빔을 가동했을 때 파괴할 수 있는 UFO의 수를 순서대로 출력한다.