Ông JOI rất thích trò chơi “JOIRIS”, nhưng lại không giỏi chơi trò này. JOIRIS được chơi trên một bảng hình chữ nhật chia thành các ô vuông. Bảng có chiều rộng \(N\) ô và chiều cao đủ lớn. Ô ở cột thứ \(i\) từ trái sang và hàng thứ \(j\) từ dưới lên được ký hiệu là \((i,j)\). Trong suốt trò chơi, mỗi ô hoặc chứa một khối vuông, hoặc để trống.

Trò chơi diễn ra như sau:

• Cho dãy số nguyên \(A_1,A_2,\ldots,A_N\) mô tả trạng thái ban đầu của bảng.
• Ban đầu, ở cột thứ \(i\) (\(1\le i\le N\)), mỗi ô trong \(A_i\) ô dưới cùng chứa một khối vuông; các ô còn lại đều trống. Nói cách khác, ô \((i,j)\) chứa khối vuông khi và chỉ khi \(1\le j\le A_i\).
• Người chơi có \(10\,000\) mảnh ghép hình chữ nhật, mỗi mảnh gồm \(1\times K\) khối vuông. Người chơi lặp lại thao tác đặt mảnh ghép theo quy tắc dưới đây.

Đầu tiên, người chơi chọn đặt mảnh ghép theo chiều dọc hoặc chiều ngang.

Nếu đặt theo chiều dọc, người chơi chọn một số nguyên \(x\) với \(1\le x\le N\), rồi đặt mảnh ghép thẳng đứng ngay phía trên khối vuông cao nhất trong cột \(x\). Cụ thể, gọi \(y\) là số nguyên lớn nhất sao cho ô \((x,y)\) chứa khối vuông; nếu cột này trống thì lấy \(y=0\). Đặt một khối vuông vào mỗi ô sau:

Nếu đặt theo chiều ngang, người chơi chọn một số nguyên \(x\) với \(1\le x\le N-K+1\), rồi đặt mảnh ghép nằm ngang ngay phía trên khối vuông cao nhất trong các cột từ \(x\) đến \(x+K-1\). Cụ thể, gọi \(y\) là số nguyên lớn nhất sao cho tồn tại \(i\) (\(1\le i\le K\)) mà ô \((x+i-1,y)\) chứa khối vuông; nếu tất cả các cột này đều trống thì lấy \(y=0\). Đặt một khối vuông vào mỗi ô sau:

Sau mỗi lần đặt, nếu cả \(N\) ô của một hàng đều chứa khối vuông, tất cả các khối vuông trong hàng đó biến mất. Sau đó, mỗi khối vuông phía trên hàng vừa xóa dịch xuống một ô. Nói cách khác, khi hàng \(y\) được lấp đầy, trạng thái của mọi ô \((i,j)\) với \(1\le i\le N\) và \(j\ge y\) được đồng thời thay bằng trạng thái của ô \((i,j+1)\). Nếu nhiều hàng cùng được lấp đầy, thực hiện việc xóa hàng theo thứ tự từ dưới lên.

Mục tiêu của JOIRIS là xóa hết các khối vuông trên bảng bằng không quá \(10\,000\) lần đặt mảnh ghép. Vì không giỏi trò chơi này, ông JOI không biết cách đạt được mục tiêu đó.

Yêu cầu

Cho trạng thái ban đầu của bảng và kích thước mảnh ghép, hãy xác định liệu có thể xóa hết các khối vuông trên bảng bằng không quá \(10\,000\) lần đặt hay không. Nếu có thể, hãy tìm một cách thực hiện.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,K\) cách nhau bởi một dấu cách: chiều rộng của bảng và kích thước \(1\times K\) của mỗi mảnh ghép.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1\le i\le N\)) chứa số nguyên \(A_i\): số ô dưới cùng chứa khối vuông ở cột \(i\) trong trạng thái ban đầu.

Dữ liệu ra

Nếu không thể xóa hết các khối vuông bằng không quá \(10\,000\) lần đặt, in số nguyên -1 trên một dòng.

Ngược lại, in \(X+1\) dòng, trong đó \(X\) là số lần đặt mảnh ghép và \(0\le X\le 10\,000\):

• Dòng đầu tiên chứa số nguyên \(X\).
• Dòng thứ \(i\) trong \(X\) dòng tiếp theo mô tả lần đặt thứ \(i\), theo đúng thứ tự thực hiện:
• In 1 x nếu đặt theo chiều dọc tại cột \(x\), với \(1\le x\le N\).
• In 2 x nếu đặt theo chiều ngang, bắt đầu tại cột \(x\), với \(1\le x\le N-K+1\).

Trong mỗi dòng mô tả thao tác, hai số nguyên được ngăn cách bởi một dấu cách. Sau khi thực hiện tất cả các thao tác và xóa các hàng đầy theo quy tắc, bảng phải hoàn toàn trống. Có thể in bất kỳ dãy thao tác hợp lệ nào thỏa mãn giới hạn; không cần tối thiểu hóa \(X\). Bộ chấm chỉ đánh giá đúng hoặc sai, không cho điểm dựa trên số lần đặt.

Ràng buộc

• \(2\le N\le 50\).
• \(1\le K\le N\).
• \(0\le A_i\le 50\) với mọi \(1\le i\le N\).
• Có ít nhất một chỉ số \(i\) (\(1\le i\le N\)) thỏa mãn \(A_i=0\).
• Có ít nhất một chỉ số \(i\) (\(1\le i\le N\)) thỏa mãn \(A_i>0\).

Phân nhóm

1. 15 điểm: \(K=2\) và \(N\) chẵn.
2. 15 điểm: \(K=2\) và \(N\) lẻ.
3. 15 điểm: \(N\) chia hết cho \(K\).
4. 55 điểm: Không có ràng buộc bổ sung.

Ví dụ

4 2
1
0
1
2

4
2 2
1 1
2 3
1 2

3 2
2
0
1

3
1 2
1 3
2 1

2 2
0
1

-1

5 3
1
0
1
0
1

9
1 4
1 5
2 1
2 1
2 2
1 1
1 2
2 3
2 3