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$초 동안 가동된 후 UFO들이 $T$초에 순간이동하기 직전에 작동을 정지한다.

그러나 현재 가동할 수 있는 레이저 빔은 단 하나뿐이었기에, $Q$명의 작전 참모들이 각자 레이저 빔을 설치할 위치를 하나씩 제시했다. 대한민국의 영공을 수호하기 위해, 각 작전 참모들이 제시한 위치에 레이저 빔을 가동한 경우 레이저 빔이 작동을 정지하기 전까지 파괴할 수 있는 UFO의 대수를 구해주자.

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

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

이후 $Q$개의 줄에 걸쳐, $N+i+1$번째 줄에 $i$번째 작전 참모가 제시한 레이저 가동 위치가 다음과 같은 형식으로 주어진다.

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

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