The Smart Beaver from ABBYY started cooperating with the Ministry of Defence. Now they train soldiers to move armoured columns. The training involves testing a new type of tanks that can transmit information. To test the new type of tanks, the training has a special exercise, its essence is as follows. Initially, the column consists of n tanks sequentially numbered from 1 to n in the order of position in the column from its beginning to its end. During the whole exercise, exactly n messages must be transferred from the beginning of the column to its end. Transferring one message is as follows. The tank that goes first in the column transmits the message to some tank in the column. The tank which received the message sends it further down the column. The process is continued until the last tank receives the message. It is possible that not all tanks in the column will receive the message — it is important that the last tank in the column should receive the message. After the last tank (tank number n ) receives the message, it moves to the beginning of the column and sends another message to the end of the column in the same manner. When the message reaches the last tank (tank number n - 1 ), that tank moves to the beginning of the column and sends the next message to the end of the column, and so on. Thus, the exercise is completed when the tanks in the column return to their original order, that is, immediately after tank number 1 moves to the beginning of the column. If the tanks were initially placed in the column in the order 1, 2, ..., n , then after the first message their order changes to n , 1, ..., n - 1 , after the second message it changes to n - 1, n , 1, ..., n - 2 , and so on. The tanks are constructed in a very peculiar way. The tank with number i is characterized by one integer a i , which is called the message receiving radius of this tank. Transferring a message between two tanks takes one second, however, not always one tank can transmit