Giả sử chúng ta có một hình vuông có \(W\) ô mỗi cạnh, và do đó có tổng cộng \(W^2\) ô. Hãy lấp đầy mỗi ô bằng một trong các loại sau:

• Một chữ số từ 0 đến 9;
• Dấu cộng (+);
• Dấu trừ (-).

Nếu chúng ta thêm ràng buộc rằng không có 2 chữ số nào nằm kề nhau theo chiều ngang hoặc chiều dọc, và không có 2 toán tử (+ hoặc -) nào nằm kề nhau theo chiều ngang hoặc chiều dọc, thì hình vuông của chúng ta được gọi là một "hình vuông số học".

Square Math là tên của một trò chơi đố chữ, trong đó, cho trước một hình vuông số học, chúng ta bắt đầu từ bất kỳ ô chứa chữ số nào và di chuyển theo chiều ngang hoặc chiều dọc mỗi lần một ô, cuối cùng kết thúc ở một ô chứa chữ số. Biểu thức toán học chúng ta nhận được từ quá trình di chuyển sẽ được tính toán để ra một giá trị duy nhất. Ví dụ:

2+3
+4-
1+0

Trên đây là một hình vuông số học hợp lệ kích thước \(W = 3\). Nếu chúng ta bắt đầu từ "2", di chuyển sang phải, sau đó xuống dưới, chúng ta sẽ có "2+4", cho giá trị là "6". Nếu chúng ta tiếp tục di chuyển sang phải, sau đó lên trên, chúng ta sẽ có "2+4-3", bằng "3".

Trong Square Math, không có giới hạn về số lần bạn có thể sử dụng một ô cụ thể. Việc di chuyển từ một ô sang ô lân cận, rồi quay lại ô ban đầu là hoàn toàn hợp lệ. Cho một hình vuông số học và một danh sách các truy vấn, nhiệm vụ của bạn là tìm một biểu thức Square Math có giá trị bằng mỗi truy vấn.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất, \(T\). \(T\) bộ dữ liệu kiểm tra theo sau. Dòng đầu tiên của mỗi bộ dữ liệu chứa 2 số nguyên, \(W\) và \(Q\). \(W\) dòng tiếp theo, mỗi dòng chứa \(W\) ký tự, đại diện cho hình vuông số học. Đừng lo lắng, tất cả các hình vuông số học trong dữ liệu vào đều được định dạng đúng. Dòng tiếp theo chứa một danh sách \(Q\) số nguyên cách nhau bởi dấu cách, đại diện cho các giá trị cần được tính toán bằng Square Math (các truy vấn). Bạn có thể giả định rằng tất cả các giá trị cho trước sẽ có ít nhất một giải pháp Square Math khả thi.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, bắt đầu đầu ra với "Case #\(X\):" trên một dòng riêng biệt, trong đó \(X\) là số thứ tự bộ dữ liệu, bắt đầu từ 1. Sau đó, đối với mỗi truy vấn trong bộ dữ liệu, hãy in biểu thức Square Math có giá trị bằng truy vấn đó trên một dòng riêng biệt.

Trong trường hợp có nhiều biểu thức Square Math khả thi, hãy in biểu thức ngắn nhất. Nếu vẫn còn hòa, hãy in biểu thức nhỏ nhất theo thứ tự từ điển. Lưu ý rằng '+' nhỏ hơn '-' theo thứ tự từ điển.

Ràng buộc

• \(1 \le T \le 60\)

Phân nhóm

• Small dataset:

  • \(2 \le W \le 10\)
  • \(1 \le Q \le 20\)
  • \(1 \le \text{mỗi truy vấn} \le 50\)

  • Large dataset:

  • \(2 \le W \le 20\)

  • \(1 \le Q \le 50\)
  • \(1 \le \text{mỗi truy vấn} \le 250\)

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
5 3
2+1-2
+3-4+
5+2+1
-4-0-
9+5+1
20 30 40
3 2
2+1
+4+
5+1
2 20

Case #1:
1+5+5+9
3+4+5+9+9
4+9+9+9+9
Case #2:
2
5+5+5+5

Nguồn

Google Code Jam 2009, Vòng 1B, bài Square Math.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.