#include <bits/stdc++.h>
using namespace std;
mt19937 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
const long double PI = 3.141592653589793;
const long long INF = 1e6;
const long long mod = 1e9 + 7;
void solve() {
  int n, m, q;
  cin >> n >> m >> q;
  int pos[n + 1];
  int bks[n];
  int ar[m];
  for (int i = 0; i < n; ++i) {
    cin >> bks[i];
    pos[bks[i]] = i;
  }
  for (int i = 0; i < m; ++i) {
    cin >> ar[i];
  }
  int go = ceil(log2(n));
  int up[m][go + 1];
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j <= go; ++j) {
      up[i][j] = -INF;
    }
  }
  int prev[n + 1];
  for (int i = 0; i <= n; ++i) prev[i] = -INF;
  for (int i = 0; i < m; ++i) {
    up[i][0] = prev[bks[(pos[ar[i]] - 1 + n) % n]];
    for (int j = 1; j <= go; ++j) {
      if (up[i][j - 1] != -INF) {
        up[i][j] = up[up[i][j - 1]][j - 1];
      } else
        up[i][j] = -INF;
    }
    prev[ar[i]] = i;
  }
  int ans[m];
  for (int i = 0; i < m; ++i) {
    int cur = i;
    for (int j = 32; j >= 0; --j) {
      if (((1ll << j) & (n - 1)) != 0) {
        cur = up[cur][j];
        if (cur == -INF) break;
      }
    }
    ans[i] = cur;
  }
  for (int i = 1; i < m; ++i) {
    ans[i] = max(ans[i], ans[i - 1]);
  }
  for (int i = 0; i < q; ++i) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    if (ans[b] >= a)
      cout << 1;
    else
      cout << 0;
  }
  cout << '\n';
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  solve();
  return 0;
}
