ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Password Search

Time limit: 1.0 second
Memory limit: 64 MB
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 ≤ NM ≤ 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

inputoutput
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
To submit the solution for this problem go to the Problem set: 1547. Password Search