+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- 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 ```