Description

小洛正在学习三进制。他定义三进制数为每一位只包括 $0,1,2$ 三种数的无穷长的数字串 $a$。

与一般的三进制数不同的是，小洛的三进制数从左往右书写。例如，在常规表述下，$4$ 的三进制表示为 $(0000\ 0011)_3$，而在小洛的三进制数表示下为 $(1100\ 0000 \cdots)_3$。

小洛特别喜欢从 $0$ 开始计数，因此他规定三进制的第 $0$ 位为最左侧的那一数位。

下表给出了小洛的三进制数表示下，数字 $37$ 的最低的 $8$ 位数位以及位权：

现在小洛有一个十进制正整数 $V$（显然，需要将其转化为小洛的三进制数表示），并且给定三种操作：

• 操作一，将第 $i$ 位上的数进行操作：$0$ 变为 $1$，$1$ 变为 $2$，$2$ 变为 $0$。
• 操作二，将第 $i$ 位上的数进行操作：$0$ 变为 $2$，$1$ 变为 $0$，$2$ 变为 $1$。
• 操作三，将第 $i$ 位上的数进行操作：$1$ 变为 $2$，$2$ 变为 $1$，$0$ 不变。

小洛一共要进行 $q$ 次操作。每次操作后，小洛需要得到三进制串代表的数值。请你告诉他。

如果对题意有不清晰之处，请查看样例解释。

Input Format

第一行输入两个正整数 $V,q$。

接下来 $q$ 行，每行一个操作，形如 op i。

请注意，你需要将 $V$ 转化为三进制串并作为初始的三进制串。

Output Format

输出共 $q$ 行，第 $i$ 行表示第 $i$ 个操作后的答案。

4 3
1 1
2 0
1 2

7
6
15

Hint

【样例解释】

初始时，$V=4$，转化为小洛的三进制数为 $\texttt{1100 0000} \cdots$，接下来进行了 $3$ 次操作：

• 将第 $1$ 位上的数位从 $1$ 变为 $2$，三进制数变为 $\texttt{1200 0000} \cdots$，十进制下为 $7$。
• 将第 $0$ 位上的数位从 $1$ 变为 $0$，三进制数变为 $\texttt{0200 0000} \cdots$，十进制下为 $6$。
• 将第 $2$ 位上的数位从 $0$ 变为 $1$，三进制数变为 $\texttt{0210 0000} \cdots$，十进制下为 $15$。

【数据范围】

• 对于 $30\%$ 的数据，保证 $V\leq 10^9$。
• 对于另外 $30\%$ 的数据，保证不含操作三。

对于所有数据，保证 $0\leq V\leq 10^{18}$，$1\leq q\leq 10^5$，任意获取到的答案不超过 $2\times 10^{18}$。