JOIRIS

JOI 씨는 “JOIRIS”라는 게임을 좋아한다. 하지만 그는 이 게임을 잘하지 못한다. JOIRIS은 정사각형 칸으로 이루어진 격자인 직사각형 보드에서 진행된다. 보드의 너비는 N이고, 높이는 충분히 크다. 왼쪽에서 i번째 열이고 아래에서 j번째 행인 칸을 (i, j)로 나타낸다. 게임 도중 각 칸의 상태는 다음 중 하나이다. 그 칸에 블록이 있거나, 블록이 없다. JOIRIS은 다음과 같이 진행된다.

• 게임의 초기 상태를 나타내는 정수열 A1 , A2 , . . . , AN이 주어진다.

• 처음에 i번째 열에서(1 ≤ i ≤ N) 아래에서부터 Ai개의 각 칸에는 블록이 있고, 다른 칸에는 블록이 없다. 다시 말해, 1 ≤ j ≤ A_i인 각 칸 (i, j)에만 블록이 있다.

• 플레이어는 10 000개의 직사각형 조각을 가지고 있다. 각 조각은 1 × K개의 블록으로 이루어진 직사각형이다. 플레이어는 다음 연산을 반복해서 수행한다.

◦ 먼저 플레이어는 직사각형 조각의 방향을 선택한다. 방향은 세로 또는 가로이다. ◦ 플레이어가 세로 방향을 선택하면, 보드에 조각을 놓을 위치로 정수 x를 선택한다(1 ≤ x ≤ N). 그런 다음 x번째 열의 가장 위에 있는 블록 바로 위에 조각을 세로로 놓는다. 다시 말해, 칸 (x, y)에 블록이 있는 가장 큰 정수 y를 구하고(그러한 y가 없으면 y = 0을 사용한다), K개의 각 칸 (x, y + j)에 블록을 놓는다(1 ≤ j ≤ K). ◦ 플레이어가 가로 방향을 선택하면, 보드에 조각을 놓을 위치로 정수 x를 선택한다(1 ≤ x ≤ N − K + 1). 그런 다음 x번째 열부터 (x + K − 1)번째 열까지에서 가장 위에 있는 블록 바로 위에 조각을 가로로 놓는다. 다시 말해, 어떤 1 ≤ i ≤ K에 대해 칸 (x + i − 1, y)에 블록이 있는 가장 큰 정수 y를 구하고(그러한 y가 없으면 y = 0을 사용한다), K개의 각 칸 (x + i − 1, y + 1)에 블록을 놓는다(1 ≤ i ≤ K). ◦ 위 연산을 수행한 뒤, 한 행의 N개 칸이 모두 블록으로 채워져 있으면 그 행의 모든 블록이 사라진다. 그러면 그 행 위의 각 블록은 1칸 아래로 이동한다. 다시 말해, y번째 행의 모든 칸이 블록으로 채워져 있으면 칸 (i, j)의 상태가(1 ≤ i ≤ N, y ≤ j) 칸 (i, j + 1)의 상태로 동시에 갱신된다. 둘 이상의 행이 동시에 블록으로 채워져 있으면 이 연산을 아래에서부터 순서대로 수행한다.

JOIRIS의 목적은 조각을 최대 10 000번 놓아 보드에서 모든 블록을 제거하는 것이다. 하지만 JOI 씨는 이 게임을 잘하지 못하므로 이를 달성하는 방법을 모른다. 여러분의 임무는 조각을 최대 10 000번 놓아 보드에서 모든 블록을 제거할 수 있는지 판정하고, 가능하다면 이를 달성하는 방법을 찾는 것이다.

JOIRIS 보드의 초기 상태와 조각의 크기에 관한 정보가 주어질 때, 조각을 최대 10 000번 놓아 보드에서 모든 블록을 제거할 수 있는지 판정하고, 가능하다면 이를 달성하는 방법을 찾는 프로그램을 작성하라.

제약 조건

모든 입력 데이터는 다음 조건을 만족한다.

• 2 ≤ N ≤ 50.

• 1 ≤ K ≤ N.

• 0 ≤ Ai ≤ 50.

• 어떤 i에 대해 Ai = 0이다(1 ≤ i ≤ N).

• 어떤 i에 대해 Ai > 0이다(1 ≤ i ≤ N).

서브태스크

서브태스크 1 [15점] 다음 조건을 만족한다.

• K = 2.

• N은 짝수이다.

서브태스크 2 [15점] 다음 조건을 만족한다.

• K = 2.

• N은 홀수이다.

서브태스크 3 [15점] • N은 K로 나누어떨어진다.

서브태스크 4 [55점] 추가 제약 조건은 없다.

표준 입력에서 다음 데이터를 읽는다.

• 입력의 첫 번째 줄에는 공백으로 구분된 두 정수 N, K가 주어진다. 이는 JOIRIS의 보드 너비가 N이고, 직사각형 조각의 크기가 1 × K임을 의미한다.

• 이어지는 N개 줄의 i번째 줄에는(1 ≤ i ≤ N) 정수 Ai가 주어진다. 이는 게임의 초기 상태에서 i번째 열의 아래에서부터 Ai개의 각 칸에는 블록이 있고, 다른 칸에는 블록이 없음을 의미한다.

조각을 최대 10 000번 놓아 보드에서 모든 블록을 제거하는 것이 불가능하면, 한 줄에 정수 −1을 출력한다. 그렇지 않으면 출력은 X + 1개의 줄로 이루어지며, 여기서 X는 보드에 조각을 놓는 연산의 횟수이다.

• 출력의 첫 번째 줄에는 정수 X를 출력한다.

• 이어지는 X개 줄의 i번째 줄에는(1 ≤ i ≤ X) 보드에 놓을 i번째 조각의 정보를 다음 형식으로 출력한다.

◦ 플레이어가 조각을 세로로 놓는다면 공백으로 구분된 두 정수를 출력한다. 첫 번째 정수는 1이고, 두 번째 정수는 플레이어가 보드에 조각을 놓을 때 선택한 x이다. ◦ 플레이어가 조각을 가로로 놓는다면 공백으로 구분된 두 정수를 출력한다. 첫 번째 정수는 2이고, 두 번째 정수는 플레이어가 보드에 조각을 놓을 때 선택한 x이다.