#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
const int INF = 0x3f3f3f3f;
int a[N], b[N], to[N];
int dp[N][20], mi[N];
vector<int> q[N];
int n, m, Q;
void ST() {
  memset(dp, INF, sizeof(dp));
  for (int i = 1; i <= m; i++) {
    q[to[b[i]]].push_back(i);
    for (auto v : q[b[i]]) {
      dp[v][0] = i;
    }
    q[b[i]].clear();
  }
  for (int j = 1; j <= 20; j++)
    for (int i = 1; i + (1 << j) - 1 <= m; i++) {
      if (dp[i][j - 1] == INF) continue;
      dp[i][j] = dp[dp[i][j - 1]][j - 1];
    }
  mi[m + 1] = INF;
  for (int i = m; i >= 1; i--) {
    int k = i;
    for (int j = 0; j < 20; j++) {
      if ((n - 1) & (1 << j)) k = dp[k][j];
      if (k == INF) break;
    }
    mi[i] = min(mi[i + 1], k);
  }
}
int Query(int l, int r) { return mi[l] <= r ? 1 : 0; }
int re[N];
int main() {
  scanf("%d %d %d", &n, &m, &Q);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i < n; i++) {
    to[a[i]] = a[i + 1];
  }
  to[a[n]] = a[1];
  for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
  ST();
  for (int i = 1; i <= Q; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    re[i] = Query(l, r);
  }
  for (int i = 1; i <= Q; i++) printf("%d", re[i]);
  return 0;
}
