题目描述

给一个长为 n 的序列 A₁,A₂,...,A_n，定义(i,j)（规定i<j）为好点对，当且仅当满足下列条件之一：

• i = j - 1
• 

现在有 m 组询问，每组询问给定一个区间，求这个区间内的好点对的个数。

给定一个 Type，当 Type=0 的时候不强制在线，否则强制在线。具体操作请看输入格式。

输入格式

输入第一行三个正整数 n,m,Type，分别表示序列长度，询问的个数，输入数据的种类。

输入第二行，共 n 个正整数。第 i 个数表示 A_i。

接下来 m 行，每行两个非负整数 l,r。当 Type = 0 的时候，询问区间就是 [l,r]，否则令：

u = (l + last - 1) mod n + 1 , v = (r + last - 1) mod n + 1，

那么当前询问区间就是 [min(u,v), max(u,v)]。其中 last 是上一次询问的答案，初始时 last = 0。

输出格式

输出共 m 行，每行一个非负整数，第 i 个数表示第 i 次询问的答案。

样例输入

3 2 0

2 1 2

1 1

1 3

样例输出

0

3

数据范围及约定