Luka found a very unusual game board in his attic. Surprisingly, it consists of \(R \cdot C\) square cells. The rows are numbered \(0\) to \(R-1\) top to bottom and the columns \(0\) to \(C-1\) left to right.

What makes the board unusual is the way in which the cells are coloured. Each cell is either grey or white:

• white, if the row and column numbers of the cell, when represented in binary, have at least one digit \(1\) in the same position. For example, the cell \((4, 5)\) would be white.
• grey, otherwise. For example, the cell \((2, 5)\) would be grey.

Luka's hedgehog likes walking on this unusual board. The hedgehog starts his walk in the cell \((0, 0)\) and continues in a zig-zag (boustrophedon) pattern: it walks along row \(0\) from left to right, then steps down to row \(1\) and walks it from right to left, then row \(2\) from left to right again, and so on. While the hedgehog is walking, Luka counts how many grey squares it visited.

After visiting \(K\) squares, the hedgehog gets tired and falls asleep.

Knowing the dimensions of the board and the number \(K\) beforehand, write a program that calculates the result.

The first line contains two integers \(R\) (\(1 \le R \le 1\,000\,000\)) and \(C\) (\(1 \le C \le 1\,000\,000\)), the dimensions of the board.

The second line contains the integer \(K\) (\(1 \le K \le R \cdot C\)), the total number of squares the hedgehog visits. Note that this number may not fit in a 32-bit integer.

Output the number of grey cells the hedgehog visits.

Scoring: In test cases worth \(50\%\) of points, \(K\) will be less than \(1\,000\,000\).

riseoj 작성

출처 COCI 2008/2009 Contest 1