You are given a sequence $a_1, a_2, \dots, a_n$ of length $n$, where it is guaranteed that each $a_i$ is odd.

There are two types of operations:

1. Given $l, r, x$, add an even number $x$ to $a_l, a_{l+1}, \dots, a_r$.
2. Given $l, r$, find the product of $a_l, a_{l+1}, \dots, a_r$, modulo $2^{20}$.

Input

The input is read from standard input.

The first line contains two positive integers $n$ and $q$, representing the length of the sequence and the number of queries, respectively. It is guaranteed that $1 \le n, q \le 2 \times 10^5$.

The second line contains $n$ odd integers $a_1, a_2, \dots, a_n$. It is guaranteed that $1 \le a_i < 2^{20}$.

The next $q$ lines each describe an operation, in one of the following formats:

• $1 ~ l ~ r ~ x$: Perform the first operation. It is guaranteed that $1 \le l \le r \le n$ and $0 \le x < 2^{20}$.
• $2 ~ l ~ r$: Perform the second operation. It is guaranteed that $1 \le l \le r \le n$.

Output

The output is written to standard output.

For each operation of type $2$, output a single integer representing the answer on a new line.

Examples

Input 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

Output 1

1045541
1012343
558151
580413
810659
527353