Description

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

与一般的三进制数不同的是，小江的三进制数从左往右书写。例如，在常规表述下，$4$ 的三进制表示为$(0000 0011)_3$ ，而在小江的三进制数表示下为 $(1100 0000……)_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$ 次操作。每次操作后，小江需要得到三进制串代表的数值。请你告诉她。

Format

Input

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

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

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

Output

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

Samples

4 3
1 1
2 0
1 2

7
6
15

提示

初始时，$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$。

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

python中一行输入两个整型数据可采用下列语句实现：

a,b=map(int,input().split())

来源

sxz