Giải bài trực tuyến

Josip là một họa sĩ kỳ lạ. Anh muốn vẽ một bức tranh gồm N×N điểm ảnh, với N là một lũy thừa của 2 (1, 2, 4, 8, 16 v.v…). Mỗi điểm sẽ có màu đen hoặc màu trắng. Josip đã có một ý tưởng cho việc tô màu mỗi điểm ảnh.

Sẽ chẳng có vấn đề gì nếu như phương pháp tô màu của Josip không kỳ lạ. Anh ấy sử dụng quá trình đệ quy sau:

• Nếu như bức tranh chỉ có một điểm ảnh, anh tô nó theo cách đã dự định.
• Trường hợp còn lại, chia hình vuông thành 4 hình vuông nhỏ hơn và:
  • 1. Chọn một trong số 4 hình vuông, tô nó bằng màu trắng.
  • 2. Chọn một trong 3 hình vuông còn lại, tô nó màu đen.
  • 3. Coi 2 hình vuông còn lại như những bức tranh mới và áp dụng quá trình trên với chúng.

Josip nhanh chóng thấy rằng không thể nào chuyển tải hết được ý tưởng của mình vào các bức tranh với phương pháp này. Nhiệm vụ của bạn là viết một chương trình tìm cách tô một bức tranh sao cho nó sai khác ít nhất so với bức tranh đã thiết kế sẵn. Sự sai khác giữa hai bức tranh là số cặp điểm ở vị trí tương ứng mà khác màu nhau.

Input

Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 512), là kích thước của bức tranh mà Josip muốn vẽ. N là một lũy thừa của 2.

Mỗi dòng trong số N dòng tiếp theo chứa N chữ số 0 hoặc 1, thể hiện điểm ảnh màu trắng hoặc màu đen trong bức tranh cần vẽ.

Output

Dòng đầu tiên ghi ra số lượng sai khác nhỏ nhất tìm được.

Trên N dòng tiếp theo, in ra bức tranh có thể tô được theo phương pháp của Josip's mà có ít sai khác nhất so với bức tranh cần vẽ. Bức tranh phải được in ra theo cùng định dạng như trong input.

Lưu ý: Phần thứ 2 của output (bức tranh) có thể không duy nhất. Bất kỳ output đúng nào đều được chấp nhận.

Example

Input:
8
01010001
10100011
01010111
10101111
01010111
10100011
01010001
10100000

Output:
16
00000001
00000011
00000111
00001111
11110111
11110011
11110001
11110000