31884번 - Stacking Sticks

문제

사토리는 가로로 긴 1ドル \times 4$ 블럭과, 세로로 긴 4ドル \times 1$ 블럭을 쌓는 놀이를 하고 있다. 블럭이 떨어질 위치를 고르면 이 블럭은 그대로 수직 방향으로 떨어진다. 떨어지는 도중 블럭의 아래쪽 면의 일부분이 다른 블럭의 윗면 또는 바닥과 닿는다면, 블럭은 떨어지는 것을 멈춘다. 이때 좌우로 인접한 블럭끼리는 스쳐 지나갈 수 있다.

사토리를 위해, 여러분은 다음 쿼리를 처리하는 프로그램을 작성해야 한다.

• 1ドル\ i:$ 가로로 긴 1ドル \times 4$ 블럭의 왼쪽 끝 칸이 $x = i$에 위치하게 블럭을 떨어뜨린다.
• 2ドル\ i:$ 세로로 긴 4ドル \times 1$ 블럭이 $x = i$에 위치하게 블럭을 떨어뜨린다.
• 3ドル\ i:$ $x = i$에 존재하는 블럭의 $y$좌표의 최댓값을 출력한다. 해당 $x$좌표에 블럭이 존재하지 않는다면 0ドル$을 출력한다.

입력

첫 번째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \leq Q \leq 150,000円)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다. 3ドル$번 쿼리는 한 번 이상 주어진다. $(-10^9 \leq i \leq 10^9,\ i$는 정수$)$

출력

3ドル$번 쿼리의 답을 한 줄에 하나씩 출력한다.

제한

힌트