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*10⁵, the number of queries.

Each of the next Q lines will contain ? x y: 0 ≤ x, y ≤ 2*10⁴, 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