• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

Jeff got bored in Semnan and decided to pass his time thinking about gcd. We define $gcd(a, b)$ as the greatest common divisor of two natural numbers $a$ and $b$. Jeff defines $F(X, Y)$ between two non empty lists $X_1$, $X_2$, ..., $X_n$ and $Y_1$, $Y_2$, ..., $Y_m$ like this:

$$F(X, Y) = max(gcd(X_i, Y_j)) \quad 1 \leq i \leq n, 1 \leq j \leq m$$

In other words, $F(X, Y)$ is the greatest gcd between one member of the $X$-list and another member from $Y$-list. if one of the $X$ or $Y$ is empty consider $F(X, Y) = 1$.

Sehri decides to make Jeff's life harder by inserting and deleting numbers in Jeff's lists $Q$ times. more formally for each $$1 \le i \le Q$$Sehri chooses one of lists $X$ or $Y$ and a number $n_i$, then decides to add $n_i$ to the chosen list or remove one of the occurrences of $n_i$ in the chosen list. After each of Sehri's attempts to make Jeff's life harder, Jeff wonders what is $F(X, Y)$ and since his life is hard enough already, he asks you to calculate $F(X, Y)$ for him. the lists $X$, $Y$ are empty at first. note that it is garanteed that Sehri will always remove an existing $n$.

input

the first line consists $Q$ number of Sehri's attempts. for the next Q lines, i-th line consists of a character '+' or '-' to denote Sehri decided to insert or delete a number. then another character 'X' or 'Y' shows which list Sehri has chosen and then the number $n_i$.

$$1 \le Q \le 100,000$$

$$1 \le n_i \le 1000,000$$

output

output should consist of Q number F(X, Y) after each of Sehri's attempts.

example

sample input 1

6
+ X 3
+ Y 1
+ Y 6
+ X 12
- Y 1
+ Y 12

sample output 1

1
1
3
6
6
12