题目背景

为了提供更加良好的区分度，相较于蓝桥杯国赛，本场比赛的所有程序设计题添加了额外样例，请在附件处下载。

其中，后缀名为 $\bf{.in}$ 的文件为输入文件，$\bf{.out}$ 的文件为输出文件。您可以使用这些额外样例检验自己的程序正确性。但我们不保证通过额外样例一定能取得您期望的分数。

此外，我们提供了相较蓝桥杯国赛更多档的部分分，以确保分数分布更为科学合理。

题目描述

小洛正在学习三进制。他定义三进制数为每一位只包括 $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$ 次操作。每次操作后，小洛需要得到三进制串代表的数值。请你告诉他。

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

输入格式

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

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

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

输出格式

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

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$。

输入样例 #2

1 100
2 13
3 38
3 29
1 13
3 37
1 6
1 7
1 2
3 31
3 8
3 15
2 23
1 38
3 33
2 38
2 33
2 14
2 6
2 21
1 35
2 29
3 32
2 10
2 28
2 26
2 11
1 11
1 5
1 34
1 10
3 36
3 38
3 35
3 34
3 20
3 55
1 2
3 38
2 31
1 19
3 24
2 15
3 30
3 55
2 31
3 19
3 1
2 1
1 19
2 27
3 20
1 20
2 36
1 20
1 21
3 33
3 0
2 33
1 11
3 13
1 14
1 35
2 9
2 37
1 14
1 33
2 10
1 9
3 15
3 9
2 1
2 30
3 20
3 34
1 31
3 37
1 12
1 33
2 23
2 10
1 30
2 21
3 15
3 30
3 18
3 34
3 12
1 16
1 13
1 16
3 21
1 30
2 27
3 7
1 37
2 37
1 28
2 9
2 27
3 28

输出样例 #2

3188647
3188647
3188647
1
1
730
2917
2926
2926
2926
2926
188286360580
1350851905959352669
1350851905959352669
188286360580
11118309419471626
11118309429037564
11118309429036835
11118330349743241
61149875448742948
61287136203472714
61287136203472714
61287136203590812
61332889788500734
61337973520157392
61337973520511686
61337973520157392
61337973520157635
78015155219824204
78015155219706106
78015155219706106
78015155219706106
128046700318705813
144723882018372382
144723882018372382
144723882018372382
144723882018372391
144723882018372391
145959228810940285
145959229973201752
145959229973201752
145959230001899566
145959230001899566
145959230001899566
145341556605615619
145341557767877086
145341557767877086
145341557767877092
145341555443354158
145356806638324132
145356806638324132
145356810125108533
445546080719106775
445546084205891176
445546063285184770
439987002718629247
439987002718629248
434427942152073725
434427942152250872
434427942152250872
434427942142684934
334364851944685520
334364851944724886
1234932663726719612
1234932663731502581
1240491724298058104
1240491724298176202
1240491724298136836
1240491724283787929
1240491724283787929
1240491724283787926
1240903506547977224
1240903503061192823
1224226321361526254
1224843994757810201
774560088866812838
774560088867344279
780119149433899802
780119055290720975
780119055290661926
779707273026472628
779707293947179034
779707293961527941
779707293961527941
779707293961527941
796384475661194510
796384475661725951
796384475704772672
796384475706366995
796384475749413716
796384465289060513
796590356421155162
796582730823670175
796582730823672362
1246866636714669725
796582730823672362
796536977238762440
796536977238801806
796529351641316819
796529351641316819

输入样例 #3

0 100
3 32
3 18
3 22
1 12
2 32
1 18
1 17
3 27
1 13
3 38
1 26
1 14
3 10
1 33
2 25
2 27
2 6
3 35
1 11
1 35
1 9
3 37
2 5
2 12
3 35
3 29
3 6
1 20
2 10
2 30
2 10
1 12
1 35
2 12
1 9
2 4
2 27
2 31
3 25
3 24
2 36
1 1
3 38
2 6
2 29
3 17
2 19
1 31
3 5
1 3
2 2
1 0
1 7
2 33
2 26
1 12
2 16
1 38
1 35
3 4
1 31
1 21
3 17
3 28
3 8
2 27
2 11
2 22
2 21
1 25
1 18
1 25
3 31
1 14
3 20
2 3
1 10
3 31
3 18
2 36
1 1
1 19
3 6
1 25
1 33
1 32
3 0
1 16
2 28
3 10
2 26
3 26
3 18
2 14
3 18
2 11
3 10
2 4
3 18
2 23

输出样例 #3

0
0
0
531441
3706040378235123
3706040765655612
3706040894795775
3706040894795775
3706040896390098
3706040896390098
3708582762218427
3708582767001396
3708582767001396
9267643333556919
9269337910775805
9284589105745779
9284589105747237
9284589105747237
9284589105924384
59316134204924091
59316134204943774
59316134204943774
59316134204944260
59316134204412819
109347679303412526
109347679303412526
109347679303411797
109347682790196198
109347682790314296
109759465054503594
109759465054444545
109759465054975986
9696374856976572
9696374856445131
9696374856464814
9696374856464976
9688749258979989
10924096051547883
10923248762938440
10923248762938440
311112519356936682
311112519356936685
311112519356936685
311112519356935956
311249780111665722
311249780240805885
311249782565328819
310014435772760925
310014435772760682
310014435772760709
310014435772760727
310014435772760728
310014435772762915
304455375206207392
304452833340379063
304452833340910504
304452833427003946
1655304551099996035
1705336096198995742
1705336096198995661
1705953769595279608
1705953780055632811
1705953779926492648
1705953779926492648
1705953779926492648
1705946154329007661
1705946154328830514
1705946217090949732
1705946206630596529
1705947053919205972
1705947054306626461
1705945359729407575
1706563033125691522
1706563033130474491
1706563036617258892
1706563036617258865
1706563036617317914
1705945363221033967
1705945362833613478
1555850727536614357
1555850727536614360
1555850725212091426
1555850725212091426
1555851572500700869
1561410633067256392
1557704592689552710
1557704592689552711
1557704592603459269
1557750346188369191
1557750346188310142
1557755429919966800
1557752888054138471
1557752888441558960
1557752888436775991
1557752888049355502
1557752888049709796
1557752888049768845
1557752888049768764
1557752888437189253
1557753076723546907

【数据范围】

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

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