Infinitely Long Ternary Number Operations

Little Luo is studying ternary numbers. He defines a ternary number as an infinitely long string of digits, where each digit is one of \(0,1,2\). Unlike the usual ternary representation, Little Luo writes his ternary number from left to right. In his representation, the left‐most (i.e. position 0) digit has weight \(3^0\), the next digit has weight \(3^1\), and so on.

For example, the usual ternary representation of \(4\) is \((0011)_3\), but in Little Luo's representation it is \((11\,00\,00\,\dots)_3\) because the digits are written from left to right.

Given a positive decimal integer \(V\), convert it into Little Luo's ternary representation (note that because \(V\) is finite, only a finite number of digits on the left are nonzero; all digits at positions greater than or equal to the length of the representation are \(0\)). Then, you are given \(q\) operations. In each operation, one of the following three operations is performed on the digit at position \(i\) (where position 0 is the left‐most digit):

• Operation 1: Change the digit according to \(0 \to 1,\; 1 \to 2,\; 2 \to 0\).
• Operation 2: Change the digit according to \(0 \to 2,\; 1 \to 0,\; 2 \to 1\) (i.e. subtract 1 modulo 3).
• Operation 3: Change the digit according to: \(0\) remains \(0\); \(1 \to 2\); \(2 \to 1\) (i.e. swap \(1\) and \(2\)).

After each operation, recompute and output the decimal value represented by the new ternary string, i.e., \[ V = \sum_{i \ge 0} a_i \times 3^i \] where \(a_i\) is the digit at position \(i\). If an operation is applied on a digit position that is beyond the current length of the representation, consider its current digit as \(0\) (and extend the representation accordingly).

If any part of the statement is unclear, please refer to the sample explanations.

inputFormat

The input begins with two integers \(V\) and \(q\) (\(V \gt 0\)), where \(V\) is the initial decimal number and \(q\) is the number of operations.

Each of the next \(q\) lines contains two integers \(op\) and \(i\), where \(op\) is one of {1, 2, 3} representing the type of operation, and \(i\) (\(\ge 0\)) is the digit position (with position 0 being the left‐most digit) on which the operation is applied.

outputFormat

After each operation, output the new decimal value represented by the ternary number on a separate line.

sample

37 3
1 2
3 3
2 0

46
73
72