After his trip to Japan, Vova has forgotten his password to Timus Online Judge.
Fortunately, students of the Ural State University have access to a powerful
multiprocessor computer MVS-1000, and Vova can be allowed to use M processors
for solving complex mathematical problems. Vova wants to use the supercomputer
for a simple search of passwords. He remembers that his password is no longer
than N symbols and consists of lowercase Latin letters.
First he wants to check all words of length 1 in the lexicographic order
(that is, a, b, …, z), then all words of length 2 in the same order
(that is, aa, ab, …, zz), and so on.
In order to use the supercomputer with maximal efficiency, the search must be
distributed equally between all processors: the first portion of words is
checked by the first processor, the second portion is checked by the second
processor, and so on. If it is impossible to distribute the work equally, let
the first several processors check one word more than the remaining processors.
Vova wants to know the range of words for each processor.
Input
The only line of the input contains the integers N and M
(1 ≤ N, M ≤ 50). It is guaranteed that
the number of words to be checked is no less than the number of processors.
Output
Output M lines. Each line must contain the range of words that will be
checked by the corresponding processor. See the required format in the sample.
Sample
input | output |
---|
5 4
| a-fssst
fsssu-mmmmn
mmmmo-tgggg
tgggh-zzzzz
|
Problem Author: Vladimir Yakovlev
Problem Source: The 11th Urals Collegiate Programing Championship, Ekaterinburg, April 21, 2007