Cho bảng \(A\) kích thước \(m \times n\) các hàng của bảng được đánh số từ \(1\) tới \(m\) và các cột của bảng được đánh số từ \(1\) tới \(n\). Ô nằm trên hàng \(i\) và cột \(j\) được điền một số nguyên có giá trị \(a_{i,j}\). Có \(q\) thao tác và có 2 loại thao tác

• \(1\ d\ r\)
• \(2\ x\ y\ u\ v\)

Thao tác 1: Thực hiện \(d\) lệnh \(D\) và \(r\) lệnh \(R\).

Lệnh D: Dịch các hàng lên 1 hàng

• Hàng 2 lên hàng 1
• Hàng 3 lên hàng 2
• ….
• Hàng 1 xuống hàng m

Ví dụ: \(d=1\)

\(\begin{matrix} &1&2&3\\ &4&5&6\\&7&8&9\end{matrix}\) \(\ \ \ \Rightarrow\) \(\begin{matrix} &4&5&6\\&7&8&9\\&1&2&3\end{matrix}\)

Lệnh R: Dịch các cột sang trái 1 cột

• Cột 2 sang cột 1
• Cột 3 sang cột 2
• …
• Cột 1 sang cột n

Ví dụ: \(r=1\)

\(\begin{matrix} &1&2&3\\ &4&5&6\\&7&8&9\end{matrix}\) \(\ \ \ \Rightarrow\) \(\begin{matrix} &2&3&1\\&5&6&4\\&8&9&7\end{matrix}\)

Thao tác 2: Trả về giá trị lớn nhất của bảng trong khoảng góc trái trên \([x,y]\) và góc phải dưới \([u,v]\).

Input

• Dòng đầu gồm hai số nguyên dương \(m,n\) \((m,n \le 300)\).
• \(m\) dòng tiếp theo chứa \(n\) số nguyên \((a_{i,j} \le 10^6)\).
• Dòng tiếp theo chứa số \(q\) là số lượng thao tác \((q \le 10^5)\).

• \(q\) dòng tiếp theo chứa lệnh 1 hoặc 2 cùng dữ kiện tương ứng

  \(1\ d\ r\) \((d,r \le 10^6)\)

  \(2\ x\ y\ u\ v\) \((1 \le x \le u \le m , 1 \le y \le v \le n)\)

Output

• Với mỗi lệnh 2, in kết quả tìm được

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(m,n,q \le 100,\ d=r = 1\).
• Subtask \(2\) (\(50\%\) số điểm): không có giới hạn gì thêm.

Example

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

4
9