#include <bits/stdc++.h>
using namespace std;
long long poww(long long a, long long b, long long md) {
  return (!b ? 1
             : (b & 1 ? a * poww(a * a % md, b / 2, md) % md
                      : poww(a * a % md, b / 2, md) % md));
}
const long long MAXN = 1e6 + 10;
const long long INF2 = 8e18;
const long long INF = 2e18;
const long long MOD = 1e9 + 7;
const long long LOG = 22;
long long mn_r[MAXN], nxt[MAXN], P[MAXN], A[MAXN], n, m, qr;
set<long long> ind[MAXN];
long long table[MAXN][LOG];
long long walk(long long i, long long k) {
  long long j = 0;
  long long ans = i;
  while (k > 0) {
    if (k & 1) ans = table[ans][j];
    k /= 2;
    j++;
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fill(mn_r, mn_r + MAXN, INF2);
  cin >> n >> m >> qr;
  if (n == 1) {
    while (qr--) cout << 1;
    cout << '\n';
    return 0;
  }
  for (int i = 0; i < n; i++) cin >> P[i];
  nxt[P[n - 1]] = P[0];
  for (int i = 1; i < n; i++) nxt[P[i - 1]] = P[i];
  for (int i = 0; i < m; i++) cin >> A[i], ind[A[i]].insert(i);
  for (int i = 0; i < m; i++) {
    auto it = ind[nxt[A[i]]].upper_bound(i);
    if (it == ind[nxt[A[i]]].end())
      table[i][0] = m;
    else
      table[i][0] = *it;
  }
  fill(table[m], table[m] + LOG, m);
  for (int i = m - 1; i >= 0; i--) {
    long long j = 1;
    while (j < LOG) table[i][j] = table[table[i][j - 1]][j - 1], j++;
  }
  mn_r[m - 1] = m;
  for (int i = m - 2; i >= 0; i--) mn_r[i] = min(mn_r[i + 1], walk(i, n - 1));
  while (qr--) {
    long long l, r;
    cin >> l >> r;
    l--;
    r--;
    if (mn_r[l] <= r)
      cout << 1;
    else
      cout << 0;
  }
  cout << '\n';
  return 0;
}
