24531번 - 슈팅 게임

문제

공부만 하며 학창 시절을 보낸 남라는 드디어 지긋지긋한 학업을 청산하고 친구들과 함께 게임을 시작했다! 남라가 플레이하는 게임은 레이저를 발사하여 벽을 파괴하는 슈팅 게임이다. 게임 속 공간은 xy평면이고 벽은 x축과 평행한 선분으로, 레이저가 날아가는 것은 점이 이동하는 것으로 나타낼 수 있다. 서로 다른 두 벽은 만나지 않는다. (한 점에서 만나는 것도 만나는 것이다.)

레이저는 초기 좌표에서부터 날아가면서 만나는 모든 벽을 파괴하며, 파괴된 벽은 사라진다. 기본적으로 레이저가 날아가는 방향은 +y축 방향이다. 그러나 각각의 벽은 고윳값을 가지고 있고, 이로 인하여 레이저가 벽을 파괴한다면 레이저의 이동 경로가 변화하게 된다.

레이저가 $(a,b)$에서 벽과 만나서 벽을 파괴하였고, 이 벽의 고윳값이 $a'$라면 레이저는 $(a,b)$와 $(a',b+1)$을 잇는 직선 경로를 따라 $(a',b+1)$로 날아간다. 레이저가 $(a',b+1)$에서 벽과 만나지 않는다면 다시 +y축 방향으로 날아간다.

또한 레이저는 다음과 같은 성질을 가진다.

• 레이저는 초기 좌표에서 벽과 만날 때도 벽을 파괴한다.
• 레이저의 y좌표가 10ドル^9$보다 커지는 순간 레이저는 사라진다.
• 둘 이상의 레이저가 동시에 날아가지 않는다. 즉, 레이저를 발사하고 레이저가 사라진 후에 다음 레이저를 발사한다.

예를 들어, 그림과 같이 $(-2,1)$과 $(2,1)$을 끝 점으로 하고 고윳값이 1ドル$인 벽, $(-3,3)$과 $(1,3)$을 끝 점으로 하고 고윳값이 0ドル$인 벽, $(1,2)$와 $(5,2)$를 끝 점으로 하고 고윳값이 1ドル$인 벽이 있을 때 초기 좌표가 $(-2,1)$인 레이저를 발사하면 세 개의 벽을 모두 파괴하고 점선으로 나타낸 경로를 따라 이동한다.

현재 게임 내에 $N$개의 벽이 존재하고 남라는 $Q$번의 레이저 발사를 하려고 한다. 벽의 정보와 레이저 발사의 정보가 주어질 때, 각 레이저가 어떤 벽을 파괴하는지 구하는 프로그램을 작성해보자.

입력

첫째 줄에 벽의 개수 $N$과 레이저 발사의 횟수 $Q$가 공백을 사이에 두고 차례로 주어진다. $(1\leq N\leq 200,000円;$ 1ドル\leq Q\leq 200,000円)$

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에는 $i$번 벽의 정보를 나타내는 정수 $l_i, r_i, h_i, v_i$가 공백을 사이에 두고 차례로 주어진다. 벽은 $(l_i, h_i)$와 $(r_i, h_i)$를 잇는 선분이고, $v_i$는 벽의 고윳값을 의미한다. $(-10^9\leq l_i, r_i, h_i, v_i\leq 10^9;$ $l_i<r_i)$

그 다음 줄부터 레이저를 발사하는 순서대로, $Q$개의 줄에 걸쳐 $i$번째 줄에는 $i$번째 레이저 발사의 정보를 나타내는 정수 $x_i, y_i$가 공백을 사이에 두고 차례로 주어진다. 레이저의 초기 좌표가 $(x_i, y_i)$라는 의미이다. $(-10^9\leq x_i,y_i\leq 10^9)$

출력

레이저를 발사하는 순서대로, 한 줄 또는 두 줄에 걸쳐 각 레이저가 파괴한 벽의 정보를 출력한다. 레이저가 아무 벽도 파괴하지 않는다면 첫째 줄에만 0을 출력한다. 레이저가 적어도 하나의 벽을 파괴한다면 첫째 줄에는 레이저가 파괴한 벽의 개수를 출력하고, 둘째 줄에는 레이저가 파괴한 벽의 번호를 파괴된 순서대로 공백을 사이에 두고 출력한다.

제한

힌트