Description

You are given a sequence $a$ of length $n$. You need to perform $m$ operations on it. There are two types of operations:

1. Given two integers $l, r$, query the maximum subarray sum in the range from $l$ to $r$.
2. Given three integers $l, r, k$, bitwise OR every $a_i$ in the range from $l$ to $r$ with $k$.

For all testdata, $n, m \leq 10^5$, $-2^{30} \leq a_i, k < 2^{30}$, and $1 \leq l \leq r \leq n$.

Note: For negative numbers, the bitwise OR is computed using 32-bit two's complement.

Input Format

The input consists of $m + 2$ lines.

The first line contains two positive integers $n, m$.

The second line contains $n$ integers $a_1 \ldots a_n$.

The next $m$ lines each start with one positive integer $op$. If $op = 1$, then two integers $l, r$ follow, representing a query. Otherwise, three integers $l, r, k$ follow, representing an update.

Output Format

Output several lines. Each line contains one integer, which is the answer to a query.

15 15
512 -65 33554432 32 8194 13 16 2 67108872 131072 -8192 8194 16 2048 4096 
1 3 5
1 10 10
2 1 7 671367424
1 8 14
1 5 11
2 13 13 335579137
2 2 13 5376
1 2 5
2 5 6 8392768
1 1 2
2 2 14 201335872
2 1 14 0
1 11 12
1 8 12
1 4 9

33562658
131072
67242012
2081350441
2047680290
671367936
201340226
805489228
3373416393

Hint

Translated by ChatGPT 5