Cho ma trận kích thước \(N×N\). Các hàng được đánh số từ \(1\) tới \(N\), các cột đánh số từ \(1\) tới \(N\). Tại ô \((i,j)\) ở hàng \(i\), cột \(j\) chứa một số nguyên \(a_{ij} (a_{ij}≤10^6; 1≤i,j≤N)\). Thực hiện lần lượt \(Q\) truy vấn, mỗi truy vấn thuộc một trong ba loại sau:

• \(R\ X:\) Xoay ma trận theo chiều quay kim đồng hồ \(90° X\) lần;
• \(L \ Y:\) Xoay ma trận ngược chiều quay kim đồng hồ \(90° Y\) lần;
• \(3 \ K:\) Tìm đường đi có tổng lớn nhất từ một ô bất kì ở cột \(1\) đến một ô bất kì ở cột \(N\).

Biết rằng từ ô \((i,j)\) có thể di chuyển đến ô \((i-1,j+1),(i,j+1)\) và \((i+1,j+1)\). Đưa ra tổng lớn nhất.

Dữ liệu vào:

• Dòng 1: Ghi số nguyên dương \(N\) và \(Q (N,Q≤50)\);
• \(N\) dòng tiếp theo, mỗi dòng ghi \(N\) số nguyên;
• \(Q\) dòng tiếp theo, mỗi dòng chứa một trong ba loại truy vấn trên.

Dữ liệu vào có ít nhất một truy vấn dạng \(3 \ K\). Các số trên một dòng cách nhau bởi một dấu cách.

Kết quả:

• Gồm nhiều dòng, mỗi dòng ghi kết quả của một truy vấn dạng \(3 \ K\).

Ví dụ:

Input

4  5
-6  3  -5  2
2  -4   7  -9
4  -3   5  -2
5   3   -6  3
R  2
L  1
3  3
L  1
3  3

Output

18
16

Hình minh họa

Ràng buộc:

• Số nguyên dương \(K≤50\);
• \(0≤X,Y≤50\);
• Có 20% test với \(X\) và \(Y\) chia hết cho \(4\);
• Có 80% test với ràng buộc gốc.