삼진논리 OR과 쿼리

음이 아닌 두 정수 $X$, $Y$에 대하여 다음 조건을 모두 만족하는 정수 $m$, $x_0$, $x_1$, $\cdots$, $x_m$, $y_0$, $y_1$, $\cdots$, $y_m$이 존재한다.

• $m \ge 0$
• $0 \le i \le m$을 만족하는 모든 정수 $i$에 대하여 $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$

이때 $OR_3(X,Y) := \sum_{i=0}^{m} \max(x_i, y_i) \cdot 3^i$의 값은 유일하게 결정된다.

집합 $S = \{ 0 \}$에 아래와 같은 $M$개의 쿼리를 수행하는 프로그램을 작성해 보자.

• 1 $x$: 집합 $S$를 $S \cup \{ x \}$로 갱신한다.
• 2 $x$: $\max_{a \in S} \left( OR_3(a,x) \right)$의 값을 출력한다. 즉, 집합 $S$의 각 원소 $a$에 대하여 $OR_3(a,x)$를 구하고, 그 최댓값을 출력한다.

쿼리가 누적해서 수행됨에 유의하여라.

첫째 줄에 쿼리의 개수 $M$이 주어진다. $(1 \le M \le 500 000)$

둘째 줄부터 $M$개의 줄에 걸쳐 쿼리가 $q$ $x$ 형태로 주어진다. $(1 \le q \le 2;$ $0 \le x < 3^{15})$

2번 쿼리는 하나 이상 주어진다. 입력으로 주어지는 모든 수는 정수이다.

2번 쿼리가 주어질 때마다 그 답을 한 줄에 하나씩 출력한다.

임의의 실수 $x$, $y$에 대하여 $\max(x,y) = \begin{cases} x & (x \ge y) \\ y & (x < y) \end{cases}$로 정의한다.

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