AT_abc089_d [ABC089D] Practical Skill Test

[problemUrl]: https://atcoder.jp/contests/abc089/tasks/abc089_d $ H $ 行 $ W $ 列のマス目があり、$ i $ 行目の $ j $ 列目のマスをマス $ (i,j) $ と呼びます。 このマス目には $ 1 $ から $ H×W $ までの整数が重複なく書かれており、マス $ (i,j) $ に書かれている整数は $ A_{i,j} $ です。 魔法少女であるあなたは、魔力 $ |x-i|+|y-j| $ を消費することでマス $ (i,j) $ に置かれた駒をマス $ (x,y) $ に瞬間移動させることができます。 あなたは、魔法少女としての能力を計るために、$ Q $ 回の実技試験を受けなければなりません。 $ i $ 回目の実技試験は、以下の手順で行われます。 - 初めに、駒が整数 $ L_i $ の書かれているマスに置かれている。 - 駒の置かれているマスに書かれている整数を $ x $ とする。$ x $ が $ R_i $ でない限り、駒を $ x+D $ の書かれているマスに移動することを繰り返す。$ x=R_i $ となったら終了する。 - ただし、$ R_i-L_i $ が $ D $ の倍数であることは保証される。 それぞれの実技試験に対し、あなたの消費する魔力の総和を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ D $ $ A_{1,1} $ $ A_{1,2} $ $ ... $ $ A_{1,W} $ $ : $ $ A_{H,1} $ $ A_{H,2} $ $ ... $ $ A_{H,W} $ $ Q $ $ L_1 $ $ R_1 $ $ : $ $ L_Q $ $ R_Q $

それぞれの実技試験に対し、あなたの消費する魔力の総和を出力せよ。 ただし、出力する順番は実技試験の行われる順とすること。

### 制約 - $ 1\ \leq\ H,W\ \leq\ 300 $ - $ 1\ \leq\ D\ \leq\ H×W $ - $ 1\ \leq\ A_{i,j}\ \leq\ H×W $ - $ A_{i,j}\ \neq\ A_{x,y}\ ((i,j)\ \neq\ (x,y)) $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ H×W $ - $ (R_i-L_i) $ は $ D $ の倍数 ### Sample Explanation 1 \- $ 4 $ が書かれたマスは、マス $ (1,2) $ です。 - $ 6 $ が書かれたマスは、マス $ (3,3) $ です。 - $ 8 $ が書かれたマスは、マス $ (3,1) $ です。 よって、$ 1 $ 回目の実技試験であなたの消費する魔力の総和は、$ (|3-1|+|3-2|)+(|3-3|+|1-3|)=5 $ です。 ### Sample Explanation 2 駒を全く移動しない実技試験が存在する場合や、複数の実技試験の内容が同じ場合に注意してください。