Cho ma trận vuông \(a_{ij}\) cỡ n nhân n với chỉ số hàng và chỉ số cột được đánh số từ \(1\) đến \(n\) và cho tọa độ u và v \(1<= u,v <=n\) hãy tính tổng các phần tử nằm trên đường chéo song song với đường chéo chính và đi qua tọa độ \((u,v)\) và giá trị nhỏ nhất của các phần tử nằm trên đường chéo song song với đường chéo phụ của ma trận đi qua tọa độ \((u,v)\)

Input

Dòng đầu chứ hai số nguyên gồm \(n\) là cỡ của ma trận và \(q\) là số phép truy vấn \(10<=n,q<=100\)

\(n\) dòng tiếp theo mỗi dòng chứa n số nguyên có giá trị tuyệt đối không vượt quá \(10^4\) tương ứng với các dòng của ma trận vuông \(n * n\)

\(q\) dòng cuối cũng là các truy vấn mỗi truy vấn gồm một cặp hai số \(u, v\) trong đó \(1<=u,v<=n\)

Output

Với mỗi truy vấn xuất ra màn hình hai giá trị nguyên tương ứng là tổng các phần tử nằm trên đường chéo song song với đường chéo chính đi qua \((u,v)\) và giá trị nhỏ nhất của các phần tử nằm trên đường chéo song song với đường chéo phụ của ma trận đi qua tọa độ \((u,v)\)

Ví dụ

Input

5 3
4 3 6 1 6 
6 8 3 0 4 
6 9 7 7 8 
4 3 1 0 7 
6 4 9 5 2 
1 3
2 1
4 4

Output

14 6
21 3
21 0