P16030 [CSPro 23] Hakone Mountains: The Hardest in the World.

The testdata on Luogu is only for community exchange and is not official testdata. Official judging link: . “Do you know what the best compliment is for a long-distance runner?” “Is it ‘fast’?” “No, it’s ‘strong’,” Kiyose said. “Just being fast is not enough to stand out in long-distance running. Weather, the course, how the race develops, physical condition, and your own mental state—long-distance runners must calmly analyze all these factors. Even when facing huge difficulties, they must endure and push through. What long-distance runners need is real ‘strength’. So we must treat ‘strength’ as the highest honor and keep running every day.” Whether it was Aoi or the other housemates, everyone listened to Kiyose with full attention. “Seeing how you’ve done these past three months, I believe more and more that I didn’t choose the wrong person,” Kiyose continued. “You’re talented, and you have great potential. So, Aoi, you must believe in yourself more, and don’t rush to become amazing overnight. Getting stronger takes time, and you could also say it never has an endpoint. Long-distance running is a competition worth dedicating a lifetime to. Some people, even when they’re old, still don’t give up jogging or marathons.” — Shion Miura, *The Wind Rises Strongly* (pinyin: Qiang Feng Chui Fu). The Hakone Ekiden (official name: Tokyo-Hakone Round-Trip Intercollegiate Ekiden Race) is a Japanese relay road race held every year on January 2-3, hosted by the Kanto Intercollegiate Athletic Association. Every university in the Kanto region has a chance to participate. In Japan, the Hakone Ekiden is a must-watch during the New Year holiday, and many families watch the intense race while eating ozoni. This year, Kyoto University also wants to send a long-distance team to the Hakone Ekiden. The long-distance coach of the track and field club organized a group of reserve athletes and started strict training.

Kyoto University’s training lasts for a total of $m$ days. During training, the roster of official team members may change. For simplicity, we agree that at and only at the end of day $t \ (1 \leq t \leq m)$, exactly one of the following three events happens: 1. Either a student’s $10\text{km}$ speed reaches the official-member requirement, and the coach adds them as the last member of the official roster, with strength $x$; or the official member ranked last in speed is eliminated from the official roster due to being too slow. - During training, we assume the relative speed ranking of athletes never changes, and it is unrelated to strength. - The strict coach sets a harsh rule: an eliminated student will still train with everyone, but cannot rejoin this year’s official roster for the Hakone Ekiden. 2. Due to recent training, at the end of day $s$, the strengths of athletes whose speed ranks are from $l$ to $r$ change to $y$ times their previous values. 3. Late at night, the coach wants to know the effect of recent training, so he computes the sum of the current (i.e., at the end of day $t$) strengths of athletes whose speed ranks are from $l$ to $r$ in the roster at the end of day $s$. Since the result may be large, we only consider its value modulo $p$. To protect students’ privacy, the event log may be encrypted.

Read input from standard input. The first line contains three integers $m, p$ and $T$, separated by spaces. If $T = 0$, then in event 1, $x = x'$, and in event 2, $y = y'$. If $T = 1$, the event log is encrypted: in event 1, $x = x' \oplus A$, and in event 2, $y = y' \oplus A$, where $\oplus$ is the bitwise XOR operation, and $A$ is the result computed by the most recent event 3. If no event 3 has occurred before, then $A = 0$. The next $m$ lines describe the events. Line $t$ describes the event that happens at the end of day $t$: - `1; x'`: event 1 happens. If $x > 0$, a student with strength $x$ is added as the last member of the official roster; if $x = 0$, the last-ranked official member is eliminated from the roster. It is guaranteed that $0 \leq x' < 2^{30}$. - `2; s; l; r; y'`: event 2 happens. It is guaranteed that $1 \leq s \leq t$, $1 \leq l \leq r \leq n$, $0 \leq y' < 2^{30}$, where $n$ is the number of official members at the end of day $s$. - `3; s; l; r`: event 3 happens. It is guaranteed that $1 \leq s \leq t$, $1 \leq l \leq r \leq n$, where $n$ is the number of official members at the end of day $s$.

Write output to standard output. For each event 3, output one line containing one integer: the computed result.

### Sample 1 Explanation At the end of day $1$, a student with strength $7$ is listed as an official member; let us call him Oz. The official roster is: Oz. At the end of day $2$, a student with strength $3$ is listed as an official member; let us call him Jonosaki. The official roster is: Oz, Jonosaki. At the end of day $3$, Jonosaki is eliminated. The official roster is: Oz. At the end of day $4$, a student with strength $4$ is listed as an official member; let us call him Higuchi Seitaro. The official roster is: Oz, Higuchi Seitaro. At the end of day $5$, due to recent training, in the roster at the end of day $4$, the strengths of the $1$st to $2$nd members—namely Oz and Higuchi Seitaro—are multiplied by $2$. Therefore, Oz’s strength becomes $14$, and Higuchi Seitaro’s strength becomes $8$. At the end of day $6$, the coach computes the current strengths of the $1$st to $2$nd members in the roster at the end of day $2$—namely Oz and Jonosaki. Oz’s strength is $14$, Jonosaki’s strength is $3$, so the sum is $17$, and its value modulo $p$ is $7$. At the end of day $7$, due to recent training, in the roster at the end of day $1$, the strength of the $1$st member—namely Oz—is multiplied by $3$. Therefore, Oz’s strength becomes $42$. At the end of day $8$, the coach computes the current strengths of the $1$st to $2$nd members in the roster at the end of day $6$—namely Oz and Higuchi Seitaro. Oz’s strength is $42$, Higuchi Seitaro’s strength is $8$, so the sum is $50$, and its value modulo $p$ is $0$. ### Subtasks $1 \leq m \leq 3 \times 10^5$, $2 \leq p < 2^{30}$, $T \in {0, 1}$ |Test point|Special property|$T$| |:-:|:-:|:-:| |$1$|$m \leq 5000$|$1$| |$2$|In event 1, $x > 0$|^| |$3$|No event 2|^| |$4$|In event 1, $x$ is chosen randomly from ${0, 1}$|$0$| |$5$|$r - l \leq 10$|^| |$6$|^|$1$| |$7, 8$|None|$0$| |$9, 10$|^|$1$| Each test point is worth $10$ points. Translated by ChatGPT 5