// C++11
    #include <algorithm>
    #include <array>
    #include <bitset>
    #include <chrono>
    #include <cmath>
    #include <iostream>
    #include <numeric>
    #include <random>
    #include <vector>
    #include <set>
    #include <unordered_set>
     
    using namespace std;
     
    #define LOCAL 1
     
    #if LOCAL
    #define pv(val) cerr << #val << '=' << (val) << endl
    #define pvn(name, val) cerr << name << '=' << (val) << endl
    #define pl cerr << '@' << __LINE__ << endl
    #else
    #define pv(val)
    #define pvn(name, val)
    #define pl
    #endif
     
    template <class T>
    ostream& operator<<(ostream& os, vector<T> const& vec) {
      if (vec.empty()) {
        os << "{}";
      } else {
        os << '{';
        for (size_t i = 0; i < vec.size() - 1; i++) os << vec[i] << ", ";
        os << vec.back() << '}';
      }
      return os;
    }
     
    template <class T, size_t S>
    ostream& operator<<(ostream& os, array<T, S> const& arr) {
      if (arr.empty()) {
        os << "{}";
      } else {
        os << '{';
        for (size_t i = 0; i < arr.size() - 1; i++) os << arr[i] << ", ";
        os << arr.back() << '}';
      }
      return os;
    }
     
    class Timer {
      using clock = chrono::high_resolution_clock;
      clock::time_point startTime;
     
      template <class T>
      auto elapsed() const {
        return chrono::duration_cast<T>(clock::now() - startTime).count();
      }
     
     public:
      Timer() { restart(); }
     
      void restart() { startTime = clock::now(); }
     
      auto milli() const { return elapsed<chrono::milliseconds>(); }
     
      auto micro() const { return elapsed<chrono::microseconds>(); }
    };
     
    Timer globalTimer;
     
    class Xorshift128 {
      uint32_t x, y, z, w, t;
     
     public:
      using result_type = uint32_t;
     
      Xorshift128(uint32_t seed = 12433)
          : x(123456789), y(362436069), z(521288629), w(seed) {}
     
      static constexpr result_type min() {
        return std::numeric_limits<result_type>::min();
      }
     
      static constexpr result_type max() {
        return std::numeric_limits<result_type>::max();
      }
     
      result_type operator()() {
        t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
      }
    };
     
    template <typename T, typename Comp = std::less<T>>
    class PriorityQueue {
     public:
      using container = vector<T>;
      using iterator = typename container::iterator;
      using const_iterator = typename container::const_iterator;
     
     private:
      container queue_;
      size_t last_;
     
     public:
      PriorityQueue() { last_ = 0; }
     
      size_t size() const { return last_; }
     
      const_iterator begin() const { return queue_.begin(); }
     
      const_iterator end() const { return queue_.begin() + last_; }
     
      bool full() const { return size() == capacity(); }
     
      void setCapacity(size_t n) { queue_.resize(n); }
     
      size_t capacity() const { return queue_.size(); }
     
      void push(const T& val) {
        queue_[last_] = val;
        last_++;
        std::push_heap(queue_.begin(), queue_.begin() + last_, Comp());
      }
     
      void push(T&& val) {
        queue_[last_] = std::move(val);
        last_++;
        std::push_heap(queue_.begin(), queue_.begin() + last_, Comp());
      }
     
      void clear() { last_ = 0; }
     
      T const& top() const { return queue_[0]; }
     
      void pop() {
        std::pop_heap(queue_.begin(), queue_.begin() + last_, Comp());
        last_--;
      }
    };
     
    int main(void)
    {
      vector<pair<int, int>> A;
      int H, W, D;
      cin >> H >> W >> D;
      A.resize((H+1)*(W+1));
      for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
          int a;
          cin >> a;
          a--;
          A[a] = {i, j};
        }
      }
     
      vector<vector<int>> B;
      B.resize(D+1, vector<int>(W * H / D + 1, 0));
     
      for(int d = 0; d < D; d++){
        auto& v = B[d];
     
        int x = d;
        while(x + D < W * H){
          v[(x + D) / D] = v[x / D] + abs(A[x].first - A[x + D].first) + abs(A[x].second - A[x + D].second);
          x += D;
        }
      }
     
      int Q;
      cin >> Q;
      for(int i = 0; i < Q; i++){
        int l, r;
        scanf("%d %d", &l, &r);
        l--, r--;
        int d = l % D;
        printf("%d\n", B[d][r / D] - B[d][l / D]);
      }
     
      return 0;
    }

Measured memory_bytes: 6144