题目描述

在数学研究实验室中，小$\tt Z$ 发现了一种特殊的无限整数序列，其生成规则如下：

• 序列的前三项定义为：$X_1 = 0$，$X_2 = A$，$X_3 = B$；
• 从第 $4$ 项开始，每个元素由递推关系生成：$X_i = X_{i-1} + X_{i-2} - X_{i-3}$（$i > 3$）。

这个序列展现出奇妙的数学规律，现在小$\tt Z$ 想知道：如果将这个无限序列中的所有元素按升序排列，第 $K$ 小的元素会是多少？

输入格式

输入一行三个的整数 $A$、$B$、$K$。

其中 $A, B$ 为序列的初始参数，$K$ 为需查询的排序位置。

输出格式

输出一个整数，表示排序后的第 $K$ 小的元素。

输入输出样例

18 13 2

13

样例 $\tt \#1$说明

• 生成的序列前几项为 $(0, 18, 13, 31, 26, 44, 39, \dots)$。
• 排序后的序列为 $(0, 13, 18, 26, 31, 39, 44, \dots)$，第$2$ 小的数是 $13$。

50 30 7

110

样例 $\tt \#2$说明

• 生成的序列前几项为 $(0, 50, 30, 80, 60, 110, 90, 140, \dots)$。
• 排序后的序列为 $(0, 30, 50, 60, 80, 90, 110, 120, \dots)$，第 $7$ 小的数是 $110$。

61 41 6

123

数据范围

• 对于$30\%$的数据，$1 \le A, B, K \le 100$。
• 对于另外$30\%$的数据，$A = B$。
• 对于$100\%$的数据，$1 \le A, B, K \le 10^9$。