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

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mtrgame

Hai người P1 và P2 đang chơi một trò chơi. Trò chơi được thực hiện trên một ma trận số nguyên M, với kích thước m x n.

Tại một lượt đi, P1 chọn một số i nằm trong khoảng từ 0 đến m-1 trong khi P2 chọn một số j nằm trong khoảng từ 0 đến n-1. Điều thú vị là cả hai đều không biết số mà người kia đã chọn ...

Sau khi hoàn thành việc chọn số, họ thông báo số của mình cho người kia biết. M[i][j] là một phần tử của ma trận được quyết định bởi các chỉ số mà 2 người chơi đã chọn. Nếu M[i][j] là một số âm, P1 trả P2 một lượng tiền bằng trị tuyệt đối của M[i][j]. Tuy nhiên, nếu M[i][j] là một số dương, thì P2 phải trả P1 một lượng bằng M[i][j].

Cho ma trận M và biết rằng cả hai người chơi đều tuyệt đối thông minh, hay tính số tiền trung bình mà P2 trả P1 cho một lượt chơi trong trò chơi.

Lưu ý: P1 chơi để kiếm được nhiều tiền nhất, trong khi P2 cố gắng để phải trả ít tiền nhất.

Input

Dòng đầu chứa T, số lượng test.

Trong mỗi test, dòng đầu chứa 2 số nguyên m và n, thể hiện kích thước của ma trận. Tiếp theo là m dòng, mỗi dòng chứa n số nguyên thể hiện các phần tử của ma trận.

Output

Chứa T dòng, mỗi dòng chứa một số thực với chính xác 3 chữ số thập phân, thể hiện số tiền trung bình mà P1 nhận được trong 1 lượt chơi.

Example

Input:
3
1 1
-1
2 2
1 2
3 4
2 2
1 4
4 3


Output:
-1.000
3.000
3.250

Constraints

Input Set 1: m <= 2, n <= 10, abs(values) <= 150000, số lượng test <= 120.

Input Set 2: m <= 2, n <= 5000, abs(values) <= 150000, số lượng test <= 20.

Input Set 3: m <= 2, n <= 100000, abs(values) <= 150000, số lượng test <= 10.

Input Set 4: m <= 3, n <= 5000, abs(values) <= 150000, số lượng test <= 15.