Sequence and Bitwise OR Operations

You are given a sequence \( a_1, a_2, \ldots, a_n \) of length \( n \). You need to perform \( m \) operations on the sequence. There are two kinds of operations:

1. Given two integers \( l, r \), answer the query: what is the maximum contiguous subarray sum in the subarray \( a_l, a_{l+1}, \ldots, a_r \)?
2. Given three integers \( l, r, k \), update every element \( a_i \) for \( l \le i \le r \) by replacing it with \( a_i \;|\; k \) (bitwise OR). For negative numbers, the bitwise OR is computed using 32-bit two's complement representation.

Note: The maximum contiguous subarray sum is defined over nonempty subarrays. For example, if all numbers are negative, the answer is the maximum element.

Constraints: \( 1 \le n, m \le 10^5 \); \( -2^{30} \le a_i, k < 2^{30} \); \( 1 \le l \le r \le n \).

All formulas must be rendered in \( \LaTeX \) format. HTML tags can be used for formatting the description.

inputFormat

The first line contains two integers \( n \) and \( m \), representing the length of the sequence and the number of operations, respectively.

The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \) representing the initial sequence.

The following \( m \) lines each describe an operation:

• If the line begins with 1, then it contains: 1 l r — a query asking for the maximum contiguous subarray sum in the interval \( [l, r] \).
• If the line begins with 2, then it contains: 2 l r k — an update that sets \( a_i = a_i \;|\; k \) for all \( i \) from \( l \) to \( r \).

outputFormat

For each query operation (type 1), output one line containing the maximum contiguous subarray sum for the specified interval.

sample

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

4
4