Star Brightness Operations

There are (2^n) stars in the sky, numbered from (0) to (2^n - 1). Each star (i) has an initial brightness value (a_i).

We define a Boolean operation (\otimes) for two positive integers (a) and (b) as follows: In the binary representation of (a), if every bit that is (1) is also (1) in (b) (after right-aligning and left-padding with zeros if necessary), then (a \otimes b) is (\texttt{True}); otherwise, it is (\texttt{False}).

There are two types of operations on the stars' brightness values:

1. Update Operation:
   The query is formatted as (1\ a\ b\ k). For every star with index (c) satisfying both (a \otimes c = \texttt{True}) and (c \otimes b = \texttt{True}), increase the brightness (a_c) by (k).
   
   
2. Query Operation:
   The query is formatted as (2\ a\ b). For every star with index (c) satisfying both (a \otimes c = \texttt{True}) and (c \otimes b = \texttt{True}), calculate the sum of their brightness values modulo (2^{32}) and output the answer.

inputFormat

The input begins with a line containing two integers, (n) and (Q), where (2^n) is the total number of stars and (Q) is the number of operations.

The next line contains (2^n) integers (a_0, a_1, \ldots, a_{2^n-1}) that represent the initial brightness values of the stars.

Each of the following (Q) lines represents a query, which can be in one of the following two formats:
• (1\ a\ b\ k) — Update Operation
• (2\ a\ b) — Query Operation

outputFormat

For each query of the second type (starting with (2)), output the calculated sum on a new line. The sum must be taken modulo (2^{32}).

sample

2 3
1 2 3 4
2 1 3
1 1 3 5
2 1 3

6
16