33422번 - Generating the Sequence 다국어

문제

There is a sequence $a_1, a_2, \ldots, a_n$ of length $n,ドル and it is guaranteed that each $a_i$ is an odd number.

There are two types of operations:

1. Given $\ell,ドル $r,ドル and $x,ドル add an even number $x$ to each of the elements $a_{\ell}, a_{\ell + 1}, \ldots, a_{r}$.
2. Given $\ell$ and $r,ドル find the product of $a_{\ell}, a_{\ell + 1}, \ldots, a_{r},ドル and output the answer modulo 2ドル^{20}$.

Given the initial sequence and the operations, perform them efficiently.

입력

The first line of the input contains two positive integers $n$ and $q$ (1ドル \leq n, q \leq 2 \cdot 10^5$) representing the length of the sequence and the number of queries.

The second line contains $n$ odd numbers $a_1, a_2, \ldots, a_n$ (1ドル \leq a_i < 2^{20}$).

The following $q$ lines represent queries, each in one of the following two formats:

• "1 $\ell$ $r$ $x$ ": perform the first type of operation (1ドル \leq \ell \leq r \leq n,ドル the value $x$ is even and 0ドル \leq x < 2^{20}$).
• "2 $\ell$ $r$": perform the second type of operation (1ドル \leq \ell \leq r \leq n$).

All the values in the queries are integers.

출력

For each query of type 2, output one line with an integer representing the answer.

제한

힌트