Description

The story isn't over yet.

krv went hull-down on a slope, only to find Baiyun (pinyin) penetrating her cupola shot after shot thanks to great accuracy.

krv panicked, ran into the city to peek-a-boo, and got mowed down by Baiyun trading shots stationary.

strv103b went to bush-camp, saw Jiaoshui (pinyin) doing active scouting, but found she simply couldn't hit her; then Jiaoshui lit her up, and Baiyun sent over a burst of 128 ARCR.

strv103b chickened out and tried to run, but before switching back to travel mode, Jiaoshui had already started tracking her, and she got permatracked to death by Jiaoshui.

The Swedish tanks shouted that they were invincible, and from then on did not dare to be arrogant.

Then SerB added Baiyun and Jiaoshui to WOT.

From then on, other tanks lived an even more miserable life.

But you don't play WOT—what does this have to do with you?

However, yql is everyone's little sister, so this is important:

After AK (full score) in Manhattan OI, CTSC, and APIO, yql started studying math problems.

After failing string problems in OI, CTSC, and APIO, Yuno started researching the "Great Mother Goddess" prototype.

yql made a math problem, and Yuno drew a totem representing the Great Mother Goddess.

Then they combined these into one problem:

But for unknown reasons that problem failed...

Yuno remembered that in SCOI 2017 University of Electronic Science and Technology of China put out a constant-factor-tuned RMQ, and something interesting happened:

A student surnamed Wang, relying on strange constant optimizations, demolished that problem and was 233 times faster than the official solution.

So Yuno also made a constant-factor-tuned RMQ, because there were no problems left to make.

Input Format

You are given a random number generator:

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;
}

Read three numbers $n, m, s$.

You need to call srand(s).

Then there are $n$ numbers representing $a_i$, generated by directly calling the read function.

Then there are $m$ queries asking for the range maximum. The query interval is $l = \text{read()} \bmod n + 1 , r = \text{read()} \bmod n + 1$. Note that it is possible that $l > r$.

Output Format

Output a single unsigned long long representing the sum of the answers to all queries.

233 233 233

243704637294

Hint

Translated by ChatGPT 5