#include <bits/stdc++.h>
using namespace std;
int n, m, q, g[200020][22], f[200020][22], lg[200020], aa[200020], bb[200020],
    pos[200020], last[200020], L, tot = 0, ss[200020];
int main() {
  ios::sync_with_stdio(false);
  int i, j, k, l, r, cur, ans, u;
  cin >> n >> m >> q;
  for (i = 1; i <= n; i++) {
    cin >> aa[i];
    pos[aa[i]] = i;
  }
  for (i = 1; i <= m; i++) {
    cin >> bb[i];
    last[bb[i]] = i;
    k = pos[bb[i]] - 1;
    if (!k) k = n;
    f[i][0] = last[aa[k]];
  }
  for (i = 1; (1 << i) <= n; i++)
    for (j = 1; j <= m; j++) f[j][i] = max(f[j][i], f[f[j][i - 1]][i - 1]);
  for (i = 1; i <= m; i++) {
    L = n - 1;
    cur = i;
    for (j = 20; j >= 0; j--) {
      if (L >= (1 << j)) {
        L = L - (1 << j);
        cur = f[cur][j];
      }
    }
    g[i][0] = cur;
  }
  for (i = 1; (1 << i) <= m; i++)
    for (j = 1; j + (1 << i) - 1 <= m; j++)
      g[j][i] = max(g[j + (1 << (i - 1))][i - 1], g[j][i - 1]);
  lg[1] = 0;
  for (i = 2; i <= m; i++) lg[i] = lg[i >> 1] + 1;
  while (q--) {
    cin >> l >> r;
    u = lg[r - l + 1];
    ans = max(g[l][u], g[r - (1 << u) + 1][u]);
    if (ans >= l)
      ss[++tot] = 1;
    else
      ss[++tot] = 0;
  }
  for (i = 1; i <= tot; i++) cout << ss[i];
  cout << endl;
  return 0;
}
