#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*4]; // (r, index)
pi lazy[MAXN*4]; // (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);
}
int lev[MAXN];
int L[MAXN], R[MAXN]; // smallest level greater then itself among k-1 left/right elements
int Ldst[MAXN], Rdst[MAXN];
bool vst[MAXN];
set<pi> ks;
void dfs1(int here) {
vst[here] = 1;
if(R[here]==0) {
Rdst[here] = 0;
return;
}
int there = (here + R[here])%n;
if(!vst[there]) dfs1(there);
Rdst[here] = R[here] + Rdst[there];
} void dfs2(int here) {
vst[here] = 1;
if(L[here]==0) {
Ldst[here] = 0;
return;
}
int there = (here + n-L[here])%n;
if(!vst[there]) dfs2(there);
Ldst[here] = L[here] + Ldst[there];
};
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});
}
vector<int> tmp={}; cnt++;
for(int x:rs) tmp.push_back(x);
for(int x:tmp) {
rem--;
rmv(x); lev[x] = cnt;
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});
}
}
}
// construct jump table
for(int j=1;j<k;j++) ks.insert({lev[j],j});
{
auto it = ks.lower_bound({lev[0],0});
if(it == ks.end()) R[0] = 0;
else R[0] = it->ss;
} for(int i=1;i<n;i++) {
ks.erase({lev[i],i});
ks.insert({lev[(i+k-1)%n], (i+k-1)%n});
auto it = ks.lower_bound({lev[i],0});
if(it == ks.end()) R[i] = 0;
else R[i] = (it->ss-i+n)%n;
}
ks.clear();
for(int j=n-2;j>=n-k;j--) ks.insert({lev[j],j});
{
auto it = ks.lower_bound({lev[n-1],0});
if(it == ks.end()) L[n-1] = 0;
else L[n-1] = (n-1 - it->ss)%n;
} for(int j=n-2;j>=0;j--) {
ks.erase({lev[j],j});
ks.insert({lev[(j-k+1+n)%n], (j-k+1+n)%n});
auto it = ks.lower_bound({lev[j],0});
if(it == ks.end()) L[j] = 0;
else L[j] = (j - it->ss + n)%n;
}
for(int i=0;i<n;i++) vst[i]=0;
for(int i=0;i<n;i++) if(!vst[i]) dfs1(i);
for(int i=0;i<n;i++) vst[i]=0;
for(int i=0;i<n;i++) if(!vst[i]) dfs2(i);
}
bool check(int x, int y) { // is there a path from x to y?
if(Rdst[x] >= (y-x+n)%n) return 1;
if(Ldst[x] >= (x-y+n)%n) 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;
//if(!check(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
