//失踪人口回归系列

# 2. 题解

#include <bits/stdc++.h>

#define NS (300005)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, m, tp, A[NS], root[NS], sz;

struct N {int d, l, r;} e[NS * 40];

void Add(int p, int L, int R, int& x, int y)
{
x = ++sz, e[x] = e[y], e[x].d++;
if (L == R) return;
int Mid = (L + R) >> 1;
if (p <= Mid) Add(p, L, Mid, e[x].l, e[y].l);
else Add(p, Mid + 1, R, e[x].r, e[y].r);
}

int Query(int l, int r, int L, int R, int a)
{
if (!a) return 0;
if (l <= L && R <= r) return e[a].d;
int Mid = (L + R) >> 1, res = 0;
if (l <= Mid) res = Query(l, r, L, Mid, e[a].l);
if (r > Mid) res += Query(l, r, Mid + 1, R, e[a].r);
return res;
}

PII st[NS];

vector<int> g[NS];

void Init()
{
int top = 0;
for (int i = 1; i <= n; i += 1)
{
bool flag = 0;
while (top && st[top].FIR <= A[i])
{
g[st[top].SEC].push_back(i);
if (st[top].FIR == A[i]) flag = 1;
top--;
}
if (!flag && top) g[st[top].SEC].push_back(i);
st[++top].FIR = A[i], st[top].SEC = i;
}
for (int i = 1; i <= n; i += 1)
{
root[i] = root[i - 1];
for (int j = 0; j < g[i].size(); j += 1)
}
}

int main(int argc, char const* argv[])
{
IN(n), IN(m), IN(tp);
for (int i = 1; i <= n; i += 1) IN(A[i]);
Init();
for (int i = 1, l, r, ans = 0; i <= m; i += 1)
{
IN(l), IN(r);
if (tp) l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1;
if (l > r) swap(l, r);
ans = Query(l, r, 1, n, root[r]) - Query(l, r, 1, n, root[l - 1]);
printf("%d\n", ans);
}
return 0;
}