Cho \(n\) điểm trên không gian \(k\) chiều, điểm thứ \(i\) có tọa độ là \((a_{i,1}, a_{i,2}, \dots, a_{i,k})\). Khoảng cách manhattan giữa \(2\) điểm \(x\) và \(y\) là: \(\sum_{i=1}^{k} |a_{x,i}-a_{y,i}|\).

Bạn phải xử lý \(q\) truy vấn thuộc \(1\) trong \(2\) loại:

• \(1 \; i \; b_1 \; b_2 \dots \; b_k\): Gán tọa độ điểm thứ \(i\) là \((b_1,b_2,\dots,b_k)\).

• \(2 \; l \; r\): Tìm khoảng cách manhattan lớn nhất giữa \(2\) điểm \(i\) và \(j\) với \(l \le i,j \le r\).

Input

• Dòng \(1\): Gồm \(2\) số nguyên \(n\) và \(k\) (\(1 \le n \le 10^5\); \(1 \le k \le 5\)) - số lượng phần tử trong \(a\) và số chiều của không gian.
• \(n\) dòng tiếp theo, mỗi dòng chứa \(k\) số \(a_{i,1},a_{i,2},\dots,a_{i,k}\) \((-10^6 \le a_{i,j} \le 10^6)\) - tọa độ điểm \(i\).
• Dòng tiếp theo gồm \(1\) số nguyên \(q\) \((1 \le q \le 10^5)\)- số lượng truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng gồm \(1\) trong \(2\) loại:
  • \(1 \; i \; b_1 \; b_2 \dots \; b_k\) \((1 \le i \le n;\)\(-10^6 \le b_j \le 10^6)\) - Gán tọa độ điểm thứ \(i\) là \((b_1,b_2,\dots,b_k)\).
  • \(2 \; l \; r\) \((1 \le l \le r \le n)\) - Tìm khoảng cách manhattan lớn nhất giữa \(2\) đểm \(i,j\) với \(l \le i,j \le r\).

Output

• Với mỗi truy vấn loại \(2\), đưa ra \(1\) dòng gồm \(1\) số duy nhất là kết quả tìm được.

Scoring

• Subtask \(1\) (\(30\%\) số điểm\()\): \(n,q \le 3000\)
• Subtask \(2\) (\(20\%\) số điểm\()\): \(k = 1\).
• Subtask \(3\) (\(20\%\) số điểm\()\): \(k = 2\).
• Subtask \(4\) (\(30\%\) số điểm\()\): Không có điều kiện gì thêm.

Example

5 2
1 2
2 3
3 4
4 5
5 6
7
2 1 5
2 1 3
2 3 5
1 5 -1 -2
2 1 5
1 4 -1 -2
2 1 5

8
4
4
12
10