Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Momo vừa trở lại Tokyo, và quyết định mở tiệc lẩu với hai người bạn thân của mình là Yamato và Ao!

Tất nhiên, muốn món lẩu ngon thì nước lẩu cũng phải hoàn hảo. Và momo hiểu rất rõ điều này nên chị bắt tay ngay vào việc.

Vừa quay lại Tokyo từ nhà nên momo có rất nhiều nguyên liệu - chính xác là chị có n loại nguyên liệu khác nhau để chế biến nước lẩu.

Cách mà momo chế biến nước lẩu như sau:

Đầu tiên, chị chọn k (2 ≤ k ≤ n) nguyên liệu khác nhau trong số n nguyên liệu của mình theo thứ tự x₁, x₂, …, x_k (1 ≤ x_i ≤ n, 1 ≤ i ≤ k). Sau đó, chị sẽ sử dụng lần lượt các nguyên liệu từ x₁, x₂, …, cho tới x_k để chế biến nước lẩu theo cách của mình.

Độ hài lòng của Yamato và Ao đối với “sản phẩm” thu được được tính toán rất phức tạp:

• Sự xuất hiện của nguyên liệu thứ i sẽ tăng độ hài lòng của Yamato thêm by_i đơn vị và tăng độ hài lòng của Ao thêm ba_i đơn vị.
• Nếu nguyên liệu thứ j được sử dụng ngay sau nguyên liệu thứ i, độ hài lòng của Yamato tăng thêm cy_(i,j) đơn vị và độ hài lòng của Ao tăng thêm ca_(i,j) đơn vị.

Tuy nhiên, vốn là những nguyên liệu lạ mua từ Ottawa, nên không phải thứ gì Yamato và Ao cũng đều thích cả. Momo cần phải chọn nguyên liệu và cách chế biến thích hợp sao cho độ hài lòng của hai người ít chênh lệch nhất, và nếu có nhiều cách thực hiện thì phải chọn cách để độ hài lòng của cả hai là lớn nhất!

Bạn có thể giúp chị đại của chúng ta có được một công thức hoàn hảo nhất để thỏa mãn cả hai người bạn của mình hay không? 

Input

Bắt đầu mỗi file input là một dòng chứa một số nguyên T chỉ số bộ test (1 ≤ T ≤ 30).

Mỗi bộ test sẽ có dạng như sau:

Dòng đầu tiên chứa một số nguyên n (2 ≤ n ≤ 10) - số loại nguyên liệu mà momo có.

Dòng thứ hai chứa n số nguyên by₁, by₂, ..., by_n (0 ≤ | by_i | ≤ 10) - độ hài lòng của Yamato khi từng nguyên liệu được sử dụng.

Dòng thứ ba chứa n số nguyên ba₁, ba₂, ..., ba_n (0 ≤ | ba_i | ≤ 10) - độ hài lòng của Ao khi từng nguyên liệu được sử dụng.

n dòng tiếp theo, dòng thứ i gồm n số nguyên cy_(i,1), cy_(i,2), ..., cy_(i,n) (0 ≤ | cy_(i,j) | ≤ 10) - độ hài lòng của Yamato khi từng nguyên liệu được dùng ngay sau nguyên liệu thứ i.

n dòng tiếp nữa, dòng thứ i gồm n số nguyên ca_(i,1), ca_(i,2), ..., ca_(i,n) (0 ≤ | ca_(i,j) | ≤ 10) - độ hài lòng của Ao khi từng nguyên liệu được dùng ngay sau nguyên liệu thứ i.

Output

Mỗi bộ test sẽ có output như sau:

Dòng đầu tiên chứa một số nguyên M - số cặp giá trị độ hài lòng tối ưu khác nhau.

M dòng tiếp theo, mỗi dòng in ra 2 số nguyên Y, A - lần lượt là độ hài lòng của Yamato và Ao.

M dòng này được sắp xếp theo thứ tự sau: độ hài lòng của Yamato tăng dần; nếu hai cặp giá trị có cùng độ hài lòng của Yamato thì cặp giá trị mà độ hài lòng của Ao nhỏ hơn sẽ được in ra trước.

Example

Input
1
3
2 2 -4
2 2 -4
0 1 0
3 0 0
0 0 0
0 3 8
1 0 8
8 8 0

Output
2
5 7
7 5

Giải thích:

Ta sẽ thử mọi công thức mà momo có thể thực hiện:

Công thức 1: (1) → (2) → (3). => (Y, A) = (2 + 2 – 4 + 1 + 0, 2 + 2 – 4 + 3 + 8) = (1, 11).

Công thức 2: (1) → (3) → (2). => (Y, A) = (2 – 4 + 2 + 0 + 0, 2 – 4 + 2 + 8 + 8) = (0, 16).

Công thức 3: (2) → (1) → (3). => (Y, A) = (2 + 2 – 4 + 3 + 0, 2 + 2 – 4 + 1 + 8) = (3, 9).

Công thức 4: (2) → (3) → (1). => (Y, A) = (2 – 4 + 2 + 0 + 0, 2 – 4 + 2 + 8 + 8) = (0, 16).

Công thức 5: (3) → (1) → (2). => (Y, A) = (-4 + 2 + 2 + 0 + 1, -4 + 2 + 2 + 8 + 3) = (1, 11).

Công thức 6: (3) → (2) → (1). => (Y, A) = (-4 + 2 + 2 + 0 + 3, -4 + 2 + 2 + 8 + 1) = (3, 9).

Công thức 7: (1) → (2). => (Y, A) = (2 + 2 + 1, 2 + 2 + 3) = (5, 7).

Công thức 8: (1) → (3). => (Y, A) = (2 – 4 + 0 , 2 – 4 + 8) = (-2, 6).

Công thức 9: (2) → (1). => (Y, A) = (2 + 2 + 3, 2 + 2 + 1) = (7, 5).

Công thức 10: (2) → (3). => (Y, A) = (2 – 4 + 0, 2 – 4 + 8) = (-2, 6).

Công thức 11: (3) → (1). => (Y, A) = (-4 + 2 + 0, -4 + 2 + 8) = (-2, 6).

Công thức 12: (3) → (2). => (Y, A) = (-4 + 2 + 0, -4 + 2 + 8) = (-2, 6).

Từ đây ta thấy, hai trường hợp tối ưu nhất là công thức 7 và công thức 9, khi độ hài lòng của Yamato và Ao hoặc bằng 5 hoặc bằng 7.