进制

小洛正在学习三进制。他定义三进制数为每一位只包括 $0,1,2$ 三种数的**无穷长的**数字串 $a$。 与一般的三进制数不同的是，小洛的三进制数从左往右书写。例如，在常规表述下，$4$ 的三进制表示为 $(0000\ 0011)_3$，而在小洛的三进制数表示下为 $(1100\ 0000 \cdots)_3$。 小洛特别喜欢从 $0$ 开始计数，因此他规定三进制的第 $0$ 位为最左侧的那一数位。 下表给出了小洛的三进制数表示下，数字 $37$ 的最低的 $8$ 位数位以及位权： | 三进制数表示 | $1$ | $0$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 位数 | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | | 位权 | $3^0$ | $3^1$ | $3^2$ | $3^3$ | $3^4$ | $3^5$ | $3^6$ | $3^7$ | 现在小洛有一个十进制正整数 $V$（显然，需要将其转化为小洛的三进制数表示），并且给定三种操作： - 操作一，将第 $i$ 位上的数进行操作：$0$ 变为 $1$，$1$ 变为 $2$，$2$ 变为 $0$。 - 操作二，将第 $i$ 位上的数进行操作：$0$ 变为 $2$，$1$ 变为 $0$，$2$ 变为 $1$。 - 操作三，将第 $i$ 位上的数进行操作：$1$ 变为 $2$，$2$ 变为 $1$，$0$ 不变。 小洛一共要进行 $q$ 次操作。每次操作后，小洛需要得到三进制串代表的数值。请你告诉他。 如果对题意有不清晰之处，请查看样例解释。 ## Input 第一行输入两个正整数 $V,q$。 接下来 $q$ 行，每行一个操作，形如 `op i`。 请注意，你需要将 $V$ 转化为三进制串并作为初始的三进制串。 ## Output 输出共 $q$ 行，第 $i$ 行表示第 $i$ 个操作后的答案。 [samples] ## Background 为了提供更加良好的区分度，相较于蓝桥杯国赛，本场比赛的所有程序设计题添加了额外样例，请在附件处下载。 其中，后缀名为 $\bf{.in}$ 的文件为输入文件，$\bf{.out}$ 的文件为输出文件。您可以使用这些额外样例检验自己的程序正确性。但我们不保证通过额外样例一定能取得您期望的分数。 此外，我们提供了相较蓝桥杯国赛更多档的部分分，以确保分数分布更为科学合理。 ## Note **【样例解释】** 初始时，$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}$。