小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路，马路上有 n 个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这 n 个机器人工厂编号为 1~n，因为马路是环形的，所以第 n 个机器人工厂和第 1 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 n 段马路也编号为 1~n ，并规定第 i 段马路连接第 i 个机器人工厂和第 i+1 个机器人工厂（ 1 ≤ i ≤ n-1 ），第 n 段马路连接第 n 个机器人工厂和第 1 个机器人工厂。
游戏中，环形马路上不能同时存在 2 个或者 2 个以上的机器人，并且每个机器人最多能够在环形马路上行走 p 次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走次数可以为 1~p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小新 必须立刻 在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次数。
以下是游戏的一些补充说明：
1. 游戏从小新第一次购买机器人开始计时。
2. 购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。
3. 购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买完机器人并且设定机器人行走次数之后机器人才能行走。
4. 在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器人的花费不一定相同。
对于 40%的数据，2 ≤ n ≤ 40，1 ≤ m ≤ 40。 对于 90%的数据，2 ≤ n ≤ 200，1 ≤ m ≤ 200。 对于 100%的数据，2 ≤ n ≤ 1000，1 ≤ m ≤ 1000，1 ≤ p ≤ m。
对于 40%的数据，2 ≤ n ≤ 40，1 ≤ m ≤ 40。
对于 90%的数据，2 ≤ n ≤ 200，1 ≤ m ≤ 200。
对于 100%的数据，2 ≤ n ≤ 1000，1 ≤ m ≤ 1000，1 ≤ p ≤ m。
输入文件名为 game.in。
第一行 3 个正整数， n，m，p，意义如题目所述。