Năm 20xx Việt Nam được đăng cai tổ chức Robocon,

thể lệ của 1 trận thi đấu được mô tả như sau:

Sân chơi được tổ chức thành một ma trận có kích cỡ (N+2)x(N+2)

Trong đó, ô chứa điểm tổ chức trong ma trận con NxN,

cách mỗi viền ngoài 1 ô như hình bên

Mỗi trận đấu sẽ gồm 2 đội xanh và đỏ:

> Đội xanh xuất phát ở vị trí trên cùng bên trái tọa độ là (0,0), và hướng xuống

> Đội đỏ xuất phát ở vị trí dưới cùng bên phải tọa độ là (N-1, N-1), và hướng lên trên

Nhiệm vụ của bạn là thực hiện tính điểm cho mỗi đội qua mỗi vòng thi đấu, theo quy tắc sau:

> Cả 2 đội sẽ có M lệnh để thực hiện di chuyển Robot của mình

Quy ước như sau:

> lệnh 0: robot sẽ tiến 1 bước theo hướng hiện tại của Robot đó.

> lệnh 1: Robot sẽ đứng yên và điều chỉnh hướng đi sang trái.

> lệnh 2: robot sẽ đứng yên và điều chỉnh hướng đi sang phải.

> Robot đi tới 1 ô có ghi điểm nào thì được cộng điểm đó vào tổng điểm của đội đó

> Robot của đội nào đi vào ô mà đội trước đã đi qua sẽ không được cộng điểm tại ô chứa điểm đó.

 Robot sẽ ngã khi trong các trường hợp sau:

> Tại cùng 1 thời điểm 2 robot của 2 đội cùng đi tới 1 ô

> Robot của 1 đội lao vào ô của Robot đội kia đang đứng

Giới hạn

> Sẽ ko có lệnh khiến robot ra khỏi khu vực thi đấu

> Điểm trong ô chứa điểm sẽ có giá trị từ 1 - 9

Ví dụ:

N = 5, M = 12

Lệnh của đội xanh : 0 1 0 0 0 2 0 1 0 0 1 0

Lệnh của đội đỏ : 0 1 0 0 0 2 0 1 0 0 1 0

Sân chơi được tổ chức như hình trên

Thì điểm của đội xanh và đội đỏ lần lượt là: 32 và 38

Input

> Dòng đầu tiên là số lượng bộ test

> Dòng thứ 2 là kích thước ma trận chứa điểm số (N) và số lượng lệnh của 2 đội (M).

Mỗi giá trị cách nhau 1 dấu trắng " ".

> N dòng tiếp theo chứa các giá trị của ô điểm. Mỗi giá trị cách nhau một dấu " ".

> Dòng tiếp chứa M lệnh của đội xanh. Mỗi lệnh cách nhau 1 dấu trắng “ ”.

> Dòng tiếp chứa M lệnh của đội đỏ. Mỗi lệnh cách nhau 1 dấu trắng “ ”.

Output

> Lần thực hiện, điểm của đội xanh, điểm của đội đỏ. Các giá trị các nhau 1 dấu trắng " ".