#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, m, q;
  cin >> n >> m >> q;
  vector<int> p(n), a(m);
  for (int i = (0); i < (n); ++i) cin >> p[i];
  for (int i = (0); i < (m); ++i) cin >> a[i];
  vector<vector<int> > idx(n + 1);
  for (int i = (0); i < (m); ++i) idx[a[i]].emplace_back(i);
  vector<vector<int> > nx(19, vector<int>(m));
  for (int i = (0); i < (n); ++i) {
    int src = p[i], dst = p[(i + 1) % n];
    for (int e : idx[src]) {
      nx[0][e] = lower_bound((idx[dst]).begin(), (idx[dst]).end(), e) -
                 idx[dst].begin();
      nx[0][e] = (nx[0][e] == idx[dst].size() ? m : idx[dst][nx[0][e]]);
    }
  }
  for (int i = (0); i < (18); ++i)
    for (int j = (0); j < (m); ++j) {
      nx[i + 1][j] = (nx[i][j] == m ? m : nx[i][nx[i][j]]);
    }
  vector<int> right(m);
  for (int i = (0); i < (m); ++i) {
    int pos = i;
    for (int j = (0); j < (19); ++j) {
      if (((n - 1) >> j & 1) && pos < m) pos = nx[j][pos];
    }
    right[i] = pos;
  }
  for (int i = m - 2; i >= 0; --i) right[i] = min(right[i], right[i + 1]);
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l;
    --r;
    cout << (right[l] <= r ? 1 : 0);
  }
  cout << '\n';
  return 0;
}
