时间限制：1000ms　内存限制：512MB

题目描述

程老师的实验室角落里有一只培养皿，里面的菌群是他带了三年的宝贝。为了给菌群建立长期档案，观测员每天下午四点整准时记录一个整数 $x$，叫作"活性指数"。记录本已经写满了厚厚三大本，可程老师发现，这个指数从来不需要人工干预——它完全由培养仪按照一套固定的测定规则，一天一天地自行演化。

每天的规则只有两条，按顺序判断，执行一次就结束：

如果当前的 $x$ 是偶数，第二天的指数变为 $x / 2$（整除，因为偶数一定能被 $2$ 整除）；

如果当前的 $x$ 是奇数，第二天的指数变为 $x + c$，其中 $c$ 是这台培养仪固定的环境参数（一个正奇数）。

注意"执行一次就结束"：比如某天记录的是 $10$，它是偶数，第二天就变成 $5$；至于 $5$ 要不要继续变，那是第二天的事——第二天再以 $5$ 重新判断，它是奇数，若 $c = 3$ 就变成 $8$；第三天 $8$ 是偶数变成 $4$……指数就这样起起伏伏地往前走，每一天的值都由前一天的值唯一确定。

还有几个细节要交代清楚。环境参数 $c$ 是这台培养仪出厂时定死的，同一台仪器不会变，但不同仪器可能不一样，所以每次计算都得把 $c$ 当作输入读进来。记录从项目启动那天开始，启动当天的首次记录叫作"第 $0$ 天"，这一天的数值就是 $x_0$，还没有经过任何一次演化；之后每过一天，规则执行一次，天数加一——所谓"第 $T$ 天结束时"，指的就是规则恰好执行了 $T$ 次之后的那个值。观测员的工作说轻松也轻松：每天四点看一眼仪表盘，把数字誊到本子上就完事；可说枯燥也真枯燥——三年下来，他最大的心愿，就是有人能提前告诉他，这台机器往后还会吐出什么数来。

第 $0$ 天的初始指数是 $x_0$。程老师最近申请了一个超长周期的观测项目，他想知道：第 $T$ 天结束时，活性指数是多少。观测员翻着三大本记录直摇头：光是往前翻几十天，数值就忽大忽小没个章法；而 $T$ 可能大到 $10^{18}$——就算不吃不喝一天记一次，也轮不到人来记这一天，只能靠程序算了。

P.S.：$0$ 是偶数。环境参数 $c$ 保证是正奇数。

输入格式

一行三个整数 $x_0, c, T$，分别表示初始指数、环境参数和天数。

输出格式

一行一个整数，表示第 $T$ 天结束时的活性指数。

数据范围

• 特殊性质 A：保证从 $x_0$ 开始演化，序列里第一次出现"与之前某天相同"的值时，这个值就是 $x_0$ 本身。
• 特殊性质 B：保证从 $x_0$ 开始的前 $T$ 天演化中，活性指数没有重复出现过。
• 对于全部数据，$0 \le x_0 \le 10^9$，$1 \le c \le 10^6$，$c$ 为奇数，$0 \le T \le 10^{18}$。

样例

样例 1

输入：

7 5 4

输出：

8

解释：$x_0 = 7$，$c = 5$。逐天推演：第 $0$ 天是 $7$（奇数）→ 第 $1$ 天 $7 + 5 = 12$（偶数）→ 第 $2$ 天 $6$（偶数）→ 第 $3$ 天 $3$（奇数）→ 第 $4$ 天 $3 + 5 = 8$。所以第 $4$ 天结束时指数是 $8$。

样例 2

输入：

7 5 100

输出：

8

解释：接着样例 1 继续推演：第 $4$ 天是 $8$（偶数）→ 第 $5$ 天 $4$ → 第 $6$ 天 $2$ → 第 $7$ 天 $1$（奇数）→ 第 $8$ 天 $1 + 5 = 6$——注意，第 $2$ 天已经出现过 $6$ 了，此后序列按 $6, 3, 8, 4, 2, 1$ 循环，周期为 $6$，循环从第 $2$ 天开始。$(100 - 2) \div 6$ 余 $2$，对应循环里的第 $3$ 个值 $8$。

样例 3

输入：

0 3 10

输出：

0

解释：初始指数是 $0$，$0$ 是偶数，$0 / 2 = 0$——无论过多少天都停在 $0$。