Problem Description

For a non-negative integer variable $x$, the following is defined as one round of operation:

1. Increment $x$ by 1;
2. If $x$ is a multiple of 3, then divide $x$ by 3.

Given the initial values of $x$ and $k$, find the value of $x$ after $k$ rounds of operations.

Note that the large sample is not given as a file attachment but is directly placed in the Sample Input and Output section as Sample #3.

Input Format

A single line containing two non-negative integers $x$ and $k$.

Output Format

A single line containing a positive integer, representing the value of $x$ after $k$ rounds of operations.

Sample Input and Output

Sample Input #1

1 3

Sample Output #1

2

Sample Input #2

10 3

Sample Output #2

5

Sample Input #3

1919810 3

Sample Output #3

213313

Notes

Sample Explanation

For Sample #1, the changes in $x$ are as follows: $1 \rightarrow 2 \rightarrow (3 \rightarrow 1) \rightarrow 2$.

The part in parentheses represents one operation.

Data Range and Hints

For all test data, it is guaranteed that $0 \leq x, k \leq 10^{18}$.

Specifically, for test points $1\sim 2$, $k \leq 0$ is equivalent to $k = 0$, and similarly for $x$ in test points $3\sim 4$.

见题面 Input 部分

见题面 Output 部分