由乃救爷爷

大家看过葫芦娃吧？ 没看过也没关系，让由乃告诉你吧   传说明斯克航空航天局里关着两个坦克，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，因为没题出了

给你一个随机数生成器 ```cpp 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

```cpp 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 ```