E. Another GCD
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Note: this problem is different from "WTF Another GCD?". The difference is highlighted in bold.

In this task, you need to maintain a multiset $$$S$$$ that stores pairs of integers $$$(v,w)$$$.

Your multiset should support $$$n$$$ operations of the following types:

  • + v w: insert a pair $$$(v,w)$$$ into $$$S$$$.
  • - v w: remove a pair $$$(v,w)$$$ from $$$S$$$. It is guaranteed that $$$(v,w)$$$ exists in $$$S$$$. If there are multiple occurrences of the pair, remove only one occurrence.
  • ? k: This is a query. Find a pair $$$(v,w)$$$ in $$$S$$$ such that $$$v$$$ and $$$k$$$ are not coprime, and $$$w$$$ is maximised. You only need to output the value of $$$w$$$. More formally, find:

    $$$$$$\max(\{w~|~(v,w) \in S \land \gcd(v,k) \ne 1 \})$$$$$$

    where $$$\gcd(x,y)$$$ represents the largest integer that divides both $$$x$$$ and $$$y$$$.

    If no such pair exists, output $$$0$$$.

Input

The first line of each test contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of operations.

Each of the next $$$n$$$ lines describes an operation:

  • If the line begins with "+" or "-", it is followed by two integers $$$v$$$ and $$$w$$$ ($$$1 \le v \le 5 \cdot 10^5$$$, $$$1 \le w \le n$$$), describing an insertion/removal operation.
  • If the line begins with "?", it is followed by an integer $$$k$$$ ($$$1 \le k \le 5 \cdot 10^5$$$), describing a query.
Output

For each query, output one integer representing the maximum value of $$$w$$$ you found, or $$$0$$$ if no such $$$w$$$ exists.

Example
Input
8
+ 4 5
+ 3 4
? 2
? 3
- 3 4
? 4
+ 114514 8
? 3
Output
5
4
5
0