시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 13 8 7 58.333%

문제

An empty train on a train station is waiting for passengers to board. The train consists of N cars and each car can accommodate K passengers. 

The train station is swamped with strange demands. Passengers board the train one by one and go to one of the cars in which there are free seats left. Each passenger chooses a car to board according to the following rules: 

  1. Of all the cars which are not full, the passenger chooses the one which has the fewest passengers whose names start with the same letter as his. 
  2. If there are multiple cars which have the same fewest number of such passengers, the passenger chooses the one with the smallest total number of passengers. 
  3. If there are still multiple cars, the passenger boards the first of these. 

Write a program that, given the list of passengers which are boarding the train, determines the number of passengers in each car after boarding has completed. 

입력

The first line contains two integers N and K, 1 ≤ N ≤ 10, 1 ≤ K ≤ 10, the number of cars and the number of passengers each car can accomodate. 

The second line contains an integer P, 1 ≤ P ≤ N·K, the number of passengers waiting to board. 

The next P lines contain the names of all passengers, in order in which they will board. The name of each passenger is a string of at most 10 lowercase letters of the English alphabet. No two passengers will have the same name. 

출력

Output N integers separated by single spaces on a single line, the number of passengers in each car, in order from first car to last. 

예제 입력

3 2
3
anka
branko
cvjetko

예제 출력

1 1 1

힌트

When Anka is boarding, the train is empty; according to rules 1 and 2 she can choose any car, so she chooses the first car according to rule 3. Rule 1 also allows Branko to entery any car, but rule 2 limits him to the second and third. By rule 3 he enters the second car. Cvjetko enters the third car by rule 3, since it is empty.