Ternary OR and Queries

For two nonnegative integers $X$ and $Y$, there exist integers $m$, $x_0$, $x_1$, $\cdots$, $x_m$, $y_0$, $y_1$, $\cdots$, $y_m$ that satisfy all of the following conditions.

• $m \ge 0$
• For every integer $i$ with $0 \le i \le m$, $0 \le x_i, y_i < 3$.
• $X = \sum_{i=0}^{m} x_i \cdot 3^i$
• $Y = \sum_{i=0}^{m} y_i \cdot 3^i$

Then the value of $OR_3(X,Y) := \sum_{i=0}^{m} \max(x_i, y_i) \cdot 3^i$ is uniquely determined.

Start with the set $S = \{ 0 \}$. Write a program that processes $M$ queries as follows.

• Type $1$ $x$: update the set $S$ to $S \cup \{ x \}$.
• Type $2$ $x$: print $\max_{a \in S} \left( OR_3(a,x) \right)$. In other words, for each element $a$ of the set $S$, compute $OR_3(a,x)$ and print the largest value.

Note that the queries are cumulative.

The first line contains $M$, the number of queries. $(1 \le M \le 500 000)$

From the second line onward, each of the next $M$ lines contains a query in the form $q$ $x$. $(1 \le q \le 2;$ $0 \le x < 3^{15})$

At least one query of type $2$ is given. All numbers in the input are integers.

For each query of type $2$, print the answer on its own line.

For real numbers $x$ and $y$, define $\max(x,y) = \begin{cases} x & (x \ge y) \\ y & (x < y) \end{cases}$.

$3^{15} = 14 348 907$.