Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3836
Circulation pipe

Time Limit: 4 Seconds      Memory Limit: 65536 KB

Darkgy is a transport pipe master. One day, due to some strange redstone signal, an Iron pipe changed its direction and make a part of the pipe system become a circulation pipe.

The circulation pipe consists of L unit pipe numbered from 0 to L-1. Every K ticks, an item will input into pipe 0, and it will be transported in pipes with 1 unit pipe length per tick speed from pipe 0 to pipe L-1. When it was transported into pipe L-1, its direction will reversed and will be transported from L-1 to 0. When it reached pipe 0, its direction will be reversed again.

This process will repeat until the moment when there are more than C items in one of the L pipes, C is the capacity of each pipe.

For example, if L=5, K=3, C=1.

In tick 0, the first item will input into pipe 0.

In tick 3, it will be transported into pipe 3 and the second item will input into pipe 0.

In tick 4, the first item reached pipe 4 and its direction reversed, at the same time, the second item moved into pipe 1.

In tick 6, the third item appeared in pipe 0, the first item moved into pipe 2 while the second item was in pipe 3. Though the first item and the second item crossed, but......it does not matter XD.

In tick 7, the first item and the third item meet in pipe 1, and pipe 1 blast.

Darkgy want to know in which tick, the circulation pipe will blast.


There are large amount of test cases, for each test case, there will be only one line with 3 integers 1 ≤ L, K, C ≤ 104 which was mentioned in the description.


For each test case, you should output only one line with an integer T which means the tick when circulation pipe was blast.

Sample Input

5 3 1
1 1 1
1 1 2
1 1 3

Sample Output


Author: QIAN, Yanliang
Source: ZOJ Monthly, November 2014
Submit    Status