题目描述

对于非负整数变量 $x$，记以下为一轮操作：

1. 将 $x$ 增加 $1$；
2. 如果 $x$ 是 $3$ 的倍数，则将 $x$ 除以 $3$。

给定初始的 $x,k$，试求 $k$ 轮操作后 $x$ 的值。

输入格式

一行两个非负整数 $x,k$。

输出格式

一行一个正整数，表示 $k$ 轮操作后 $x$ 的值。

样例 #1

样例输入 #1

1 3

样例输出 #1

2

样例 #2

样例输入 #2

10 3

样例输出 #2

5

样例 #3

样例输入 #3

1919810 3

样例输出 #3

213313

提示

【样例解释】

对于样例一， $x$ 的变化过程如下：$1\rightarrow 2\rightarrow (3\rightarrow 1)\rightarrow 2$。

其中括号内为一次操作。

【数据范围与提示】

对于全部的测试数据，满足 $0\leq x,k\leq 10^{18}$。