Considering a set of segments. At the beginning, the set is totally empty.

There are N operations: insert or erase a vertical (or horizontal) segment and then you have to compute how many intersections are there.

There is no two same type of segments that share a common point in the set.

Input

The first line contains N (1 ≤ N ≤ 10⁵) - the number of operations.

The following N lines describe the operations:

• 1 X₁ Y₁ X₂ Y₂: insert a segment whose two endpoints are (X₁, Y₁) and (X₂, Y₂) to the set. (|X₁|, |Y₁|, |X₂|, |Y₂| ≤ 10⁹)
• 2 K: erase the K-th oldest segment from the set. (1 ≤ K ≤ current size of the set)

Output

For each query, print the number of intersections of the line segments in the set after processing the operation in one line.

Example

Input:
10
1 -1 0 -2 0
1 2 -2 0 -2
1 1 1 1 -3
2 1
1 6 -2 5 -2
2 3
1 2 -2 2 -6
1 -4 -3 -5 -3
1 3 -4 -1 -4
2 2

Output:
0
0
1
1
1
1
2
2
3
2

UPD (1/30/2015): Increase time limit from 2s to 5s. My C++ solution (unoptimized) runs in about 7 seconds.