P3793 Yuno Saves Grandpa

Has everyone watched Calabash Brothers? Even if you haven't, let Yuno tell you.   Legend says the Minsk Aviation and Space Administration held two tanks in custody, strv103b and krv.   Mouse-ye accidentally broke the Minsk Aviation and Space Administration, and the two tanks escaped. From then on, other tanks lived in deep misery. The Minsk Aviation and Space Administration hurried to tell a bald man named SerB that only by releasing seven "YY" blueprinted tanks could they eliminate these two hull-down forces. SerB "YY"-ed seven tanks without even blueprints, but they were peeped by the Swedes on the BBS. Unable to destroy these seven "YY" tanks, they captured SerB and Mouse-ye. However, by then the seven tank models had already been built. They were T28 Prototype, T-100LT, Object 907, Grille 15, WZ-111, FV215b 183, and FV215b. To eliminate the hull-down forces and rescue SerB and Mouse-ye, they fought the hull-down forces one by one.  The T28 Prototype has very tough frontal armor as a TD, but armor is useless against premium shells and was directly head-shot to death by krv in hull-down.  The T-100LT is an excellent stealth scout, but without view range, it was perma-sniped to death by 103b.  Object 907 has an iron head, but got into a face-off with krv and was clipped to death.  The Grille 15 can snipe, but due to terrible traverse, it was circle-strafed to death by krv.  The WZ-111 has 300 mm pen, but 103b penned its side once and ammo-racked it.  The FV215b 183 has a 183 mm gun; 103b and krv trembled and dared not shoot her, so she rescued all the other tanks.  However, her brother FV215b, tempted by the Swedes, decided to defect (because the 183 has "OO" big), TKed the 183 with one shot, and the 183 caught fire and burned to death. As a result, all tanks were subdued by 103b and krv. The Swedes handed the seven tanks plus Mouse-ye to SerB, asking SerB to make the two strongest tanks to join the Swedish camp. SerB used all his wild ideas and made two tanks, E100WT and T-50-2.   krv and 103b burst into loud laughter upon seeing them. krv: E100WT, a 10 mm face; how can it not get smashed by HE? 103b: E100WT, lighthouse-like camouflage; how can it not get bush-sniped? krv: T-50-2, with that HP, I can one-shot it. 103b: T-50-2, let's see if you're more mobile or my sniping is more accurate. SerB: Baiyun, Jiaoshui, show them what you can do.

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.

You are given a random number generator: ```cpp namespace GenHelper { unsigned z1,z2,z3,z4,b; unsigned rand_() { b=((z113; z1=((z1&4294967294U)

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

| Test point ID | $n, m =$ | Time limit | |:-:|:-:|:-:| | $1 \sim 2$ | $1000$ | 1 s | | $3$ | $10^5$ | 1 s | | $4$ | $5\times10^5$ | 1 s | | $5$ | $10^6$ | 1 s | | $6$ | $10^7$ | 5 s | | $7$ | $1.2 \times 10^7$ | 5 s | | $8$ | $1.5 \times 10^7$ | 5 s | | $9$ | $2 \times 10^7$ | 5 s | Translated by ChatGPT 5