시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 2048 MB63350.000%

문제

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.

예제 입력 1

10 10
969575 741825 24903 1047319 450475 256145 1045323 479255 810659 768323
1 5 6 3034
2 1 10
2 1 9
2 1 4
1 3 6 126904
2 5 5
2 9 9
1 7 7 853094
1 4 9 1025178
2 5 8

예제 출력 1

1045541
1012343
558151
580413
810659
527353