{"problem":{"name":"Practical Skill Test","description":{"content":"We have a grid with $H$ rows and $W$ columns. The square at the $i$\\-th row and the $j$\\-th column will be called Square $(i,j)$. The integers from $1$ through $H×W$ are written throughout the grid, a","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc089_d"},"statements":[{"statement_type":"Markdown","content":"We have a grid with $H$ rows and $W$ columns. The square at the $i$\\-th row and the $j$\\-th column will be called Square $(i,j)$.\nThe integers from $1$ through $H×W$ are written throughout the grid, and the integer written in Square $(i,j)$ is $A_{i,j}$.\nYou, a magical girl, can teleport a piece placed on Square $(i,j)$ to Square $(x,y)$ by consuming $|x-i|+|y-j|$ magic points.\nYou now have to take $Q$ practical tests of your ability as a magical girl.\nThe $i$\\-th test will be conducted as follows:\n\n*   Initially, a piece is placed on the square where the integer $L_i$ is written.\n    \n*   Let $x$ be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer $x+D$ is written, as long as $x$ is not $R_i$. The test ends when $x=R_i$.\n    \n*   Here, it is guaranteed that $R_i-L_i$ is a multiple of $D$.\n    \n\nFor each test, find the sum of magic points consumed during that test.\n\n## Constraints\n\n*   $1 \\leq H,W \\leq 300$\n*   $1 \\leq D \\leq H×W$\n*   $1 \\leq A_{i,j} \\leq H×W$\n*   $A_{i,j} \\neq A_{x,y} ((i,j) \\neq (x,y))$\n*   $1 \\leq Q \\leq 10^5$\n*   $1 \\leq L_i \\leq R_i \\leq H×W$\n*   $(R_i-L_i)$ is a multiple of $D$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$ $D$\n$A_{1,1}$ $A_{1,2}$ $...$ $A_{1,W}$\n$:$\n$A_{H,1}$ $A_{H,2}$ $...$ $A_{H,W}$\n$Q$\n$L_1$ $R_1$\n$:$\n$L_Q$ $R_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc089_d","tags":[],"sample_group":[["3 3 2\n1 4 3\n2 5 7\n8 9 6\n1\n4 8","5\n\n*   $4$ is written in Square $(1,2)$.\n    \n*   $6$ is written in Square $(3,3)$.\n    \n*   $8$ is written in Square $(3,1)$.\n    \n\nThus, the sum of magic points consumed during the first test is $(|3-1|+|3-2|)+(|3-3|+|1-3|)=5$."],["4 2 3\n3 7\n1 4\n5 2\n6 8\n2\n2 2\n2 2","0\n0\n\nNote that there may be a test where the piece is not moved at all, and there may be multiple identical tests."],["5 5 4\n13 25 7 15 17\n16 22 20 2 9\n14 11 12 1 19\n10 6 23 8 18\n3 21 5 24 4\n3\n13 13\n2 10\n13 13","0\n5\n0"]],"created_at":"2026-03-03 11:01:13"}}