Tom và Jerry có một giá sách gồm ~m~ tầng, các tầng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới. Mỗi tầng có ~n~ quyển sách, các quyển được đánh số từ ~1~ đến ~n~ từ trái sang phải, quyển sách thứ ~j~ ở tầng ~i~ được gọi là quyển sách ~(i, j)~ và có ~p_{ij}~ trang.

Tom thường xuyên dành thời gian để sắp xếp lại sách trong giá sách, mỗi lần Tom sẽ tráo đổi hai quyển sách ~(x, y)~ với ~(u, v)~. Jerry thường rủ Tom cùng đọc sách theo cách:

Jerry chọn hai số ~L, R~ sao cho ~1 \le L \le R \le m~ và cho Tom chọn một tầng sách ~s~ sao cho ~L \le s \le R~ và cả hai sẽ cùng đọc tất cả ~n~ quyển sách trên tầng đó. Tại một thời điểm, một quyển chỉ được đọc bởi một người và người đó đọc liên tục cho đến hết quyển sách. Thời gian để Tom hoặc Jerry đọc một trang sách là ~1~ giây. Cả Tom và Jerry đều đọc ~n~ quyển sách trên tầng ~s~ dù trước đó quyển sách đã đọc hay chưa, thời gian để hai bạn đọc hết tầng sách là thời gian cả hai đều đọc xong ~n~ quyển sách. Vì Tom muốn ưu tiên thời gian sắp xếp lại sách nên Tom sẽ lựa chọn tầng ~s~ để thời gian đọc là nhỏ nhất.

Cho dãy ~q~ hoạt động, mỗi hoạt động thuộc một trong hai loại:

• Loại 1 có dạng: ~1~ ~x~ ~y~ ~u~ ~v~, loại này sẽ tráo đổi hai quyển sách ~(x, y)~ với ~(u, v)~;
• Loại 2 có dạng: ~2~ ~L~ ~R~, loại này cần trả lại thời gian nhỏ nhất để đọc một tầng sách trong các tầng từ ~L~ đến ~R~.

Yêu cầu: Thực hiện lần lượt ~q~ hoạt động.

Input

• Dòng đầu chứa ba số nguyên dương ~m, n, q~ (~m \times n \le 10^6; q \le 10^6~);
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo gồm ~n~ số nguyên ~p_{i1}, p_{i2}, \dots, p_{in}~ (~1 \le p_{ij} \le 10^6~);
• Dòng thứ ~k~ (~1 \le k \le q~) trong ~q~ dòng tiếp theo mô tả truy vấn.

Output

• Ghi ra lần lượt là câu trả lời cho các hoạt động loại 2.