Background

To provide better differentiation, compared with the Lanqiao Cup national finals, all programming problems in this contest include additional samples. Please download them from the attachment.

Files with the suffix $\bf{.in}$ are input files, and those with the suffix $\bf{.out}$ are output files. You can use these additional samples to check the correctness of your program. However, we do not guarantee that passing the additional samples will necessarily give you the score you expect.

In addition, we provide more partial-score tiers than the Lanqiao Cup national finals to make the score distribution more scientific and reasonable.

Problem Description

Xiao Luo is learning ternary. He defines a ternary number as an infinitely long digit string $a$ where each digit is only one of $0,1,2$.

Different from ordinary ternary numbers, Xiao Luo’s ternary numbers are written from left to right. For example, in the usual notation, the ternary representation of $4$ is $(0000\ 0011)_3$, but in Xiao Luo’s notation it is $(1100\ 0000 \cdots)_3$.

Xiao Luo especially likes counting starting from $0$, so he defines the $0$-th digit of the ternary number to be the leftmost digit.

The table below shows, in Xiao Luo’s ternary notation, the lowest $8$ digits of the number $37$ and their place values:

Now Xiao Luo has a positive decimal integer $V$ (obviously, it needs to be converted into Xiao Luo’s ternary representation), and there are three kinds of operations:

• Operation 1: operate on the digit at index $i$: $0$ becomes $1$, $1$ becomes $2$, $2$ becomes $0$.
• Operation 2: operate on the digit at index $i$: $0$ becomes $2$, $1$ becomes $0$, $2$ becomes $1$.
• Operation 3: operate on the digit at index $i$: $1$ becomes $2$, $2$ becomes $1$, $0$ stays unchanged.

Xiao Luo will perform $q$ operations in total. After each operation, he needs to obtain the value represented by the ternary string. Please tell him the answer.

If anything is unclear, please refer to the sample explanation.

Input Format

The first line contains two positive integers $V,q$.

The next $q$ lines each contain one operation in the form op i.

Note that you need to convert $V$ into a ternary string and use it as the initial ternary string.

Output Format

Output $q$ lines in total. The $i$-th line should be the answer after the $i$-th operation.

4 3
1 1
2 0
1 2

7
6
15

Hint

【Sample Explanation】

Initially, $V=4$. After converting, Xiao Luo’s ternary number is $\texttt{1100 0000} \cdots$. Then $3$ operations are performed:

• Change the digit at index $1$ from $1$ to $2$. The ternary number becomes $\texttt{1200 0000} \cdots$, which is $7$ in decimal.
• Change the digit at index $0$ from $1$ to $0$. The ternary number becomes $\texttt{0200 0000} \cdots$, which is $6$ in decimal.
• Change the digit at index $2$ from $0$ to $1$. The ternary number becomes $\texttt{0210 0000} \cdots$, which is $15$ in decimal.

【Constraints】

• For $30\%$ of the testdata, $V\leq 10^9$ is guaranteed.
• For another $30\%$ of the testdata, it is guaranteed that there is no operation 3.

For all testdata, $0\leq V\leq 10^{18}$, $1\leq q\leq 10^5$, and any obtained answer does not exceed $2\times 10^{18}$.

Translated by ChatGPT 5