Problem: Yash is finally tired of computing the length of the longest Fibonacci-ish sequence. He now plays around with more complex things such as Fibonacci-ish potentials. 

Fibonacci-ish potential of an array ai is computed as follows: 

  1. Remove all elements j if there exists i < j such that ai = aj. 
  2. Sort the remaining elements in ascending order, i.e. a1 < a2 < ... < an. 
  3. Compute the potential as P(a) = a1·F1 + a2·F2 + ... + an·Fn, where Fi is the i-th Fibonacci number (see notes for clarification). 



You are given an array ai of length n and q ranges from lj to rj. For each range j you have to compute the Fibonacci-ish potential of the array bi, composed using all elements of ai from lj to rj inclusive. Find these potentials modulo m.

Input

The first line of the input contains integers of n and m (1 ≤ n, m ≤ 30 000) — the length of the initial array and the modulo, respectively.

The next line contains n integers ai (0 ≤ ai ≤ 109) — elements of the array.

Then follow the number of ranges q (1 ≤ q ≤ 30 000).

Last q lines contain pairs of indices li and ri (1 ≤ li ≤ ri ≤ n) — ranges to compute Fibonacci-ish potentials.

Output

Print q lines, i-th of them must contain the Fibonacci-ish potential of the i-th range modulo m.

Example

Input

5 10
2 1 2 1 2
2
2 4
4 5


Output

3
3

Note

For the purpose of this problem define Fibonacci numbers as follows: 

  1. F1 = F2 = 1. 
  2. Fn = Fn - 1 + Fn - 2 for each n > 2. 



In the first query, the subarray [1,2,1] can be formed using the minimal set {1,2}. Thus, the potential of this subarray is 1*1+2*1=3.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
std::mt19937 rng(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
struct LazyContext {
  LazyContext() {}
  void reset() {}
  void operator+=(LazyContext o) {}
};
int mod;
struct modBase {
  modBase(int v = 0) : val(v) {}
  int val;
  void operator+=(modBase o) { *this = *this + o; }
  void operator-=(modBase o) { *this = *this - o; }
  void operator*=(modBase o) { *this = *this * o; }
  modBase operator*(modBase o) { return (int)(val * o.val % mod); }
  modBase operator+(modBase o) {
    return val + o.val >= mod ? val + o.val - mod : val + o.val;
  }
  modBase operator-(modBase o) {
    return val - o.val < 0 ? val - o.val + mod : val - o.val;
  }
};
struct Info {
  Info(int x) {
    val = x;
    recalc();
  }
  void recalc() {
    if (freq <= 0) {
      a[0] = 1, a[1] = 0;
      b[0] = b[1] = 0;
    } else {
      a[0] = 0, a[1] = 1;
      b[0] = 0, b[1] = val % mod;
    }
  }
  Info(Info l, Info r) {
    a[0] = l.a[0] * r.a[0] + l.a[1] * r.a[1];
    a[1] = l.a[1] * r.a[0] + l.a[0] * r.a[1] + l.a[1] * r.a[1];
    b[0] = l.a[0] * r.b[0] + l.a[1] * r.b[1] + l.b[0];
    b[1] = l.a[1] * r.b[0] + l.a[0] * r.b[1] + l.a[1] * r.b[1] + l.b[1];
  }
  void apply(LazyContext lazy, int size) {}
  void rotate() {}
  bool operator<(const Info& o) const { return val < o.val; }
  modBase a[2];
  modBase b[2];
  int freq = 0;
  int val;
};
template <class i_t, class lazy_cont>
struct SplayTree {
  struct Node {
    Node *p = NULL, *left = NULL, *right = NULL;
    int size = 1;
    bool flip = false;
    i_t base, info;
    lazy_cont lazy;
    Node(i_t v) : base(v), info(v) {}
    ~Node() {
      if (left) delete left;
      if (right) delete right;
    }
    void applyLazy(lazy_cont l) {
      info.apply(l, size);
      base.apply(l, 1);
      lazy += l;
    }
    void fix() {
      push(), info = base;
      size = 1;
      if (left)
        info = i_t(left->info, info), size += left->size, left->p = this;
      if (right)
        info = i_t(info, right->info), size += right->size, right->p = this;
    }
    Node* splay() {
      pull();
      while (p) {
        Node *y = p, *z = p->p;
        bool t1 = (y->left != this);
        bool t2 = z && (z->left != y) == t1;
        if (t2) y->rotate(t1);
        rotate(t1);
        if (z && !t2) rotate(!t1);
      }
      fix();
      return this;
    }
    void push() {
      if (flip) {
        std::swap(left, right);
        if (left) left->flip = !left->flip, left->info.rotate();
        if (right) right->flip = !right->flip, right->info.rotate();
        flip = false;
      }
      if (left) left->applyLazy(lazy);
      if (right) right->applyLazy(lazy);
      lazy.reset();
    }
    void pull() {
      if (p) {
        p->pull();
      }
      push();
    }
    void rotate(bool leftRotate) {
      Node *y = p, *z = p->p, *&w = leftRotate ? left : right;
      if (z) (z->right == y ? z->right : z->left) = this;
      if (w) w->p = y;
      (leftRotate ? y->right : y->left) = w;
      w = y;
      p = z;
      y->p = this;
      y->fix();
    }
  };
  Node* root;
  SplayTree(Node* r = NULL) : root(r) {}
  Node* lower_bound(i_t val) {
    return search(val, [](const i_t& a, const i_t& b) { return !(b < a); });
  }
  Node* upper_bound(i_t val) {
    return search(val, [](const i_t& a, const i_t& b) { return a < b; });
  }
  Node* splayFirst() { return expose(1); }
  Node* splayLast() { return expose(1e9); }
  Node* expose(int k) {
    Node* cur = root;
    if (!cur) return NULL;
    k = std::min(k, cur->size);
    k = std::max(k, 1);
    while (cur) {
      cur->push();
      if (cur->left) {
        if (cur->left->size >= k) {
          cur = cur->left;
          continue;
        } else {
          k -= cur->left->size;
        }
      }
      if (k == 1) {
        break;
      }
      k--;
      cur = cur->right;
    }
    assert(cur);
    return root = cur->splay();
  }
  template <class F>
  Node* search(i_t val, F f) {
    Node *ans = NULL, *cur = root, *last = NULL;
    while (cur) {
      cur->push();
      last = cur;
      if (f(val, cur->base)) {
        ans = cur;
        cur = cur->left;
      } else {
        cur = cur->right;
      }
    }
    root = last->splay();
    if (ans) root = ans->splay();
    return ans;
  }
  void insert(i_t t) { insert(new Node(t)); }
  void insert(Node* node) {
    if (!root) {
      root = node;
      return;
    }
    Node* tree = root;
    while (1) {
      tree->push();
      Node*& w = node->base < tree->base ? tree->left : tree->right;
      if (w) {
        tree = w;
      } else {
        w = node;
        tree->fix();
        break;
      }
    }
    root = node->splay();
  }
  void erase(Node* node) {
    node->pull();
    if (node == root) {
      if (node->left) node->left->p = NULL;
      if (node->right) node->right->p = NULL;
      *this = SplayTree(node->left) + SplayTree(node->right);
    } else {
      assert(node->p);
      Node*& w = node->p->left == node ? node->p->left : node->p->right;
      if (!node->left || !node->right) {
        w = node->left ? node->left : node->right;
      } else {
        node->left->p = node->right->p = NULL;
        w = (SplayTree(node->left) + SplayTree(node->right)).root;
      }
      node->p->fix();
      root = node->p->splay();
    }
  }
  SplayTree operator+(SplayTree o) {
    if (!root) return o;
    if (!o.root) return *this;
    splayLast();
    assert(!root->right && !o.root->p);
    root->right = o.root;
    root->fix();
    return SplayTree(root);
  }
};
inline int64_t hilbertOrder(int x, int y, int pow, int rotate) {
  if (pow == 0) {
    return 0;
  }
  int hpow = 1 << (pow - 1);
  int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
  seg = (seg + rotate) & 3;
  const int rotateDelta[4] = {3, 0, 0, 1};
  int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
  int nrot = (rotate + rotateDelta[seg]) & 3;
  int64_t subSquareSize = int64_t(1) << (2 * pow - 2);
  int64_t ans = seg * subSquareSize;
  int64_t add = hilbertOrder(nx, ny, pow - 1, nrot);
  ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
  return ans;
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int n, m;
  std::cin >> n >> mod;
  std::map<int, SplayTree<Info, LazyContext>::Node*> st;
  SplayTree<Info, LazyContext> tree;
  struct Query {
    int l, r;
    int id;
    void read() {
      std::cin >> l >> r;
      l--;
    }
    bool operator<(const Query& o) const {
      return hilbertOrder(l, r, 21, 0) < hilbertOrder(o.l, o.r, 21, 0);
    }
  };
  std::vector<int> a(n);
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
    if (!st.count(a[i])) {
      tree.insert(Info(a[i]));
      st[a[i]] = tree.root;
      assert(tree.root->base.val == a[i]);
    }
  }
  std::cin >> m;
  std::vector<Query> qries(m);
  for (int i = 0; i < m; i++) {
    qries[i].read();
    qries[i].id = i;
  }
  std::sort(qries.begin(), qries.end());
  std::vector<int> ans(m, -1);
  int l = 0, r = 0;
  auto add = [&](int x, int f) {
    auto node = st[x];
    node->base.freq += f;
    if (node->base.freq == f || node->base.freq == 0) {
      tree.root = node->splay();
      assert(node && node->base.val == x && tree.root == node);
      node->base.recalc();
      node->fix();
    }
  };
  for (auto qry : qries) {
    while (l > qry.l) add(a[--l], 1);
    while (r < qry.r) add(a[r++], 1);
    while (r > qry.r) add(a[--r], -1);
    while (l < qry.l) add(a[l++], -1);
    ans[qry.id] = tree.root->info.b[1].val;
  }
  for (int i = 0; i < m; i++) {
    std::cout << ans[i] << '\n';
  }
}