#include <bits/stdc++.h>
const int N = 200005;
using namespace std;
int p[N], a[N];
int pos[N], lst[N];
int pr[20][N];
int maxp[20][N], lg[N];
int main() {
  int n, m, q;
  scanf("%d%d%d", &n, &m, &q);
  int i, j, k;
  for (i = 0; i < n; i++) {
    scanf("%d", &p[i]);
    pos[p[i]] = i;
  }
  memset(lst, -1, sizeof(lst));
  lg[1] = 0;
  for (i = 2; i <= m; i++) lg[i] = lg[i >> 1] + 1;
  for (i = 0; i < m; i++) {
    scanf("%d", &a[i]);
    lst[a[i]] = i;
    int t = p[(pos[a[i]] - 1 + n) % n];
    pr[0][i] = lst[t];
  }
  for (i = 0; i < 19; i++)
    for (j = 0; j < m; j++)
      if (pr[i][j] == -1)
        pr[i + 1][j] = -1;
      else
        pr[i + 1][j] = pr[i][pr[i][j]];
  for (i = 0; i < m; i++) {
    int u = i;
    for (k = n - 1, j = 0; k > 0; k >>= 1, j++) {
      if (k & 1) u = pr[j][u];
      if (u == -1) break;
    }
    maxp[0][i] = u;
  }
  for (i = 0; i < 19; i++)
    for (j = 0; j < m; j++) {
      k = j + (1 << i);
      if (k < m)
        maxp[i + 1][j] = max(maxp[i][j], maxp[i][k]);
      else
        maxp[i + 1][j] = maxp[i][j];
    }
  int l, r;
  while (q--) {
    scanf("%d%d", &l, &r);
    l--;
    r--;
    k = lg[r - l + 1];
    int maxi = max(maxp[k][l], maxp[k][r - (1 << k) + 1]);
    if (maxi >= l)
      printf("1");
    else
      printf("0");
  }
  return 0;
}
