Covid-19

Dịch Covid-19 đã được kiểm soát, trong gần một tháng qua, tại Việt Nam không có ca nhiễm mới trong cộng đồng. Lệnh cách ly đã được nới lỏng, Hồng và các bạn được đi học trở lại, đó cũng là thời điểm thầy Phương mở trại HCC cho các bạn yêu thích lập trình, một hoạt động mà thầy đã duy trì trong nhiều năm qua. Tham gia HCC, Hồng rất thích thú với một bài toán của thầy Phương, bài toán mô phỏng việc di chuyển của virus, cụ thể bài toán như sau:

Xét lưới ô vuông kích thước $m\times n$, các dòng được đánh số từ $1$ đến $m$ từ trên xuống, các cột được đánh số từ $1$ đến $n$ từ trái sang phải. Ô nằm trên giao của dòng $i$, cột $j$ được gọi là ô $(i,j)$ và ô này chứa một số nguyên dương $a(i,j)$. Nếu một virus đang ở ô $(x,y)$, virus có thể thực hiện bước di chuyển sau:

• Virus di chuyển sang ô kề cạnh với ô $(x,y)$ nằm trong lưới, việc di chuyển này mất $1$ đơn vị thời gian;
• Virus di chuyển sang ô $(u,v)$ nằm trong lưới nếu $u\times v=a(x,y)$, việc di chuyển này mất $3$ đơn vị thời gian.

Bài toán yêu cầu tính thời gian nhỏ nhất để virus di chuyển từ ô $(p,q)$ đến ô $(r,s)$.

Đây là bài toán khó đối với Hồng nên Hồng nhờ các anh chị tham gia kỳ thi Duyên Hải năm 2020 giải giúp.

Yêu cầu: Cho lưới kích thước $m\times n$ và các số trên lưới. Có $h$ câu hỏi, với câu hỏi thứ $k$ ($k=1,2,\dots ,h$) cần phải trả lời thời gian nhỏ nhất để virus di chuyển từ ô $(p_k,q_k)$ đến ô $(r_k,s_k)$ là bao nhiêu?

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương $m,n,h$ ($h\le 5$).
• Dòng thứ $i$ ($i=1,2,\dots ,m$) trong $m$ dòng tiếp theo chứa $n$ số nguyên dương $a(i,1),a(i,2),\dots ,a(i,n)$. Các số có giá trị không vượt quá ${10}^6$.
• Dòng thứ $k$ ($k=1,2,\dots ,h$) trong $h$ dòng tiếp theo chứa bốn số nguyên $p_k,q_k,r_k,s_k$.

Dữ liệu ra

• Ghi $h$ dòng, dòng thứ $k$ ($k=1,2,\dots ,h$) ghi một số nguyên là thời gian nhỏ nhất để virus di chuyển từ ô $(p_k,q_k)$ đến ô $(r_k,s_k)$.

Ràng buộc

• Có $20\%$ số lượng test ứng với $20\%$ số điểm thỏa mãn điều kiện: $m\times n\le {10}^2$.
• Có $20\%$ số lượng test khác ứng với $20\%$ số điểm thỏa mãn điều kiện: $m\times n\le {10}^3$.
• Có $20\%$ số lượng test ứng khác với $20\%$ số điểm thỏa mãn điều kiện: $m\times n\le {10}^4$.
• Có $20\%$ số lượng test khác ứng với $20\%$ số điểm thỏa mãn điều kiện: $m\times n\le {10}^5$.
• Có $20\%$ số lượng test còn lại ứng với $20\%$ số điểm thỏa mãn điều kiện: $m\times n\le {10}^6$.

Ví dụ