Stacking Sticks

Interview

Time limit1sMemory limit512 MB

Summary

Drop 1x4 horizontal and 4x1 vertical blocks onto columns, then report the highest block height at a given x coordinate.

Level: Medium5 of 10
Topics: Segment tree, Sorting, Simulation
Solved: No attempts yet

Statement

Satori is playing a stacking game with horizontal $1 \times 4$ blocks and vertical $4 \times 1$ blocks. Once you choose where a block lands, it falls straight down. If part of the bottom face of a falling block touches the top face of another block or the floor, the block stops. Blocks that are next to each other horizontally may pass by each other while falling.

Write a program that handles the following queries.

1 i: Drop a horizontal $1 \times 4$ block so that its left end cell is at $x = i$ .
2 i: Drop a vertical $4 \times 1$ block so that it is at $x = i$ .
3 i: Print the maximum $y$ coordinate of the blocks at $x = i$ . If no block exists at that $x$ coordinate, print $0$ .

Input

The first line contains the number of queries $Q$ . $(1 \leq Q \leq 150\,000)$

The next $Q$ lines each contain one query. Query type 3 appears at least once. $(-10^9 \leq i \leq 10^9,\ i$ is an integer $)$

Output

For each query of type 3, print the answer on its own line.

Examples1

Example 1
Input
```
5
1 1
2 3
1 2
3 1
3 5
```
Expected output
```
1
6
```