3552 -- Snatch!

The company Supersafe produces a safe with a combination lock. The lock of this safe consists of N cylinders on a common axis. Each cylinder revolves on this axis independently of other cylinders. The are numbers from 1 to M in a circle on each cylinder. At any time, one of these numbers is visible in a special window on the door of the safe. Thus it is possible to enter numbers by rotating the cylinders. Accordingly, the code of the safe is a sequence of N numbers, each number belonging to the interval from 1 to M.

As a rule, such safes have a mechanism for opening them in the case the code is forgotten or lost. For this model, the mechanism has two components:

a key which is unique for each safe and kept by the owner. This key can be put in a keyhole only when the number 1 is entered on the first cylinder. After that, all the cylinders of the lock can be turned around only simultaneously (at the same time) by the same angle;
a universal technological code which is common for all safes. This code is known to a specialist of the company Supersafe, who should be invited to open the safe. It is known that the technological code starts with the number 1.

The process of opening the safe is as follows. The specialist enters the technological code (not allowing the owner to see the code, of course), puts in the key, and then turns all cylinders until – click – the safe unlocks. After that, the specialist takes out the key and mixes up the obtained code by entering random numbers on all the cylinders.

You want to open one of such safes without the owner’s knowledge. For this purpose, you have obtained a copy of the safe key and found out that:

after entering the technological code, putting in the key, and turning cylinders, the safe opens when the sum of numbers appearing in windows is maximal;
the correct technological code, selected from all codes starting with the number 1, has the least value of such sum.

It remains to determine the technological code.