题目描述

你获得了一个长度为 $n$ 的整数序列 $a$，这个序列是通过一个特定的伪随机数生成器构造的，你需要按照给定的种子 $s$ 初始化生成器，然后依次调用 $read()$ 函数得到每个元素的值。之后，有 $m$ 次询问，每次询问给出一个区间 $[l,r]$（注意：$l$ 和 $r$ 也是由随机数生成的，并且可能 $l>r$），请你求出该区间内的最大值。 伪随机数生成器如下：

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{
  using namespace GenHelper;
  z1=x; 
  z2=(~x)^0x233333333U;
  z3=x^0x1234598766U; 
  z4=(~x)+51;
}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

输入格式

第一行包含三个整数 $n$,$m$,$s$，分别表示序列长度、询问次数以及随机种子。 接下来，你需要使用提供的 $srand(s)$初始化随机生成器，然后连续调用 $read()$ 共 $n$ 次，得到序列的每个元素 $a_i$。 接着，对于每一次询问： 调用一次 $read()$得到一个整数 $L$，令 $l$=$L$ $mod$ $n$ $+$ $1$； 再调用一次 $read()$得到一个整数 $R$，令 $r$=$R$ $mod$ $n$ $+$ $1$；

输出格式

输出一个整数，表示每次询问的答案的和。

样例

233 233 233

243704637294

数据范围