{"code":"dialgrid","name":"Thuật toán Dial trên lưới","description":"Cho một lưới gồm $m$ hàng, $n$ cột. Bạn Hiếu có $k$ lọ sơn, và với mỗi ô, bạn sẽ chọn một trong số $k$ màu để tô lên.\r\n\r\nTừ một ô có thể đi sang các ô kề cạnh. Cụ thể hơn, từ ô $(x, y)$, chúng ta có thể đi sang ô $(x-1, y), (x, y-1), (x, y+1), (x+1, y)$.\r\n\r\nĐể đi từ ô có màu $x$ sang ô có màu $y$, chi phí dịch chuyển là $c_{xy}$. Lưu ý, $c_{xy}$ có thể khác $c_{yx}$.\r\n\r\nHãy trả lời $q$ câu hỏi, mỗi câu có dạng \"Chi phí thấp nhất để đi từ ô $(u, v)$ tới ô $(x, y)$ là bao nhiêu?\".\r\n\r\n

Input

\r\n\r\n- Dòng đầu chứa 3 số $m, n, k$\r\n- $m$ dòng sau, dòng thứ $i$ chứa n số: $a_{i1}, a_{i2}, \\dots, a_{in}$ biểu thị màu của từng ô.\r\n- k dòng sau, dòng thứ i chứa k số: $c_{i1}, c_{i2}, \\dots, c_{ik}$. $c_{ij}$ là chi phí chuyển từ ô màu i sang ô màu j.\r\n- Dòng tiếp theo chứa số $q$\r\n- $q$ dòng cuối, dòng thứ $i$ chứa 4 số $u_i, v_i, x_i, y_i$ biểu thị cho câu hỏi thứ $i$.\r\n\r\n

Output

\r\n\r\n- In ra $q$ dòng, mỗi dòng in ra đáp án của câu hỏi thứ $i$.\r\n\r\n

Constants

\r\n\r\n- $m, n \\le 2000, k \\le 4, q \\le 10$\r\n- $\\forall 1 \\le i \\le m, 1 \\le j \\le n: a_{ij} \\le 4$\r\n- $\\forall 1 \\le i,j \\le k: c_{ij} \\le 10. \\forall 1 \\le i \\le k: c_{ii} = 1$\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3 4 2\r\n 2 1 1 2\r\n 1 2 1 2\r\n 1 1 2 2\r\n 1 2\r\n 3 1\r\n 3\r\n 1 2 2 3\r\n 1 1 3 2\r\n 2 1 2 2\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 2\r\n 5\r\n 2\r\n ```","points":300.0,"partial":false,"time_limit":5.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}