V, q = map(int, input().split())

# s 用来存储 V 转换为三进制后的每一位，列表中的索引对应三进制的位数
s = []

# n 用以记录 V 的三进制位数
n = 0

# 将 V 转换为三进制数表示，并存储在列表 s 中
while V > 0:
    s.append(V % 3)
    V = V // 3
    n += 1

# 扩充列表 s 到足够的长度，以确保即便后续有高位的操作也能正确执行
for i in range(1000):
    s.append(0)

# 处理 q 次操作
for j in range(q):
    op, i = map(int, input().split())
    # 更新 n，保证 n 始终为操作的最大位数
    n = max(n, i)
    # 操作一：s[i] 的值按照 0→1→2→0 循环变化
    if op == 1:
        s[i] = (s[i] + 1) % 3
    # 操作二：s[i] 的值按照 0→2→1→0 循环变化
    if op == 2:
        s[i] = (s[i] + 2) % 3
    # 操作三：s[i] 的值在 1 和 2 之间变化，0保持不变
    if op == 3:
        if s[i] == 1:
            s[i] = 2
        elif s[i] == 2:
            s[i] = 1

    # 操作完后，计算从三进制数转换回十进制后的结果
    res = 0
    k = 1
    for i in range(n + 1):
        res += k * s[i]
        k = k * 3
    # 输出每次操作后的三进制数对应的十进制数
    print(res)