Wooden Board

Time limit2sMemory limit1024 MB

Summary

Sheets hang on a board, each held by a nail. Removing a sheet drops the nails piercing it, possibly cascading, and queries ask nail counts or remaining sheets.

Level: Medium6 of 10
Topics: Graph, DFS, Implementation
Solved: No attempts yet

Statement

Petya and Vasya love solving interesting problems. They share one rectangular board. The board is a rectangle with sides parallel to the coordinate axes, with corners $(0, 0)$ and $(W, H)$ at the bottom-left and top-right. They hang sheets of paper on it with the statements of problems they have not solved yet. Each sheet is a rectangle, and it may degenerate to a single point. A sheet is hung on a special nail that stops it from rotating around the nail. The sheets are always hung with their sides parallel to the axes. A nail holds a sheet if the nail's point is inside the sheet or on its boundary.

At each moment, one of the friends can do one of the following:

Hang a sheet on a nail. A new sheet may be hung on top of other sheets. The nail pierces every sheet that contains its point, inside or on the boundary.
Remove sheet number $k$ from the board. All nails that pierce it fall. Because of this, other sheets may fall too. Sheets are numbered from 1 in the order they were hung.
Ask how many nails pierce sheet number $k$ . If the sheet has fallen, the answer is 0.
Ask how many sheets remain on the board.

Help Petya and Vasya answer their questions.

Input

The first line contains two integers $W$ and $H$ $(5 \le W, H \le 10^8)$ , the width and height of the board.

The second line contains the number $N$ $(1 \le N \le 10000)$ , the number of queries.

Each of the next $N$ lines describes a query of one of four types:

1 x1 y1 x2 y2 x y: Hang a sheet whose lower-left corner is $(x_1, y_1)$ and upper-right corner is $(x_2, y_2)$ , and attach it with a nail at $(x, y)$ . It is given that $0 \le x_1 \le x \le x_2 \le W$ and $0 \le y_1 \le y \le y_2 \le H$ . Several nails may be at the same point.
2 k: Remove sheet $k$ . It is guaranteed that some sheet with number $k$ was hung before this query.
3 k: Ask how many nails hold sheet $k$ . It is guaranteed that sheet $k$ was hung before this query.
4: Ask how many sheets remain on the board.

All numbers in the input are integers.

Output

For each query of type 3 and type 4, print the answer on a separate line, in the order the queries appear.

Examples2

Example 1

Input

10 10
8
1 2 2 8 8 3 3
4
1 0 0 5 5 5 5
3 1
1 5 5 10 10 5 5
2 2
4
3 3

Expected output

Example 2

Input

100 100
6
1 5 5 5 5 5 5
1 5 5 5 5 5 5
4
3 1
2 2
4

Expected output

2
2
1