Recently Lynyrd and Skynyrd went to a shop where Lynyrd bought a permutation p of length n, and Skynyrd bought an array a of length m, consisting of integers from 1 to n. 

Lynyrd and Skynyrd became bored, so they asked you q queries, each of which has the following form: "does the subsegment of a from the l-th to the r-th positions, inclusive, have a subsequence that is a cyclic shift of p?" Please answer the queries.

A permutation of length n is a sequence of n integers such that each integer from 1 to n appears exactly once in it.

A cyclic shift of a permutation (p_1, p_2, …, p_n) is a permutation (p_i, p_{i + 1}, …, p_{n}, p_1, p_2, …, p_{i - 1}) for some i from 1 to n. For example, a permutation (2, 1, 3) has three distinct cyclic shifts: (2, 1, 3), (1, 3, 2), (3, 2, 1).

A subsequence of a subsegment of array a from the l-th to the r-th positions, inclusive, is a sequence a_{i_1}, a_{i_2}, …, a_{i_k} for some i_1, i_2, …, i_k such that l ≤ i_1 < i_2 < … < i_k ≤ r.

Input

The first line contains three integers n, m, q (1 ≤ n, m, q ≤ 2 ⋅ 10^5) — the length of the permutation p, the length of the array a and the number of queries.

The next line contains n integers from 1 to n, where the i-th of them is the i-th element of the permutation. Each integer from 1 to n appears exactly once.

The next line contains m integers from 1 to n, the i-th of them is the i-th element of the array a.

The next q lines describe queries. The i-th of these lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ m), meaning that the i-th query is about the subsegment of the array from the l_i-th to the r_i-th positions, inclusive.

Output

Print a single string of length q, consisting of 0 and 1, the digit on the i-th positions should be 1, if the subsegment of array a from the l_i-th to the r_i-th positions, inclusive, contains a subsequence that is a cyclic shift of p, and 0 otherwise.

Examples

Input

3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5


Output

110


Input

2 4 3
2 1
1 1 2 2
1 2
2 3
3 4


Output

010

Note

In the first example the segment from the 1-st to the 5-th positions is 1, 2, 3, 1, 2. There is a subsequence 1, 3, 2 that is a cyclic shift of the permutation. The subsegment from the 2-nd to the 6-th positions also contains a subsequence 2, 1, 3 that is equal to the permutation. The subsegment from the 3-rd to the 5-th positions is 3, 1, 2, there is only one subsequence of length 3 (3, 1, 2), but it is not a cyclic shift of the permutation.

In the second example the possible cyclic shifts are 1, 2 and 2, 1. The subsegment from the 1-st to the 2-nd positions is 1, 1, its subsequences are not cyclic shifts of the permutation. The subsegment from the 2-nd to the 3-rd positions is 1, 2, it coincides with the permutation. The subsegment from the 3 to the 4 positions is 2, 2, its subsequences are not cyclic shifts of the permutation.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ll = long long int;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using cdouble = complex<double>;
const double eps = 1e-7;
bool feq(double x, double y) { return abs(x - y) <= eps; }
bool inrange(ll x, ll t) { return x >= 0 && x < t; }
bool inrange(vll xs, ll t) {
  for (auto x : xs)
    if (!(x >= 0 && x < t)) return false;
  return true;
}
int ceillog2(ll x) {
  int ret = 0;
  x--;
  while (x > 0) {
    ret++;
    x >>= 1;
  }
  return ret;
}
ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); }
ll floorsqrt(ll x) {
  ll m = (ll)sqrt((double)x);
  return m + (m * m <= x ? 0 : -1);
}
ll ceilsqrt(ll x) {
  ll m = (ll)sqrt((double)x);
  return m + (x <= m * m ? 0 : 1);
}
ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); }
ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); }
ll gcd(ll m, ll n) {
  if (n == 0)
    return m;
  else
    return gcd(n, m % n);
}
ll lcm(ll m, ll n) { return m * n / gcd(m, n); }
class Ancestor {
 private:
  int n;
  vvi lst;
  vvi table;
  vi from;
  vi visited, departed;
  deque<int> deq;
  void dfs(int a, int &t) {
    for (int i = 0; i < deq.size(); i = i * 2 + 1) {
      table[a].push_back(deq[i]);
    }
    visited[a] = t++;
    deq.push_front(a);
    for (auto b : lst[a]) {
      if (from[b] == INT_MIN) {
        from[b] = a;
        dfs(b, t);
      }
    }
    deq.pop_front();
    departed[a] = t++;
  }

 public:
  Ancestor(const vvi &lst, vi roots = {0}) {
    n = lst.size();
    this->lst = lst;
    table = vvi(n);
    from = vi(n, INT_MIN);
    visited.resize(n);
    departed.resize(n);
    int t = 0;
    for (auto root : roots) {
      from[root] = -1;
      dfs(root, t);
    }
  }
  bool is_ancestor(int des, int anc) {
    return visited[anc] < visited[des] && departed[des] < departed[anc];
  }
  int lowest_common_ancestor(int x, int y) {
    if (x == y) return x;
    if (is_ancestor(x, y)) return y;
    if (is_ancestor(y, x)) return x;
    for (int i = 1; i <= int(table[x].size() - 1); i++) {
      if (is_ancestor(y, table[x][i])) {
        return lowest_common_ancestor(table[x][i - 1], y);
      }
    }
    return lowest_common_ancestor(table[x].back(), y);
  }
  int get_ancestor(int des, int k) {
    if (k == 0) return des;
    int l = int(log2(k));
    if (l >= table[des].size())
      return -1;
    else
      return get_ancestor(table[des][l], k - (1 << l));
  }
  template <typename bsargv_t>
  int upper_bsearch(int des, const bsargv_t &v,
                    bool (*evalfunc)(int, const bsargv_t &)) {
    if (evalfunc(des, v)) return des;
    if (table[des].size() == 0) return -1;
    for (int i = 1; i <= int(table[des].size() - 1); i++) {
      if (evalfunc(table[des][i], v)) {
        return upper_bsearch(table[des][i - 1], v, evalfunc);
      }
    }
    return upper_bsearch(table[des].back(), v, evalfunc);
  }
  template <typename bsargv_t>
  int lower_bsearch(int des, const bsargv_t &v,
                    bool (*evalfunc)(int, const bsargv_t &)) {
    if (!evalfunc(des, v)) return -1;
    if (table[des].size() == 0) return des;
    for (int i = 0; i < int(table[des].size()); i++) {
      if (!evalfunc(table[des][i], v)) {
        if (i == 0)
          return des;
        else
          return lower_bsearch(table[des][i - 1], v, evalfunc);
      }
    }
    return lower_bsearch(table[des].back(), v, evalfunc);
  }
};
class SegTree {
 private:
  struct val_t {
    bool enable;
    ll upd, add, min;
  };
  int n, N;
  int base;
  vector<val_t> nodes;
  int left_of(int id) {
    if (id >= base)
      return -1;
    else
      return id * 2 + 1;
  }
  int right_of(int id) {
    if (id >= base)
      return -1;
    else
      return id * 2 + 2;
  }
  int parent_of(int id) {
    if (id == 0)
      return -1;
    else
      return (id - 1) >> 1;
  }
  void merge(int id, int id_l, int id_r) {
    nodes[id].min = min(nodes[id_l].min + nodes[id_l].add,
                        nodes[id_r].min + nodes[id_r].add);
  }
  void lazy_rec(int s, int t, int l, int r, int id, ll upd, ll add,
                bool enable) {
    if (s == l && t == r) {
      if (enable)
        nodes[id] = {true, upd, add, upd};
      else
        nodes[id].add += add;
    } else {
      int m = (l + r) / 2;
      int id_l = left_of(id);
      int id_r = right_of(id);
      if (!enable) {
        add += nodes[id].add;
        if (nodes[id].enable) {
          upd = nodes[id].upd;
          enable = true;
        }
      }
      nodes[id].enable = false;
      nodes[id].add = 0;
      if (s < m && m < t) {
        lazy_rec(s, m, l, m, id_l, upd, add, enable);
        lazy_rec(m, t, m, r, id_r, upd, add, enable);
      } else if (s < m) {
        lazy_rec(s, t, l, m, id_l, upd, add, enable);
        lazy_rec(0, 0, 0, 0, id_r, upd, add, enable);
      } else if (m < t) {
        lazy_rec(0, 0, 0, 0, id_l, upd, add, enable);
        lazy_rec(s, t, m, r, id_r, upd, add, enable);
      }
      merge(id, id_l, id_r);
    }
  }
  enum change_t { UPD, ADD };
  void change_rec(int s, int t, int l, int r, int id, ll x, change_t op) {
    if (s == l && t == r) {
      if (op == UPD)
        nodes[id] = {
            true,
            x,
            0,
            x,
        };
      else if (op == ADD)
        nodes[id].add += x;
    } else {
      int m = (l + r) / 2;
      int id_l = left_of(id);
      int id_r = right_of(id);
      if (s < m && m < t) {
        change_rec(s, m, l, m, id_l, x, op);
        change_rec(m, t, m, r, id_r, x, op);
      } else if (s < m) {
        change_rec(s, t, l, m, id_l, x, op);
      } else if (m < t) {
        change_rec(s, t, m, r, id_r, x, op);
      }
      merge(id, id_l, id_r);
    }
  }
  enum solve_t { MIN };
  ll solve_rec(int s, int t, int l, int r, int id, solve_t op) {
    ll v = 0;
    if (s == l && t == r) {
      if (op == MIN) v = nodes[id].min;
    } else {
      int m = (l + r) / 2;
      int id_l = left_of(id);
      int id_r = right_of(id);
      if (s < m && m < t) {
        ll v0 = solve_rec(s, m, l, m, id_l, op);
        ll v1 = solve_rec(m, t, m, r, id_r, op);
        if (op == MIN) v = min(v0, v1);
      } else if (s < m) {
        v = solve_rec(s, t, l, m, id_l, op);
      } else if (m < t) {
        v = solve_rec(s, t, m, r, id_r, op);
      }
    }
    if (op == MIN) v += nodes[id].add;
    return v;
  }
  void lazy(int s, int t) { lazy_rec(s, t, 0, N, 0, 0, 0, false); }

 public:
  SegTree(int n, ll init) {
    this->n = n;
    N = (int)pow(2, ceil(log2(n)));
    base = N - 1;
    nodes = vector<val_t>(base + N, {false, 0, 0, LLONG_MAX});
    upd(0, n, init);
  }
  int cover_size(int id) {
    int cnt = 1;
    while (left_of(id) != -1) {
      id = left_of(id);
      cnt *= 2;
    }
    int l = id - base;
    int r = min(l + cnt, n);
    return max(0, r - l);
  }
  void upd(int s, int t, ll x) {
    lazy(s, t);
    change_rec(s, t, 0, N, 0, x, UPD);
  }
  void add(int s, int t, ll x) {
    lazy(s, t);
    change_rec(s, t, 0, N, 0, x, ADD);
  }
  ll minof(int s, int t) {
    lazy(s, t);
    return solve_rec(s, t, 0, N, 0, MIN);
  }
};
int main() {
  int n, m, q;
  cin >> n >> m >> q;
  vi p(n);
  vi next(n);
  for (int i = 0; i < int(n); i++) {
    cin >> p[i];
    p[i]--;
  }
  for (int i = 0; i < int(n); i++) {
    if (i == n - 1)
      next[p[i]] = p[0];
    else
      next[p[i]] = p[i + 1];
  }
  vi a(m);
  vvi occ(n);
  for (int i = 0; i < int(m); i++) {
    cin >> a[i];
    a[i]--;
    occ[a[i]].push_back(i);
  }
  vvi lst(m);
  vi roots;
  for (int i = 0; i < int(m); i++) {
    auto itr = upper_bound(occ[next[a[i]]].begin(), occ[next[a[i]]].end(), i);
    if (itr == occ[next[a[i]]].end())
      roots.push_back(i);
    else {
      lst[i].push_back(*itr);
      lst[*itr].push_back(i);
    }
  }
  Ancestor *anc = new Ancestor(lst, roots);
  vi r(m);
  for (int i = 0; i < int(m); i++) {
    r[i] = anc->get_ancestor(i, n - 1);
    if (r[i] == -1) r[i] = INT_MAX;
  }
  SegTree *st = new SegTree(m, INT_MAX);
  for (int i = 0; i < int(m); i++) {
    st->upd(i, i + 1, r[i]);
  }
  string ans;
  for (int _ = 0; _ < int(q); _++) {
    int l, r;
    cin >> l >> r;
    l--;
    int min_r = st->minof(l, r);
    if (min_r < r)
      ans += '1';
    else
      ans += '0';
  }
  cout << ans << endl;
}
