Nhảy bungee
View as PDFNhảy bungee là môn thể thao mạo hiểm, hấp dẫn với đặc trưng là cú nhảy mang lại cảm giác cực mạnh. Một trong số những sự hấp dẫn khác của nhảy bungee là bạn có thể ngắm nhìn khung cảnh hùng vĩ, tuyệt vời của thiên nhiên theo nhiều độ cao và theo một cách thức rất khác biệt.
Người chơi khi tham gia nhảy bungee sẽ được bảo hộ sự an toàn bằng dây dai xung quanh người và leo lên một nơi có địa thế rất cao ví dụ như cây cầu, khinh khí cầu, nơi tòa nhà cao tầng, trực thăng hoặc cáp treo... Sau đó, họ sẽ được thả mình xuống phía dưới mặt đất và cũng có thể là mặt nước. Ngay lúc đó, người chơi sẽ được trải nghiệm cảm giác dường như cả thế giới xung quanh đang bị đảo ngược. Cho đến khi họ chỉ còn cách bề mặt tiếp xúc một khoảng ngắn, người chơi sẽ được kéo lên.
Hôm nay là một ngày đặc biệt nên quyết định sẽ đăng ký trải nghiệm ~Q~ cuộc chơi nhảy bungee được tổ chức ở New Zealand. Khu vực nhảy bungee rất đa dạng và đặc sắc, thế nên nó được chia thành N khu vực mỗi khu vực có M địa điểm nhảy, tại khu vực thứ ~i~ và địa điểm nhảy thứ ~j~ gọi là cổng thứ ~(i, j)~, thêm vào đó mỗi cổng có một cây cầu giành cho việc nhảy, mỗi cây cầu có được độ cao là ~h[i][j]~ dặm, mặc dù rất can đảm nhưng anh ấy không thể nào vượt qua nỗi sợ độ cao nếu như cây cầu đó quá cao cụ thể với một số nguyên ~X~ nếu cây cầu có độ cao bé hơn hoặc bằng ~X (h[i][j] \leq X)~ thì cây cầu chỉ là ruồi muỗi ngược lại anh ấy sẽ bị sang chấn tâm lý. Để thêm phần kịch tính ban tổ chức đã ra quy chế chơi như sau, ở mỗi vòng thử thách ban tổ chức sẽ giới hạn lại khu vực nhảy của , cụ thể là anh ấy chỉ có thể tham gia các cổng giới hạn bởi vị trí trái trên ~(x1, y1)~ và phải dưới ~(x2, y2)~. Cụ thể nó sẽ được diễn ra như sau:
- Ban đầu xuất phát từ cổng ~(x1, y1)~, người chơi sẽ bắt đầu ở vị trí đó lần lượt chơi hết tất cả các cánh cổng ~(i, j)~ sao cho ~(x1 \leq i \leq x2 ~ ~~ và ~~ ~ y1 \leq j \leq y2).~
- Khi tới một cánh cổng nếu độ cao của nó bé hơn hoặc bằng ~X~ thì người chơi sẽ tiếp tục nhảy và vượt qua nếu không thì anh ta sẽ bỏ đi và chơi ở cổng khác.
Vì chưa biết rõ sức chịu đựng của mình như thế nào nhưng mà vì đã xem bói (bà bói nói rằng con sẽ vượt qua được ~K~ cổng của thứ thách này) nên muốn biết được sức chịu đựng nhỏ nhất của mình sao cho tồn tại ít nhất ~K~ cánh cổng mà có thể vượt qua. Vì đã tạch (tạch gì thì chắc ai cũng biết) nên anh ấy nhờ bạn giúp giải bài này.
INPUT:
- Dòng tiếp theo là 3 số nguyên dương ~N, M, Q~ lần lượt là ~N~ khu vực ~M~ địa điểm chơi và ~Q~ lượt chơi ~(N, M \leq 10^3~, ~~ ~N * M \leq 10^5~ ~~ và ~~ ~Q \leq 2 * 10^5)~.
- Dòng thứ ~i~ trong ~N~ dòng tiếp theo gồm ~M~ số nguyên dương là giá trị cho ~h[i][1], ..., h[i][M]~ ~~ ~(1 \leq h[i][j] \leq 10^4)~.
- Dòng thứ ~j~ trong số ~Q~ dòng tiếp theo là 5 số nguyên dương ~x1~ ~~ ~y1~ ~~ ~x2~ ~~ ~y2~ ~~ và ~K~ ~~ lần lượt ~(x1, y1)~ là ô trái trên và ~(x2, y2)~ là ô phải dưới và quẻ bói ~K~.
OUTPUT:
- Gồm ~Q~ dòng chính là kết quả mà bạn cần phải tìm.
SAMPLE INPUT:
5 5 3
24 7 28 9 83
11 12 10 77 12
66 22 11 33 45
99 22 87 86 12
34 13 59 12 22
2 3 4 5 7
1 1 5 5 12
4 5 4 5 1
SAMPLE OUTPUT:
77
22
12
Các Subtask:
- Subtask 1 (20%): ~N~, ~M~, ~Q~ ~\leq~ ~200~.
- Subtask 2 (20%): ~N~, ~M~ ~\leq 200~ và ~Q~ ~\leq~ ~10^3~.
- Subtask 3 (30%): Các giá trị của ~h[i][j] ~ ~\leq~ ~10~.
- Subtask 4 (30%): Không có bất kỳ ràng buộc nào thêm.
Comments
ban tach tinh con toi tach vong 2
toi ga qua mak
The ban biet lam bai nay khong