题目描述

有一个长为 $r$ 宽为 $c$ 的矩形，将其划分为 $r\times c$ 个 $1\times 1$ 的小矩形。

行数从上到下从 $0$ 到 $r-1$ 编号，列数从左到右从 $0$ 到 $c-1$ 编号。

每个小矩形都有颜色，如果一个小矩形的行数为 $x$，列数为 $y$，则：

• 若 $x\oplus y=x+y$ 这个小矩形为灰色。
• 反之，则为白色。

下左图为 $r=c=10$ 的情况：

现在有人沿着上右图的轨迹沿着这个矩形走 $k$ 步，求他走了多少个灰色格子。

输入格式

第一行为两个整数 $r$ 和 $c$。

第二行为一个整数 $k$。

输出格式

一行，表示他走的灰色格子的个数。

10 10
6

5

3 5
11

8

10 10
100

51

提示

数据规模与约定

• 对于 $50\%$ 的数据，保证 $k\le 10^6$。
• 对于 $100\%$ 的数据，保证 $1\le r,c\le 10^6$，$1\le k\le r\times c$，答案在 $32$ 位整数范围之内。

说明：

题目译自 COCI2008-2009 CONTEST #1 JEZ，译者 @菜鸟一只。