Cho một bàn cờ gồm ~n~ hàng và ~m~ cột. Ô ở hàng ~i~, cột ~j~ chứa ~a_{i,j}~ quân cờ.

Một trạng thái của bàn cờ được gọi là hợp lệ nếu với mọi hai ô kề nhau theo cạnh, tổng số quân cờ trong hai ô đó là số lẻ.

Cụ thể, với mọi chỉ số hợp lệ:

• ~a_{i-1,j} + a_{i,j}~ là số lẻ.
• ~a_{i,j-1} + a_{i,j}~ là số lẻ.

Trong một lượt, người chơi có thể thêm đúng một quân cờ vào một ô bất kỳ. Từ trạng thái ban đầu, hãy thực hiện một số lượt, có thể bằng ~0~, để đưa bàn cờ về trạng thái hợp lệ.

Trong các cách thực hiện hợp lệ, ưu tiên:

1. Tổng số quân cờ trên bàn sau cùng là nhỏ nhất.
2. Nếu vẫn có nhiều đáp án, ma trận kết quả phải nhỏ nhất theo thứ tự từ điển.

Hai ma trận được so sánh theo thứ tự từ điển bằng cách đọc lần lượt từng hàng từ trên xuống dưới, trong mỗi hàng đọc từ trái sang phải. Tại vị trí đầu tiên khác nhau, ma trận có giá trị nhỏ hơn là ma trận nhỏ hơn theo thứ tự từ điển.

Yêu cầu

Hãy in ra ma trận hợp lệ đạt tổng số quân cờ nhỏ nhất. Nếu có nhiều ma trận như vậy, in ra ma trận nhỏ nhất theo thứ tự từ điển.

Dữ liệu

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ là số hàng và số cột của bàn cờ.

~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên. Số thứ ~j~ trên dòng thứ ~i~ là ~a_{i,j}~, số quân cờ ban đầu tại ô ~\left(i,j\right)~.

Kết quả

In ra ~n~ dòng, mỗi dòng gồm ~m~ số nguyên.

Số thứ ~j~ trên dòng thứ ~i~ là ~b_{i,j}~, số quân cờ tại ô ~\left(i,j\right)~ sau khi thực hiện các lượt đi.

Ma trận ~b~ phải thỏa mãn:

• ~b_{i,j} \ge a_{i,j}~ với mọi ~i, j~.
• Tổng trên mọi cặp ô kề nhau theo cạnh là số lẻ.
• ~\sum b_{i,j}~ là nhỏ nhất.
• Trong các ma trận thỏa mãn các điều kiện trên, ~b~ nhỏ nhất theo thứ tự từ điển.

Ví dụ

Ví dụ ~1~

Input

2 3
1 1 2
2 2 3

Output

2 1 2
3 2 3

Giải thích

Ví dụ ~1~

Thêm một quân cờ vào mỗi ô ~\left(1,1\right)~ và ~\left(2,1\right)~.

Ma trận thu được là:

2 1 2
3 2 3

Tổng trên mọi cặp ô kề nhau theo cạnh đều là số lẻ. Đây là ma trận hợp lệ có tổng số quân cờ nhỏ nhất.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n, m \le 100~.
• ~0 < a_{i,j} \le 10^9~.

Chấm điểm

Cho ~n~ chiếc đinh trên một tấm ván. Đinh thứ ~i~ có tọa độ ~\left(x_i, y_i\right)~. Không có hai chiếc đinh nào trùng vị trí.

Có đúng hai sợi chỉ, và ban đầu cả hai đều được buộc tại đinh ~1~. Mỗi sợi chỉ có thể lần lượt được buộc thêm vào một số đinh.

Nếu một sợi chỉ vừa được buộc tại đinh ~i~, lần buộc tiếp theo của sợi đó chỉ được thực hiện tại một đinh ~j~ thỏa mãn ~j > i~. Nói cách khác, dãy chỉ số các đinh mà mỗi sợi chỉ đi qua phải tăng строго ngặt.

Mỗi chiếc đinh phải được sử dụng bởi ít nhất một trong hai sợi chỉ. Một đinh có thể được sử dụng bởi cả hai sợi chỉ.

Độ dài của một đoạn chỉ nối giữa hai đinh ~i~ và ~j~ là:

~d(i,j) = \sqrt{(x_i-x_j)^2+(y_i-y_j)^2}~.

Tổng chiều dài chỉ là tổng độ dài các đoạn nối giữa hai lần buộc liên tiếp trên mỗi sợi chỉ.

Yêu cầu

Hãy xác định tổng chiều dài nhỏ nhất của hai sợi chỉ sao cho mọi đinh đều được sử dụng ít nhất một lần.

Dữ liệu

Dòng đầu tiên chứa số nguyên ~n~ là số lượng đinh.

~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i~ và ~y_i~, là tọa độ của đinh thứ ~i~.

Kết quả

In ra một số thực với 10 chữ số thập phân, là tổng chiều dài nhỏ nhất cần sử dụng.

Kết quả được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá ~10^{-6}~.

Ví dụ

Ví dụ 1

Input

2
0 0
3 4

Output

5.0000000000

Ví dụ 2

Input

3
0 0
1 10
2 0

Output

12.0498756211

Ví dụ 3

Input

4
0 0
2 0
5 0
9 0

Output

9.0000000000

Ví dụ 4

Input

5
0 0
1 4
2 1
3 5
4 0

Output

10.8313095581

Giải thích

Ví dụ 1

Buộc một trong hai sợi chỉ từ đinh ~1~ đến đinh ~2~. Độ dài cần dùng là ~5~.

Ví dụ 2

Có thể sử dụng hai sợi chỉ theo các dãy đinh ~1 \to 2~ và ~1 \to 3~.

Tổng chiều dài là:

~\sqrt{101} + 2 = 12.0498756211~.

Ví dụ 3

Một sợi chỉ đi qua các đinh theo thứ tự ~1 \to 2 \to 3 \to 4~, sợi còn lại chỉ được buộc tại đinh ~1~.

Tổng chiều dài là:

~2 + 3 + 4 = 9~.

Ví dụ 4

Có thể sử dụng hai sợi chỉ theo các dãy đinh ~1 \to 2 \to 4~ và ~1 \to 3 \to 5~.

Tổng chiều dài là:

~\sqrt{17} + 3\sqrt{5} = 10.8313095581~.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le n \le 2000~.
• ~|x_i|, |y_i| \le 10^9~.
• Không có hai đinh nào có cùng tọa độ.

Chấm điểm

Có ~n~ cửa hàng mới cần được phân vào ~2~ chuỗi cửa hàng.

Cửa hàng thứ ~i~ có tọa độ ~\left(x_i, y_i\right)~. Các cửa hàng nằm trên hệ thống đường phố vuông góc, vì vậy khoảng cách giữa hai cửa hàng ~i~ và ~j~ được tính theo khoảng cách Manhattan:

~d(i,j) = |x_i - x_j| + |y_i - y_j|~.

Hãy chia tất cả các cửa hàng thành ~2~ nhóm sao cho khoảng cách lớn nhất giữa hai cửa hàng thuộc cùng một nhóm là nhỏ nhất.

Yêu cầu

Tìm giá trị nhỏ nhất có thể của khoảng cách Manhattan lớn nhất giữa hai cửa hàng cùng thuộc một nhóm.

Dữ liệu

Dòng đầu tiên chứa số nguyên ~n~ là số lượng cửa hàng.

Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, \ldots, x_n~, trong đó ~x_i~ là hoành độ của cửa hàng thứ ~i~.

Dòng thứ ba chứa ~n~ số nguyên ~y_1, y_2, \ldots, y_n~, trong đó ~y_i~ là tung độ của cửa hàng thứ ~i~.

Nhiều cửa hàng có thể có cùng tọa độ.

Kết quả

In ra một số nguyên là giá trị nhỏ nhất có thể của khoảng cách Manhattan lớn nhất giữa hai cửa hàng thuộc cùng một nhóm.

Ví dụ

Ví dụ 1

Input

7
2 10 7 13 5 13 15
4 6 1 5 7 3 5

Output

8

Giải thích

Ví dụ 1

Có thể chia các cửa hàng thành hai nhóm:

• ~{1, 3, 5}~
• ~{2, 4, 6, 7}~

Trong nhóm thứ nhất, khoảng cách lớn nhất giữa hai cửa hàng là:

~d(1,3) = |2 - 7| + |4 - 1| = 8~.

Trong nhóm thứ hai, mọi khoảng cách giữa hai cửa hàng đều không vượt quá ~8~.

Không tồn tại cách chia nào làm cho khoảng cách lớn nhất trong mỗi nhóm nhỏ hơn ~8~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 30000~.
• ~1 \le x_i, y_i \le 5 \cdot 10^8~.

Chấm điểm

Có ~n~ cách chế biến và ~m~ nguyên liệu truyền thống, được đánh số lần lượt từ ~1~ đến ~n~ và từ ~1~ đến ~m~.

Với mỗi cặp ~\left(i, j\right)~, đầu bếp có thể chuẩn bị đúng ~a_{i,j}~ món ăn bằng cách chế biến ~i~ và sử dụng nguyên liệu ~j~ làm nguyên liệu chính.

Các món ăn được xem là phân biệt, kể cả khi chúng có cùng cách chế biến và cùng nguyên liệu chính.

Đầu bếp muốn chọn một tập gồm ~k~ món ăn để giới thiệu. Tập được chọn phải thỏa mãn các điều kiện sau:

• Tập không rỗng, tức là ~k \ge 1~.
• Không có hai món nào được chế biến bằng cùng một cách.
• Với mỗi nguyên liệu, số món sử dụng nguyên liệu đó làm nguyên liệu chính không vượt quá ~\left\lfloor \frac{k}{2} \right\rfloor~.

Hai tập món ăn được xem là khác nhau nếu tồn tại ít nhất một món thuộc đúng một trong hai tập đó.

Yêu cầu

Đếm số cách chọn một tập món ăn thỏa mãn các điều kiện trên.

Vì số cách có thể rất lớn, hãy in ra kết quả theo modulo ~998244353~.

Dữ liệu

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~, lần lượt là số cách chế biến và số nguyên liệu.

~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên ~a_{i,1}, a_{i,2}, \ldots, a_{i,m}~. Trong đó, ~a_{i,j}~ là số món có thể được chuẩn bị bằng cách chế biến ~i~ và sử dụng nguyên liệu ~j~ làm nguyên liệu chính.

Kết quả

In ra một số nguyên là số cách chọn tập món ăn thỏa mãn yêu cầu, lấy theo modulo ~998244353~.

Ví dụ

Ví dụ 1

Input

2 3
1 0 1
0 1 1

Output

3

Ví dụ 2

Input

3 3
1 2 3
4 5 0
6 0 0

Output

190

Ví dụ 3

Input

5 5
1 0 0 1 1
0 1 0 1 0
1 1 1 1 0
1 0 1 0 1
0 1 1 0 1

Output

742

Giải thích

Ví dụ 1

Có đúng ~3~ cách chọn hợp lệ, mỗi cách gồm ~2~ món được chế biến bằng hai cách khác nhau và sử dụng hai nguyên liệu khác nhau.

Ví dụ 2

Số tập món ăn thỏa mãn đồng thời các điều kiện là ~190~.

Ví dụ 3

Số tập món ăn thỏa mãn đồng thời các điều kiện là ~742~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 100~.
• ~1 \le m \le 2000~.
• ~0 \le a_{i,j} \le 998244353~.

Chấm điểm