시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB3611932.143%

문제

당신은 칩을 만들기 위해 기판에 N개의 부품을 장착했다. 각각의 부품을 작동시키기 위해서는 전원을 연결해야 하는데, 기판에 연결할 수 있는 전원 선이 K개 밖에 없었다. 당신은 이 K개의 전원 선을 기판의 아래쪽에 연결하고, 기판의 위쪽에서 부품을 연결하여 전원을 나눠 쓰기로 하였다. 이때 다음과 같은 조건을 지켜야 한다.

  1. 한 개의 전원 선은 최대 두 개의 부품에만 사용될 수 있다.
  2. 기판의 위쪽에 연결한 전선들은 서로 꼬여서는 안 된다. 하지만 하나의 전선이 덮는 구역 안에 다른 전선이 연결될 수는 있다.
  3. 각각의 부품에는 그 부품의 중요도가 있다. 우리가 만든 칩의 중요도는, 한 개의 전원 선이 한 개의 부품에 연결될 때는 그 부품의 중요도를 제곱하여 더하고, 두 개의 부품에 연결될 때는 각 부품의 중요도를 곱한 것을 더한 값으로 표현된다. 이와 같은 중요도를 최대로 하는 칩을 만드는 것이 목적이다.

제일 왼쪽의 예는 기판의 위쪽에 연결한 전선이 꼬이는 경우로 올바르지 않은 경우이다. 두 번째 경우는 올바른 연결이지만 중요도가 최대가 아니다. 세 번째 경우는 올바른 경우이며, 중요도가 4 × 4 + 5 × 5 = 41로 최대가 되는 경우이다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 50), K(1 ≤ K ≤ 20)이 주어진다. 다음 줄에는 N개의 정수로 각 부품의 중요도가 차례로 주어진다. 부품의 중요도는 1,000 이하의 음이 아닌 정수이다.

출력

처음 K개의 줄에는 전원을 연결한 부품의 번호를 출력한다. 사용하지 않은 전원에 대해서는 0을 출력한다. 다음 N개의 줄에는 각 부품이 몇 번 부품과 전원을 공유하는지를 출력한다. 전원을 혼자 사용하는 경우에는 자기 자신을 출력하고, 전원을 사용하지 않는 경우에는 0을 출력한다.

예제 입력 1

5 2
2 3 4 4 5

예제 출력 1

4
5
0
0
4
3
5