#ifndef LOCAL
#include "plants.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
#define sz(v) ((int)(v).size())
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 100100*2;
const ll MOD = 1e9+7;
const ll INF = 2e9;
struct SegTree {
pi tree[MAXN]; // (r, index)
pi lazy[MAXN]; // (0, diff), (1, set)
void init(int node, int s, int e, vector<int>& r) {
if(s==e) {
tree[node] = {r[s], s};
return;
}
int mid=s+e>>1;
init(node<<1,s,mid,r); init(node<<1|1,mid+1,e,r);
tree[node] = min(tree[node<<1], tree[node<<1|1]);
}
void cal(pi &x, pi a) {
if(a.ff == 1) x = a;
else if(!(x==pi(1,MAXN))) x.ss += a.ss;
}
void prop(int node, int s, int e) {
if(lazy[node].ff == 0) { if(tree[node].ff^MAXN) tree[node].ff += lazy[node].ss;}
else tree[node].ff = lazy[node].ss;
if(s!=e) {
for(int x:{node<<1, node<<1|1})
cal(lazy[x], lazy[node]);
} lazy[node] = {0,0};
}
void update(int node, int s, int e, int l, int r, pi val) {
prop(node, s, e);
if(e<l || r<s) return;
if(l<=s && e<=r) {
cal(lazy[node], val);
prop(node, s, e); return;
}
int mid=s+e>>1;
update(node<<1,s,mid,l,r,val); update(node<<1|1,mid+1,e,l,r,val);
tree[node] = min(tree[node<<1], tree[node<<1|1]);
}
pi solve(int node, int s, int e) {
prop(node, s, e); return tree[1];
}
pi f(int node, int s, int e, int l, int r) {
prop(node,s,e);
if(e<l || r<s) return {MAXN,MAXN};
if(l<=s && e<=r) return tree[node];
int mid=s+e>>1;
return min(f(node<<1,s,mid,l,r), f(node<<1|1,mid+1,e,l,r));
}
} seg;
int K, n;
set<int> s, rs;
void f(int a, int b) {
int d = (b+n-a)%n; if(d==0) d=n;
if(d >= K) {
if(rs.find(b) == rs.end()) rs.insert(b);
else rs.erase(b);
}
}
void ins(int x) {
if(s.empty()) {
s.insert(x);
rs.insert(x);
return;
}
auto itr = s.lower_bound(x);
if(itr == s.end()) itr = s.begin();
auto itl = s.lower_bound(x);
if(itl == s.begin()) itl = prev(s.end());
else itl = prev(itl);
f(*itl, *itr); f(*itl, x); f(x, *itr);
s.insert(x);
} void rmv(int x) {
if(sz(s) == 1) {
s.erase(x);
rs.erase(x);
return;
}
auto it = s.find(x);
auto itr = (next(it)==s.end() ? s.begin() : next(it));
auto itl = (it==s.begin() ? prev(s.end()) : prev(it));
f(*itl, *it); f(*it, *itr); f(*itl, *itr);
s.erase(it);
}
vector<int> adj[MAXN];
int lev[MAXN];
void init(int k, std::vector<int> r) {
n = r.size(); int cnt=0; K = k;
// init seg -> r
// each loop, pick min (r, index) -> if r=0, store in a set and delete from segtree
// make another set, managing elements whose left k-1 elements are not in the origin set
// assign new level to the managing set, delete from the set / update segtree
seg.init(1,0,n-1,r);
int rem=n;
while(rem) {
while(1) {
auto [a,x] = seg.solve(1,0,n-1);
if(a>0) break;
ins(x);
seg.update(1,0,n-1,x,x,{1,MAXN});//cout<<'a'<<x<<endl;cout.flush();
} //for(int x:s) cout<<x<<bl;cout<<endl;
//for(int x:rs) cout<<x<<bl;cout<<endl;
vector<int> tmp={}; cnt++;
for(int x:rs) tmp.push_back(x);
for(int x:tmp) {
rem--;
rmv(x); lev[x] = cnt; //cout<<'b'<<x<<bl<<cnt<<endl;cout.flush();
if(x-k+1 >= 0) seg.update(1,0,n-1,x-k+1,x-1,{0,-1});
else {
seg.update(1,0,n-1,0,x-1,{0,-1});
seg.update(1,0,n-1,x-k+1+n,n-1,{0,-1});
}
}
}
for(int i=0;i<n;i++) {//cout<<lev[i]<<bl;
for(int j=(i+1)%n,t=1;t<k;t++,j=(j+1)%n) {
if(lev[i] < lev[j]) adj[i].push_back(j);
else if(lev[i]>lev[j]) adj[j].push_back(i);
}
}//cout<<endl;
}
bool vst[MAXN];
bool dfs(int x, int y) {
vst[x]=1;
if(x==y) return 1;
for(int nx:adj[x]) {
if(vst[nx]) continue;
if(dfs(nx,y)) return 1;
} return 0;
}
int compare_plants(int x, int y) {
if(lev[x] == lev[y]) return 0;
int res=1;
if(lev[x] > lev[y]) swap(x,y),res=-1;
for(int i=0;i<n;i++) vst[i]=0;
if(!dfs(x,y)) res=0;
return res;
}
#ifdef LOCAL
// grader
static int N, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
assert(scanf("%d%d%d", &N, &k, &q) == 3);
r.resize(N);
answer.resize(q);
for (int i = 0; i < N; i++) {
int value;
assert(scanf("%d", &value) == 1);
r[i] = value;
}
x.resize(q);
y.resize(q);
for (int i = 0; i < q; i++) {
assert(scanf("%d%d", &x[i], &y[i]) == 2);
}
fclose(stdin);
init(k, r);
for (int i = 0; i < q; i++) {
answer[i] = compare_plants(x[i], y[i]);
}
for (int i = 0; i < q; i++) {
printf("%d\n", answer[i]);
}
fclose(stdout);
return 0;
}
#endif
