ZQUERY2 - Intersection Query

no tags 

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 (1N105) - the number of operations.

The following N lines describe the operations:

  • 1 X1 Y1 X2 Y2: insert a segment whose two endpoints are (X1, Y1) and (X2, Y2) to the set. (|X1|, |Y1|, |X2|, |Y2| ≤ 109)
  • 2 K: erase the K-th oldest segment from the set. (1K ≤ 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.


hide comments
Rishav Goyal: 2016-08-22 13:38:14

@author: will it pass nlogn^3?

-- setter --
- Probably not.

Last edit: 2016-10-01 06:35:37

Added by:What Does The Fox Say?
Date:2015-01-07
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY