마법 저울

잘 지켜지는 던전의 한 방에 보물이 잠겨 있다. 방의 문 앞에는 마법 저울과 N개의 추 한 세트가 있다. 저울에는 알 수 없는 목표 총무게 W가 정해져 있다. 다음 성질이 성립한다.

• 추의 부분집합 중에서 합이 정확히 W가 되는 것이 반드시 존재한다.
• 저울 위의 총무게가 정확히 W이면 문이 열리고 보물을 얻을 수 있다.
• 저울 위의 총무게가 W보다 작으면 아무 일도 일어나지 않는다.
• 보안 장치로, 저울 위의 총무게가 W를 초과하면 문이 영원히 잠긴다.

따라서 문을 반드시 열고 보물을 얻는 한 가지 방법은 N개 추의 모든 부분집합을 총무게가 증가하는 순서대로 시도하는 것이다. 그러나 여러 부분집합이 같은 총무게를 가질 수 있으므로, 주어진 총무게마다 부분집합 하나씩만 시도하는 편이 더 낫다.

모험가를 위해 가능한 총무게 중 처음 K개를 증가하는 순서대로 나열하고, 각 총무게에 대응하는 추의 부분집합을 하나씩 구해 주자.

• 첫째 줄에 정수 N이 주어진다.
• 둘째 줄에 정수 K가 주어진다.
• 셋째 줄에 N개의 추를 나타내는 N개의 정수가 공백으로 구분되어 주어진다.

가능한 총무게 중 처음 K개를 증가하는 순서대로, 각각에 대응하는 추와 함께 K개의 줄에 출력한다. K개 줄 각각의 형식은 다음과 같다.

total_weight: weight_1 weight_2 ... weight_p

여기서 weight_1 weight_2 ... weight_p는 합이 total_weight가 되는 p개의 추를 공백으로 구분해 나열한 것이다. 여러 가지가 가능하면 어느 것을 출력해도 된다.

주어진 입력에 대해 서로 다른 무게 합을 K개 이상 찾을 수 있음이 보장된다.

• 1 ≤ N ≤ 1000
• 1 ≤ K ≤ 1000
• 각 추는 [1, 1000000] 범위에 있다.