#1187 짐 나르기

10  10 s   128 MB  

Description

한 항구에 적재되어야 할 많은 컨테이너들이 있다. 이 컨테이너들은 색상을 가지며 이 색상에 의해 구분되어진다. 각 색상은 컨테이너의 종류를 나타내기 위한 것이다. 컨테이너 이 색상은 알파벳 값으로 주어진다. 드디어 컨테이너를 적재하는 시간이 되었다. 준비된 컨테이너들 중 몇 개를 타이타닉호에 적재해야 한다. 세준이 컨테이너를 적재할 차례가 되었는데 컨테이너들이 너무 많아서 무엇을 가지고 가야할지 고민하고 있다. 현재 항구에 남아있는 컨테이너의 총 개수와 그 종류, 그리고 세준이 적재할 컨테이너의 수가 주어졌을 때 컨테이너를 고르는 방법들을 모두 구하는 것이다. 단, 반드시 주어지는 수 만큼의 컨테이너를 골라야 한다.

Input

입력은 두 줄로 이뤄진다.
첫 번째 줄에 컨테이너의 수 n과 고를 컨테이너의 수 k가 차례로 빈칸으로 구분되어 주어진다.(1≤k≤40,1≤n≤7).
다음 줄에는 준비된 파일의 이름(영문 소문자 하나) n개가 빈칸 하나로 구분되어 주어진다.
같은 색의 컨테이너가 여럿 존재할 수도 있다. 또한 같은 색의 컨테이너는 순차적으로 정렬이 되어 입력된다.

Output

첫 번째 줄에 가능한 방법의 수 m을 출력한다.
다음 m개의 줄에는 컨테이너를 고르는 방법을 하나씩 출력한다. 각 줄에는 고른 컨테이너의 이름들을 빈칸으로 구분하여 출력한다. 한 줄에 출력되는 컨테이너들은 알파벳순으로 출력하며, 각각의 방법들도 사전 순서대로 출력되어야 한다.

Sample Input

Sample Output

10 2
a a a b b c c c d e
13
a a
a b
a c
a d
a e
b b
b c
b d
b e
c c
c d
c e
d e

Source

정보올림피아드 알고리즘 자료집(경기도교육정보연구원)