#include <bits/stdc++.h>
using namespace std;
class RMQ {
 private:
  vector<vector<int>> dp;

 public:
  RMQ(vector<int>& v) {
    int n = v.size() - 1;
    dp.assign(log2(n) + 1, vector<int>(n + 1));
    dp[0] = v;
    for (int i = n; i >= 1; i--)
      for (int j = 1; i + (1 << j) - 1 <= n; j++)
        dp[j][i] = max(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
  }
  int query(int lo, int hi) {
    int k = log2(hi - lo + 1);
    return max(dp[k][lo], dp[k][hi - (1 << k) + 1]);
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int k, n, q;
  cin >> k >> n >> q;
  vector<int> perm(k + 1);
  for (int i = 1; i <= k; i++) {
    int x;
    cin >> x;
    perm[x] = i;
  }
  vector<vector<int>> dp(19, vector<int>(n + 1));
  vector<int> arr(n + 1), last(k + 1), lastEnd(n + 1);
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    arr[i] = perm[x];
    dp[0][i] = last[arr[i] - 1];
    lastEnd[i] = last[k];
    last[arr[i]] = i;
  }
  for (int j = 1; (1 << j) <= n; j++)
    for (int i = 1; i <= n; i++) dp[j][i] = dp[j - 1][dp[j - 1][i]];
  auto query = [&](int pos, int qry) {
    int anc = pos;
    for (int i = 18; i >= 0; i--)
      if (qry & (1 << i)) anc = dp[i][anc];
    return anc;
  };
  vector<int> ans(n + 1);
  for (int i = 1; i <= n; i++) {
    int pos = query(i, arr[i] - 1);
    if (arr[i] == k)
      ans[i] = pos;
    else
      ans[i] = query(lastEnd[pos], k - arr[i] - 1);
  }
  RMQ rmq(ans);
  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    cout << (rmq.query(x, y) >= x);
  }
  cout << '\n';
  return 0;
}
