#include <bits/stdc++.h>
using namespace std;
struct SparseTable {
  int n, k;
  vector<vector<long long> > st;
  vector<long long> x, y;
  SparseTable(){};
  SparseTable(vector<long long> a) {
    n = k = 1;
    while (n < a.size()) n *= 2, ++k;
    st.assign(k, vector<long long>(n, 0));
    for (int j = 0; j < a.size(); ++j) st[0][j] = a[j];
    for (int i = 1, l = 1; i < k; ++i, l *= 2)
      for (int j = 0; j < n - 2 * l + 1; ++j)
        st[i][j] = min(st[i - 1][j], st[i - 1][j + l]);
    x.assign(n, 0);
    y.assign(n, 0);
    for (int i = 0, l = 1; i < k; ++i, l *= 2) {
      x[l - 1] = i;
      y[l - 1] = l;
    }
    for (int i = 1; i < n; ++i) {
      if (x[i]) continue;
      x[i] = x[i - 1];
      y[i] = y[i - 1];
    }
  }
  int get_min(int l, int r) {
    int i = r - l;
    return min(st[x[i]][l], st[x[i]][r - y[i] + 1]);
  }
};
int n, m, q, l, r;
vector<long long> p, inv, nex, a, b, h;
vector<vector<long long> > bp;
string s;
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m >> q;
  p.resize(n);
  inv.resize(n + 1);
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
    inv[p[i]] = (i + 1) % n;
  }
  a.resize(m);
  for (int i = 0; i < m; ++i) cin >> a[i];
  h.assign(n + 1, m);
  nex.assign(m + 1, m);
  for (int i = m - 1; i >= 0; --i) {
    nex[i] = h[p[inv[a[i]]]];
    h[a[i]] = i;
  }
  bp.assign(20, vector<long long>(m + 1, m));
  bp[0] = nex;
  for (int i = m - 1; i >= 0; --i)
    for (int k = 1; k < 20; ++k) bp[k][i] = bp[k - 1][bp[k - 1][i]];
  b.assign(m, m);
  for (int i = m - 1; i >= 0; --i) {
    int x = n - 1;
    int j = i;
    for (int k = 0; k < 20; ++k) {
      if ((x & (1 << k)) == 0) continue;
      j = bp[k][j];
    }
    b[i] = j;
  }
  SparseTable st(b);
  s = string(q, '0');
  for (int o = 0; o < q; ++o) {
    cin >> l >> r;
    --l;
    --r;
    if (st.get_min(l, r) <= r) s[o] = '1';
  }
  cout << s;
  return 0;
}
