칩 만들기

기판 위에 1번부터 N번까지 N개의 부품이 왼쪽에서 오른쪽 순서로 놓여 있다. 각 부품에는 0 이상의 정수인 중요도가 있다.

사용할 수 있는 전원 선은 K개뿐이다. 전원 선 하나는 한 부품에 직접 연결할 수 있고, 필요하면 같은 전원을 쓰는 다른 한 부품과도 연결할 수 있다. 따라서 전원 선 하나가 담당할 수 있는 부품 수는 최대 두 개다.

기판 위에 놓인 연결선들은 서로 교차하면 안 된다. 다만 한 연결선이 감싸는 구간 안에 다른 연결선이 놓이는 것은 허용된다.

칩의 중요도는 다음과 같이 계산한다.

1. 전원 선 하나가 부품 하나에만 연결되면, 그 부품의 중요도의 제곱을 더한다.
2. 전원 선 하나가 부품 두 개에 연결되면, 두 부품의 중요도를 곱한 값을 더한다.

조건을 만족하는 연결 중 칩의 중요도가 최대가 되는 구성을 출력하라.

첫째 줄에 두 정수 N(1 <= N <= 50), K(1 <= K <= 20)가 주어진다.

둘째 줄에는 N개의 정수가 주어진다. i번째 정수는 i번 부품의 중요도이며, 모든 중요도는 0 이상 1,000 이하이다.

처음 K개의 줄에는 각 전원 선에 직접 연결할 부품 번호를 출력한다. 사용하지 않는 전원 선은 0을 출력한다.

그다음 N개의 줄에는 각 부품이 어느 부품과 전원을 공유하는지 출력한다. 혼자 전원을 사용하면 자기 자신의 번호를 출력하고, 전원을 사용하지 않으면 0을 출력한다. 두 부품이 같은 전원을 공유한다면 두 부품은 서로의 번호를 출력해야 한다.

칩의 중요도가 최대가 되는 올바른 구성 중 하나를 출력하면 된다.