ADAFUROW - Ada and Furrows

As you might already know, Ada the Ladybug is a farmer. She has multiple furrows in which she grows vegetables. She also never grows multiple vegetables of the same kind in the same furrow. Ada sometime plants a new vegetable, harvest a vegetable or asks for some aspect which two different furrows have in common (described in input).

Input

The first line of input will contain 1 ≤ Q ≤ 3*105, the number of queries.

Each of the next Q lines will contain ? x y: 0 ≤ x, y ≤ 2*104, and ? is one of: + - v ^ ! \ with following meaning:

+: Plants vegetable of kind y to furrow number x (note that there will never be multiple vegetables of the same kind in the same furrow)

-: Harvests vegetable of kind y from furrow number x (note that there will always be a vegetable of that kind)

v: Finds out how many kinds of vegetables there are in furrows x and y.

^: Finds out how many kinds of vegetable are in both furrows (x, y)

!: Find out how many kinds of vegetables are in x and y BUT not in both of them at once.

\: Find out how many kinds of vegetable are in x but not in y

Output

For each query of the last four kinds, output the proper answer.

Example Input

10
+ 1 4
! 0 2
+ 0 2
\ 0 2
^ 0 1
v 2 0
+ 2 4
! 2 0
+ 1 0
! 0 2

Example Output

0
1
0
1
2
2

Example Input

15
+ 0 2
! 0 1
+ 1 1
v 0 1
+ 1 2
! 1 0
! 0 1
+ 0 0
v 0 1
^ 0 1
+ 1 3
\ 1 0
\ 1 0
+ 1 0
- 1 2

Example Output

1
2
1
1
3
1
2
2

Example Input

10
+ 2 1
! 3 1
! 3 1
+ 1 1
\ 2 0
+ 3 1
v 2 3
! 2 3
- 1 1
^ 1 2

Example Output

0
0
1
1
0
0

Added by:Morass
Date:2017-11-01
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2017-11-01 03:37:35 [Rampage] Blue.Mary
This problem needs some optimization, naive set operation will surely get TLE. I don't think it's necessary to change the time limit.
2017-11-01 03:31:32
Please tweak the time limit for Python/PyPy unless I'm being naive thinking it's a set operations problem.
2017-11-01 02:42:54 [Rampage] Blue.Mary
All examples contain extra lines.

Last edit: 2017-11-01 02:44:44
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.