Odd Sequence Operations

You are given a sequence (a_1,a_2,\dots,a_n) of odd integers. There are two types of operations to perform on the sequence:

1. Update Operation: Given three integers (l), (r), and (x), add the even number (x) to each element in the segment (a_l,a_{l+1},\dots,a_r). Since (x) is even and every (a_i) is odd, the updated values remain odd.

2. Query Operation: Given two integers (l) and (r), compute the product of the elements (a_l,a_{l+1},\dots,a_r) and output the result modulo (2^{20}) (i.e. modulo (1048576)).

You are to process (q) operations in order. For each query operation, print the answer on a new line.

The input format is described below.

inputFormat

The first line contains two integers (n) and (q) representing the number of elements in the sequence and the number of operations, respectively.\n\nThe second line contains (n) space-separated odd integers: (a_1,a_2,\dots,a_n).\n\nEach of the next (q) lines describes an operation. An operation is of one of the following two types:\n\n- For an update operation, the line starts with 1 followed by three integers (l), (r), and (x). Here, (x) is an even number.\n- For a query operation, the line starts with 2 followed by two integers (l) and (r).

outputFormat

For each query operation, output the required product modulo (1048576) on a separate line.

sample

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

945
2835
7