Joãozão and Eric, two renowned screenwriters, are working together on the movie Godfather. When they reached the stage of creating the climax of the story, they realized they needed a truly insane scene to surprise the audience.
Joãozão wants to make the scene as crazy as possible, trying to maximize the madness level of the story. On the other hand, Eric wants to maintain balance and prevent exaggeration, trying to minimize this level. Thus, the film's director — Bras — decided to use their differing ideas to reach a point of creative balance.
The creative process takes place over $$$N$$$ days. Bras uses a binary string $$$S$$$ to assist him. On the $$$i$$$-th day, Bras chooses who between Joãozão and Eric will make the change to the plot according to this string:
To start the process, Bras chose two plot twists: a main plot with madness level $$$A$$$, and an auxiliary plot with madness level $$$B$$$.
Whoever is chosen to make the change on day $$$i$$$ will begin the day with two values $$$X$$$ and $$$Y$$$, the current madness levels of the main and auxiliary plots, respectively. Then, this person creates a new main plot with value $$$X + Y$$$, and selects one of $$$X$$$ or $$$Y$$$ to continue as the auxiliary plot's value. Note that there is always exactly one main plot and one auxiliary plot.
Bras is still unsure how to choose who changes the plot on each day, so he wants to simulate possible scenarios. Given the initial $$$S$$$, he will perform $$$Q$$$ operations, each of which inverts the choices on the days in an interval $$$[L, R]$$$. That is, for all $$$i$$$ such that $$$L \le i \le R$$$, the value of $$$S_i$$$ is flipped: if it was $$$0$$$, it becomes $$$1$$$; if it was $$$1$$$, it becomes $$$0$$$.
Your task is to perform this simulation; after each of the $$$Q$$$ changes, determine what the final madness level of the main plot will be, knowing that Joãozão wants to maximize the final madness and Eric wants to minimize it. Since the madness level can be very large, Bras will be satisfied knowing just the result modulo $$$998244353$$$.
The first line of the input contains three integers $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$, $$$A$$$, and $$$B$$$ $$$(1 \le A, B \lt 10^6)$$$ — the number of days to develop the plot, and the initial madness levels of the main and auxiliary plots, respectively.
The second line of the input contains the binary string $$$S$$$ of length $$$N$$$, which Bras uses to determine who will make the change on each day.
The third line contains an integer $$$Q$$$ $$$(1 \le Q \le 2 \cdot 10^5)$$$, the number of changes Bras will request.
The next $$$Q$$$ lines each contain two integers $$$L$$$ and $$$R$$$ $$$(1 \le L \le R \le N)$$$, meaning that for every $$$i$$$ such that $$$L \le i \le R$$$, if Joãozão was previously making the change on day $$$i$$$, now Eric will do it, and vice versa.
The output must contain $$$Q$$$ lines; the $$$i$$$-th line must contain the madness level of the main plot twist after the first $$$i$$$ updates, modulo $$$998244353$$$.
8 4 51110101181 81 64 74 61 82 68 85 7
131 162 226 213 131 153 153 170
1 8 2151 11 11 11 11 1
10 10 10 10 10
6 3 1911111131 52 54 5
37 191 122
| UDESC Selection Contest 2025-1 |
|---|
| Finished |
