Trong một đêm đầy sao, ledinhbaonam muốn chuẩn bị một món quà thật đặc biệt dành cho uia. Cậu tạo ra một khu vườn ánh sáng hình chữ nhật gồm \(m\) hàng và \(n\) cột. Mỗi ô trong khu vườn chứa một viên pha lê phát sáng, viên pha lê ở hàng \(i\), cột \(j\) có độ lung linh là \(a_{i,j}\).

Tuy nhiên, những cơn mưa sao băng liên tục xuất hiện khiến độ lung linh của các viên pha lê thay đổi theo thời gian. Vì vậy, uia muốn thường xuyên tìm kiếm một khu vực hoàn hảo để ngắm sao.

Một hình vuông con kích thước \(k \times k\) được gọi là hài hòa nếu độ chênh lệch giữa viên pha lê sáng nhất và tối nhất trong hình vuông không vượt quá một ngưỡng cho trước \(T\). Nói cách khác, nếu gọi \(\max(S)\) là giá trị lớn nhất và \(\min(S)\) là giá trị nhỏ nhất trong hình vuông thì hình vuông đó hợp lệ khi: \(\max(S)-\min(S)\le T\)

Kích thước khu vực ngắm sao không cố định. Với mỗi thời điểm, uia muốn biết kích thước lớn nhất của một hình vuông hài hòa có thể tồn tại trong khu vườn.

Bạn cần xử lý \(Q\) sự kiện thuộc một trong hai loại sau:

• 1 i j X: thay đổi độ lung linh của viên pha lê tại vị trí \((i,j)\) thành \(X\).
• 2 T: tìm giá trị lớn nhất của \(k\) sao cho tồn tại ít nhất một hình vuông con kích thước \(k \times k\) thỏa mãn điều kiện: \(\max(S)-\min(S)\le T\)

Nếu không tồn tại hình vuông nào thỏa mãn, in ra \(0\).

Input

Dòng đầu tiên chứa ba số nguyên \(m, n, Q\). \((1 \le m \le 4,\ 1 \le n \le 40000,\ 1 \le Q \le 50000)\)

\(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên \(a_{i,j}\). \((0 \le a_{i,j} \le 10^6)\)

\(Q\) dòng tiếp theo mô tả các sự kiện.

Với sự kiện loại 1 i j X: \(1 \le i \le m,\quad 1 \le j \le n,\quad 0 \le X \le 10^6\)

Với sự kiện loại 2 T: \(0 \le T \le 10^6\)

Output

Với mỗi truy vấn loại 2, in ra trên một dòng giá trị lớn nhất của \(k\) thỏa mãn yêu cầu.

Example

2 5 6
1 2 3 4 5
2 3 4 5 6
2 1
2 2
1 1 3 10
2 1
1 2 3 10
2 0

1
2
1
1

3 6 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
2 0
1 2 3 7
2 0
1 2 3 5
2 0

3
3
3