#include <bits/stdc++.h>
using namespace std;
int Read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, m, q, a[200005], b[200005], f[200005], g[200005], h[200005],
    minn[800005], rev[200005];
vector<int> pos[200005], pos2[200005];
void build(int o, int l, int r) {
  if (l == r) {
    minn[o] = (g[l] == -1) ? 1E9 : g[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(o << 1, l, mid);
  build(o << 1 | 1, mid + 1, r);
  minn[o] = min(minn[o << 1], minn[o << 1 | 1]);
}
int query(int o, int l, int r, int nl, int nr) {
  if (nl <= l && r <= nr) return minn[o];
  int mid = (l + r) >> 1, ans = 1E9;
  if (nl <= mid) ans = min(ans, query(o << 1, l, mid, nl, nr));
  if (mid < nr) ans = min(ans, query(o << 1 | 1, mid + 1, r, nl, nr));
  return ans;
}
signed main() {
  n = Read(), m = Read(), q = Read();
  for (int i = 1; i <= n; i++) a[i] = Read(), rev[a[i]] = i;
  for (int i = 1; i <= m; i++) b[i] = Read(), pos[b[i]].push_back(i);
  memset(f, -1, sizeof(f));
  memset(g, -1, sizeof(g));
  memset(h, -1, sizeof(h));
  for (int i = n; i >= 1; i--) {
    if (i == n) {
      for (int j = 0; j < pos[a[i]].size(); j++) f[pos[a[i]][j]] = pos[a[i]][j];
      continue;
    }
    for (int j = 0; j < pos[a[i]].size(); j++) {
      vector<int>::iterator it =
          lower_bound(pos[a[i + 1]].begin(), pos[a[i + 1]].end(), pos[a[i]][j]);
      if (it == pos[a[i + 1]].end()) continue;
      f[pos[a[i]][j]] = f[*it];
    }
  }
  for (int i = 1; i <= n; i++) {
    if (i == 1) {
      for (int j = 0; j < pos[a[i]].size(); j++) h[pos[a[i]][j]] = pos[a[i]][j];
      continue;
    }
    for (int j = 0; j < pos[a[i]].size(); j++) {
      vector<int>::iterator it =
          lower_bound(pos[a[i - 1]].begin(), pos[a[i - 1]].end(), pos[a[i]][j]);
      if (it == pos[a[i - 1]].begin()) continue;
      --it;
      h[pos[a[i]][j]] = h[*it];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < pos[a[i]].size(); j++)
      pos2[a[i]].push_back(h[pos[a[i]][j]]);
  }
  for (int i = 1; i <= m; i++) {
    int ff = rev[b[i]];
    if (ff == 1) {
      g[i] = f[i];
      continue;
    }
    if (f[i] == -1) continue;
    vector<int>::iterator it =
        lower_bound(pos2[a[ff - 1]].begin(), pos2[a[ff - 1]].end(), f[i]);
    if (it == pos2[a[ff - 1]].end()) continue;
    int Pos = it - pos2[a[ff - 1]].begin();
    g[i] = pos[a[ff - 1]][Pos];
  }
  build(1, 1, m);
  for (int i = 1; i <= q; i++) {
    int l = Read(), r = Read();
    int mpos = query(1, 1, m, l, r);
    if (mpos <= r)
      putchar('1');
    else
      putchar('0');
  }
  return 0;
}
