Background

"Angels do not have vacations."
"Ah, again... It is better not to push yourself too hard."

Reprint authorization has been obtained.

Problem Description

For a non-negative integer variable $x$, define one round of operations as follows:

1. Increase $x$ by $1$.
2. If $x$ is a multiple of $3$, divide $x$ by $3$.

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

Note: The large sample is not provided as an attached file. Instead, it is placed directly in Sample #3 of the Input/Output Samples.

Input Format

One line with two non-negative integers $x, k$.

Output Format

One line with one positive integer, representing the value of $x$ after $k$ rounds of operations.

1 3

2

10 3

5

1919810 3

213313

Hint

[Sample Explanation]

For Sample 1, the change process of $x$ is as follows: $1\rightarrow 2\rightarrow (3\rightarrow 1)\rightarrow 2$.

The part in parentheses represents one operation.

[Constraints and Notes]

For all testdata, $0\leq x, k\leq 10^{18}$.

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

Translated by ChatGPT 5