#1498. 进制

进制

题目描述

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

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

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

下表给出了小洛的三进制数表示下,数字 3737 的最低的 88 位数位以及位权:

三进制数表示 11 00 11 00
位数 00 11 22 33 44 55 66 77
位权 303^0 313^1 323^2 333^3 343^4 353^5 363^6 373^7

现在小洛有一个十进制正整数 VV(显然,需要将其转化为小洛的三进制数表示),并且给定三种操作:

  • 操作一,将第 ii 位上的数进行操作:00 变为 11,11 变为 22,22 变为 00。
  • 操作二,将第 ii 位上的数进行操作:00 变为 22,11 变为 00,22 变为 11。
  • 操作三,将第 ii 位上的数进行操作:11 变为 22,22 变为 11,00 不变。

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

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

输入格式

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

接下来 qq 行,每行一个操作,形如 op i。

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

输出格式

输出共 qq 行,第 ii 行表示第 ii 个操作后的答案。

样例

4 3
1 1
2 0
1 2
7
6
15

题目来源:洛谷 P10510