Luka 在他的阁楼里发现了一个非常奇特的棋盘。令人惊讶的是，它由 $R \times C$ 个正方形格子组成。行从上到下依次编号为 $0$ 到 $R-1$，列从左到右依次编号为 $0$ 到 $C-1$。

这个棋盘的奇特之处在于格子的着色方式。每个格子要么是灰色，要么是白色：

• 白色：如果该格子的行号和列号在二进制表示下，在相同的位置上至少有一个二进制位同为 $1$。例如，格子 $(4, 5)$ 是白色的。
• 灰色：其他情况。例如，格子 $(2, 5)$ 是灰色的。

下图展示了一个大小为 $10 \times 10$ 的棋盘以及刺猬的移动路线。

Luka 的刺猬喜欢在这个奇特的棋盘上散步，而且散步的方式也很奇特。刺猬从格子 $(0, 0)$ 开始散步，并按照上图右侧所示的之字形（zig-zag）路线继续前行。在刺猬散步时，Luka 会计算它访问了多少个灰色格子。

在访问了 $K$ 个格子后，刺猬累了并睡着了。Luka 随后也去睡觉了，他为自己能够数出灰色格子的数量而感到高兴。

然而，如果提前知道棋盘的尺寸和数量 $K$，就可以编写一个程序来更快地计算出结果。这就是你的任务。

输入格式

第一行包含两个整数 $R$（$1 \le R \le 1\,000\,000$）和 $C$（$1 \le C \le 1\,000\,000$），表示棋盘的尺寸。

第二行包含一个整数 $K$（$1 \le K \le R \cdot C$），表示刺猬访问的格子总数。注意，这个数值可能无法用 32 位整数表示。

输出格式

输出刺猬访问的灰色格子数量。

子任务

在占总分 $50\%$ 的测试数据中，$K < 1\,000\,000$。

样例

输入样例 1

10 10
6

输出样例 1

5

输入样例 2

3 5
11

输出样例 2

8

输入样例 3

10 10
100

输出样例 3

51