409677: GYM103677 N Freaky Fertilizer Tests

Farmers all around the world have been freaking out over an all new brand of fertilizer, which claims to exponentially grow your grapes!

According to the advertisements, applying a fertilizer with growth factor $$$f$$$ to a grapevine causes it to immediately grow $$$f$$$ grapes, and wither directly afterwards.

You aren't very convinced that the fertilizer works that well, but the only thing you hate more than false advertising is manual labor. Clearly, the only sensible thing to do is to test the fertilizer by using your programmable army of robot farmers to apply the fertilizer, harvest the grapes, and replant them over and over.

You have sectioned off $$$n$$$ fields for the tests you plan on running, with the $$$i$$$th field initially having $$$x_i$$$ grapevines.

To test the fertilizers, you have settled on the following procedure:

1. For every field $$$i$$$ where $$$l \leq i \leq r$$$, the robots apply a fertilizer with growth factor $$$f$$$ to every grapevine.
2. The robots harvest the grapes and replant all of them, so that each grape sprouts into a new grapevine.
3. The robots manually plant $$$g$$$ extra grapes, to make sure that there is always something growing in the field (in case the fertilizer didn't work).
4. For consistency, steps 1 through 3 are repeated $$$t$$$ times.

However, all of this testing would be pointless without some kind of data measurement, so you'll also sometimes have the robots to count the number of grapevines currently growing in a specific field.

These tests will take quite a while to run, but it's gotten you thinking: if all the fertilizers work exactly as advertised, what would the measurements look like?

The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 2 \cdot 10^5$$$), representing the number of fields and robot tasks, respectively.

The next line contains $$$n$$$ integers. The $$$i$$$th integer is $$$0 \leq x_i \leq 10^8$$$, the number of grapevines in field $$$i$$$ initially.

Then, $$$q$$$ lines follow, which will be in one of the two formats:

• $$$1$$$ $$$l$$$ $$$r$$$ $$$f$$$ $$$g$$$ $$$t$$$: Apply the fertilizer test (described above) $$$t$$$ times ($$$0 \leq t \leq 10^8$$$) to the fields between $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$), inclusive. The fertilizer used has growth factor $$$f$$$, and $$$g$$$ grapes are added manually to each harvest ($$$0 \leq f, g \leq 10^8$$$).
• $$$2$$$ $$$i$$$: Command the robots to count the number of grapevines that are growing in field $$$i$$$ ($$$1 \leq i \leq n$$$), and report the number back to you mod $$$998244353$$$.

For every query of the second type, output the number of grapevines growing in field $$$i$$$ mod $$$998244353$$$.

5 7
1 2 3 4 5
1 1 3 2 1 1
2 1
2 5
1 2 4 1 1 5
2 2
2 3
2 4

3
5
10
12
9