#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int n, m, qnum, pre[maxn], a[maxn], ans[maxn], f[22][maxn], v[maxn], lc[maxn],
    ma, l[maxn], r[maxn];
vector<int> add[maxn], now[maxn];
int main() {
  scanf("%d%d%d", &n, &m, &qnum);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  pre[a[1]] = a[n];
  for (int i = 2; i <= n; i++) pre[a[i]] = a[i - 1];
  for (int i = 1; i <= m; i++) scanf("%d", &v[i]);
  for (int i = 1; i <= m; i++) {
    f[0][i] = lc[pre[v[i]]];
    lc[v[i]] = i;
  }
  for (int j = 1; j <= 19; j++)
    for (int i = 1; i <= m; i++) f[j][i] = f[j - 1][f[j - 1][i]];
  for (int i = 1; i <= m; i++) {
    int now = n - 1;
    int lc = i;
    for (int j = 19; j >= 0; j--)
      if ((now >> j) & 1) lc = f[j][lc];
    if (lc) add[i].push_back(lc);
  }
  for (int i = 1; i <= qnum; i++)
    scanf("%d%d", &l[i], &r[i]), now[r[i]].push_back(i);
  for (int i = 1; i <= m; i++) {
    for (auto j : add[i]) ma = max(ma, j);
    for (auto j : now[i]) ans[j] = (ma >= l[j]);
  }
  for (int i = 1; i <= qnum; i++) printf("%d", ans[i]);
  printf("\n");
  return 0;
}
