题目背景

大家看过葫芦娃吧？

没看过也没关系，让由乃告诉你吧

传说明斯克航空航天局里关着两个坦克，strv103b和krv。

鼠爷不小心打破了明斯克航空航天局，两个坦克逃了出来，从此其他坦克过上了水深火热的生活。

明斯克航空航天局急忙去告诉一个叫做serb的光头，只有YY出七辆图纸车，才能消灭这两个卖头势力。

serbYY出了七个连图纸都没有的车，却被瑞典人从bbs中窥见 。他们摧毁不了这七个YY车，

就把serb和鼠爷抓去。但是这时候七个坦克模型已经建出来了。

她们分别是 T28原型，T100lt，907工程，蟋蟀15，WZ111，FV215b183，FV215b

她们为了消灭卖头势力，救出serb和鼠爷，一个接一个去与卖头势力搏斗。

T28原是正面很硬的TD，但装甲在金币弹面前一点用都没有，直接被krv卖头打死。

T100lt是隐蔽超好的眼车，却因为没有视野，被103b活活黑死。

907工程是铁头，被krv顶牛直接抽包抽死。

蟋蟀15会黑枪，却因为辣鸡的转向被krv绕死。

WZ111有三百穿，被103b穿侧面一发爆了弹药架。

FV215b183有183炮，103b和krv瑟瑟发抖，不敢打她，于是她解救了其他所有坦克。

但是自己的兄弟FV215b因为瑞典人的诱惑，决定叛变（因为183OO大），TK了183一发，然后183着火烧死了，结果所有坦克都被103b和krv降服了。

瑞典人把七个坦克还有鼠爷一起给serb，让serb做出两辆最强坦克加入瑞典阵营。serb用尽了他所有的脑洞，做出了两辆车E100WT和T-50-2

krv和103b看到之后蛤蛤大笑

krv：E100WT，10mm的脸，不被HE糊死才怪

103b：E100WT，灯塔般的隐蔽，不被黑死才怪

krv：T-50-2，这血量，我一炮就可以打死

103b：T-50-2，看是你机动好还是我黑枪准

serb：百运，胶水，让她们看看你们的厉害

题目描述

故事还没讲完

krv骑坡卖头，却发现百运凭借优秀的精度炮炮打穿她的观察孔

krv慌了，跑去城市里面伸缩，被百运站桩撸死

strv103b跑去草后黑枪，看见胶水在肉侦，却发现自己根本打不中她，然后就被胶水点亮了，百运一梭子128的ARCR飞了过来

strv103b怂了，准备跑路了，但是还没等到自己切换回行走模式，胶水已经开始断她的腿了，被胶水断死

瑞典车们高呼不可战胜，从此不敢嚣张了

然后serb把百运和胶水加入了WOT

从此 其他坦克过上了更加水深火热的生活

然而你又不玩WOT，这事情不管你什么事啊

然而yql是大家的妹妹，所以这件事很重要：

yql在AK曼哈顿OI，CTSC，APIO之后，开始研究数学题。

由乃在挂了字符串OI，CTSC，APIO之后，开始研究大母神原型。

yql出了个数学题，由乃画出了一个表示大母神的图腾。

然后把这两个合成了一个题：

然而由于未知原因那个题挂掉了。。。

由乃想起来SCOI 2017 电子科技大学出了个卡常的rmq，然后发生了一件很有趣的事情

就是一位姓王的同学凭借奇奇怪怪的常数优化怒草了那个题，还比标程块了233倍

所以由乃也出了个卡常rmq，因为没题出了

输入格式

给你一个随机数生成器

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 )一下

然后n个数表示a[i]，这个直接调用read函数

然后m个询问，表示区间最大值，询问的区间是l = read() % n + 1 , r = read() % n + 1，注意有可能l > r

输出格式

输出一个unsigned long long 表示每次询问的答案的和

233 233 233

243704637294

提示

n,m=1000,1s
n,m=1000,1s
n,m=100000,1s
n,m=500000,1s
n,m=1000000,1s
n,m=10000000,5s
n,m=12000000,5s
n,m=15000000,5s
n,m=20000000,5s