Ma trận nguyên ~A~ kích thước ~n \times m~ là một tập hợp gồm ~n \times m~ số nguyên được xếp trên ~n~ dòng và ~m~ cột. Để biểu diễn một ma trận trong máy tính, ta có thể sử dụng cấu trúc dữ liệu mảng hai chiều. Tuy nhiên cách biểu diễn thuần tuý này có chi phí lưu trữ rất lớn là ~n \times m~. Trong một số trường hợp ma trận đặc biệt, người ta có thể biểu diễn ma trận theo dạng gọn hơn.

Ma trận hạng 1 là ma trận ~A = \{a_{ij}\}_{n \times m}~ thoả mãn tính chất sau: tồn tại dãy số nguyên ~u_1, u_2, \dots, u_n~ và ~v_1, v_2, \dots, v_m~ sao cho với mọi ~1 \le i \le n, 1 \le j \le m~, luôn có ~a_{ij} = u_i \cdot v_j~. Với tính chất như trên, ta có thể lưu trữ một ma trận hạng 1 với chi phí lưu trữ chỉ là ~n + m~ bằng cách lưu trữ hai dãy ~\{u_i\}~ và ~\{v_j\}~.

Hãy tìm một biểu diễn dạng gọn của ma trận hạng 1 cho trước ~A~. Nếu có nhiều phương án hợp lệ, in ra phương án có tổng ~u_1 + u_2 + \dots + u_n + v_1 + v_2 + \dots + v_m~ nhỏ nhất.

Yêu cầu: Tìm dãy ~u~ và ~v~ thỏa mãn điều kiện trên sao cho tổng các phần tử là nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, m~ là kích thước (số dòng và số cột) của ma trận ~A~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên ~a_{i1}, a_{i2}, \dots, a_{im}~ (~1 \le a_{ij} \le 10^{12}~) mô tả dòng thứ ~i~ của ma trận ~A~.

Output

• Dòng đầu tiên chứa ~n~ số nguyên mô tả dãy ~u_1, u_2, \dots, u_n~.
• Dòng tiếp theo chứa ~m~ số nguyên mô tả dãy ~v_1, v_2, \dots, v_m~.
• Nếu có nhiều đáp án hợp lệ, in ra một đáp án bất kỳ. Dữ liệu đảm bảo luôn có ít nhất một lời giải hợp lệ.