409445: GYM103561 J Dinner Reservations for One

In the spirit of treating yourself for Satisfied Staying Single Day (February 11th), you decide to make a reservation at Uchi... for just yourself. However, you made the mistake of booking a seat at the Miami restaurant instead of at the Austin location! The fortunate opening of a straight (undersea) train route from Austin to Miami gives you the chance to still make it in time to your dinner. There are $$$N-1$$$ cities along this railway labeled with consecutive integers $$$2$$$ to $$$N$$$ in order of increasing distance from Austin; Austin is labeled as city $$$1$$$ and Miami is labeled as city $$$N+1$$$. The cities are connected by $$$N$$$ segments of railroad, with the $$$i$$$-th segment connecting cities $$$i$$$ and $$$i+1$$$. Every segment of the railroad has periodic maintenance every $$$a_i$$$ units of time.

In order to get from city $$$x$$$ to $$$y$$$ (where $$$x < y$$$, this railway is unidirectional towards Miami/city $$$N+1$$$), train drivers follow a set of rules based on $$$x$$$ and the current time $$$t$$$ until they arrive in city $$$y$$$.

• If $$$t \equiv 0\ (\mathrm{mod}\ a_x)$$$, then railway segment $$$x$$$ is undergoing maintenance and the train stays in city $$$x$$$ for $$$1$$$ unit of time ($$$x$$$ is unchanged and $$$t$$$ is incremented by $$$1$$$)
• If $$$t \not\equiv 0\ (\mathrm{mod}\ a_x)$$$, then railway segment $$$x$$$ is clear and the train moves to city $$$x+1$$$ in $$$1$$$ unit of time ($$$x$$$ is incremented by $$$1$$$ and $$$t$$$ is incremented by $$$1$$$)

To pass the time while traveling, you decide to compute the number of units of time it would take for the ride from city $$$x$$$ to city $$$y$$$ after starting at time $$$t$$$, and how it would hypothetically change if the maintenance frequencies were modified.

The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), representing the number of railway segments that connect the $$$N+1$$$ cities. The second line of input contains $$$N$$$ space separated integers $$$a_i$$$ ($$$2 \leq a_i \leq 5$$$), denoting the initial maintenance frequencies on segments $$$i$$$. The third line of input contains a single integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), representing the number of queries that will be made. The next $$$Q$$$ lines are either of the format "1 x y t" or "2 s b". For the latter type, hypothetical changes are made to the maintenance frequency of rail segment $$$s$$$ ($$$1 \leq s \leq N$$$) by setting $$$a_i = b$$$ ($$$2 \leq b \leq 5$$$). These changes are persisted for following queries. For the former type, you must output the number of units of time it would take for the ride from city $$$x$$$ to city $$$y$$$ ($$$1 \leq x < y \leq N+1$$$) after starting at time $$$t$$$ (calculations assume values of $$$a_i$$$ are either the initial ones given or the last $$$b$$$ value in queries of type $$$2$$$ where $$$i = s$$$). The initial $$$t$$$ is a nonnegative integer at most $$$10^5$$$ in every query.

For each query of the first type output a single integer - the hypothetical number of time units spent traveling by train from city $$$x$$$ to city $$$y$$$ assuming all queries are made in the order they are given.

8
2 5 3 2 3 5 3 4
10
2 8 3
1 2 6 0
1 1 3 0
2 3 4
1 3 9 0
1 4 6 0
1 5 6 0
2 7 3
1 7 8 0
1 2 5 0

5
3
9
3
2
2
4