Đề bài
Dũng và Minh có một giá sách gồm \(m\) tầng, đánh số từ \(1\) đến \(m\) từ trên xuống dưới. Mỗi tầng có \(n\) quyển sách, đánh số từ \(1\) đến \(n\) từ trái sang phải. Quyển sách ở tầng \(i\) và vị trí \(j\) được gọi là sách \((i, j)\) và có \(p_{i,j}\) trang.
Minh chọn hai số \(L\), \(R\) sao cho \(1 \leq L \leq R \leq m\), sau đó Dũng chọn một tầng \(s\) sao cho \(L \leq s \leq R\). Cả hai sẽ cùng đọc tất cả \(n\) quyển sách trên tầng \(s\). Mỗi quyển chỉ được một người đọc tại một thời điểm và người đó phải đọc liên tục đến khi hết quyển sách. Thời gian đọc một trang là 1 giây cho cả hai người.
Cả hai đều phải đọc toàn bộ \(n\) quyển trên tầng \(s\), không phân biệt sách đã đọc hay chưa. Tổng thời gian đọc tầng sách \(s\) là thời gian để cả hai hoàn thành việc đọc. Dũng sẽ chọn tầng \(s\) sao cho thời gian đọc là nhỏ nhất.
Có \(q\) hoạt động, mỗi hoạt động thuộc một trong hai loại:
- Loại 1:
1 x y u v– tráo đổi quyển sách \((x, y)\) với sách \((u, v)\) - Loại 2:
2 L R– tính thời gian tối thiểu để cả hai đọc xong một tầng sách từ tầng \(L\) đến tầng \(R\)
Hãy thực hiện tuần tự \(q\) hoạt động và in kết quả cho mỗi hoạt động loại 2.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên dương \(m\), \(n\), \(q\) — số tầng, số sách mỗi tầng và số hoạt động.
- \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên \(p_{i,1}, p_{i,2}, \dots, p_{i,n}\) — số trang của các quyển sách trên từng tầng.
- \(q\) dòng tiếp theo, mỗi dòng mô tả một hoạt động như đã nêu.
Dữ liệu ra
- Với mỗi truy vấn loại 2, in ra thời gian nhỏ nhất để Dũng và Minh đọc xong một tầng trong khoảng đã cho.
Giới hạn
- \(1 \leq m \cdot n \leq 10^6\)
- \(1 \leq q \leq 10^6\)
- \(1 \leq p_{i,j} \leq 10^6\)
Subtasks (có thể có)
| Subtask | Tỉ lệ | Ràng buộc |
|---|---|---|
| 1 | 20% | \(m = n = 2\) |
| 2 | 20% | \(n = 2\) |
| 3 | 20% | \(n \leq 5\), \(q \leq 10^4\) |
| 4 | 20% | \(n \leq 20\) |
| 5 | 20% | Không giới hạn gì thêm |
Sample Input 1
2 3 3
1 1 1
1 3 3
2 1 2
1 1 2 2 2
2 1 2
Sample Output 1
3
6
Giải thích
- Hoạt động 1: Chọn tầng 1, cả hai người đọc hết 3 quyển sách: thời gian là 3 giây.
-
Hoạt động 2: tráo đổi sách (1,2) với (2,2). Giá sách sau thao tác:
1 3 1 1 1 3 -
Hoạt động 3: chọn tầng 1 hoặc 2 đều mất 6 giây để cả hai đọc xong.