Cho bảng kích thước ~k \times n~, các hàng được đánh số từ ~1~ đến ~k~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Ô nằm ở hàng ~i~ và cột ~j~ ~\left(1 \le i \le k,\ 1 \le j \le n\right)~ gọi là ô ~(i, j)~.

Mỗi ô điền một số sao cho mỗi hàng là một hoán vị của ~1, 2, \ldots, n~. Gọi ~s_j~ là tổng ~k~ số trên cột ~j~.

Một bảng được gọi là đẹp nếu ~s_1, s_2, \ldots, s_n~ là một dãy số tự nhiên liên tiếp tăng dần, nghĩa là:

~s_j = s_{j-1} + 1 \quad \text{với mọi } 2 \le j \le n~.

Yêu cầu

Bạn được thực hiện không quá ~10^6~ phép đổi chỗ hai ô trên cùng một hàng. Hãy tìm một cách biến đổi để nhận được một bảng đẹp.

Input

• Dòng đầu chứa hai số nguyên dương ~k, n~.
• ~k~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên là một hoán vị của ~1, 2, \ldots, n~.

Output

• Dòng đầu chứa số nguyên ~t~ là số thao tác đổi chỗ, hoặc ghi ~-1~ nếu không thể biến đổi để nhận được bảng đẹp.
• Nếu biến đổi được, tiếp theo là ~t~ dòng, mỗi dòng chứa ba số ~i, j_1, j_2~ cho biết đổi chỗ hai số ở hai ô ~(i, j_1)~, ~(i, j_2)~.

Ràng buộc

• ~1 \le k \le 5~
• ~1 \le n \le 10^5~

Subtasks

• Subtask 1 (30%): ~k = 1,\ n \le 100~
• Subtask 2 (30%): ~k = 2,\ n \le 10~
• Subtask 3 (20%): ~n \le 100~
• Subtask 4 (20%): Không có ràng buộc nào thêm.

Ví dụ 1

Input

1 3
1 3 2

Output

1
1 2 3

Giải thích

Sau khi đổi chỗ hai phần tử ở cột ~2~ và ~3~ của hàng ~1~, ta được bảng:

~[1\ 2\ 3]~

Khi đó các tổng cột là ~1, 2, 3~, tạo thành một dãy liên tiếp tăng dần.

Ví dụ 2

Input

2 2
1 2
1 2

Output

-1

Giải thích

Không tồn tại cách biến đổi để nhận được một bảng đẹp.

Ví dụ 3

Input

2 3
1 2 3
1 2 3

Output

2
1 2 3
2 1 2

Giải thích

Sau hai phép đổi chỗ trên, ta nhận được bảng:

• Hàng 1: ~[1\ 3\ 2]~
• Hàng 2: ~[2\ 1\ 3]~

Khi đó các tổng cột là ~3, 4, 5~, là một dãy số liên tiếp tăng dần.