떨어지는 공

요나스(Jonas)는 세워 둔 판에 비스듬한 고무 발판 $N$개를 붙여 두었다. 각 발판은 하나의 선분이며, 양 끝점은 위아래로 움직일 수 있다. 끝점의 $x$ 좌표는 절대 바뀌지 않고 높이만 바뀐다. 요나스는 다음 두 종류 중 하나인 동작을 순서대로 $K$번 수행한다.

1. 발판 끝 옮기기. 어떤 발판의 한쪽 끝을 새 높이로 올리거나 내린다. 반대쪽 끝은 그대로 있으므로 발판의 길이는 바뀔 수 있다. 이 동작 뒤에도 발판은 결코 수평이 되지 않으며, 어느 순간에도 두 발판이 서로 닿거나 교차하지 않는다.

2. 공 떨어뜨리기. 주어진 $x$ 좌표의 위쪽 높은 곳에서 작은 공을 놓는다. 공은 공중에서는 곧장 아래로 떨어지고, 발판에 닿으면 그 발판의 더 낮은 쪽 끝까지 굴러 내려가 거기서 떨어진 뒤 다시 곧장 아래로 떨어진다. 이 과정을 바닥에 닿을 때까지 반복한다.

발판들은, 한 발판에서 떨어진 공이 다른 발판의 끝에 정확히 떨어지는 일이 없도록 배치되어 있으며, 떨어뜨린 공은 항상 어떤 발판의 끝이 아닌 $x$ 좌표 위에서 출발한다. 떨어뜨린 각 공이 마지막으로 바닥에 닿는 $x$ 좌표를 구하여라.

첫째 줄에 두 정수 $N$과 $K$가 주어진다.

이어지는 $N$개의 줄에는 발판이 하나씩 주어진다. $i+1$번째 줄에는 네 정수 $x_{i1}$, $y_{i1}$, $x_{i2}$, $y_{i2}$가 주어지며, 이는 발판의 왼쪽 끝 $(x_{i1}, y_{i1})$과 오른쪽 끝 $(x_{i2}, y_{i2})$의 좌표이다. 항상 $x_{i1} < x_{i2}$이다.

그다음 $K$개의 줄에는 동작이 하나씩 주어진다. $N+j+1$번째 줄에는 두 정수 $a_j$와 $b_j$가 주어진다.

• $a_j = 0$이면 공을 떨어뜨리며, $b_j$는 그 공의 시작 $x$ 좌표이다.
• $a_j > 0$이면 $a_j$번째 발판의 오른쪽 끝을 옮기며, $b_j$는 그 끝의 새 $y$ 좌표이다.
• $a_j < 0$이면 $|a_j|$번째 발판의 왼쪽 끝을 옮기며, $b_j$는 그 끝의 새 $y$ 좌표이다.

떨어뜨린 공의 수만큼 줄을 출력한다. 공을 떨어뜨린 순서대로, 각 공이 바닥에 닿는 $x$ 좌표를 한 줄에 하나씩 출력한다.

• $1 \le N, K \le 100,000$
• $1 \le x_{i1}, y_{i1}, x_{i2}, y_{i2}, b_j \le 10^6$
• $x_{i1} < x_{i2}$이고 $y_{i1} \ne y_{i2}$
• $-N \le a_j \le N$