Watt

Interview

Time limit2sMemory limit1024 MB

Summary

Given an array, handle range-assign updates and count the contiguous subarrays with an even sum inside a query interval.

Level: Medium6 of 10
Topics: Segment tree, Prefix sum, Math
Solved: No attempts yet

Problem

Watt burst into the room. He had it. He had finally worked out the math behind it, and now he could show it to everyone. He had been right all along.

STEAM ENGINE! shouted Watt.

Everyone stared in disbelief.

What does your 'steam engine' actually do, Watt? asked Marin skeptically.
You give it an array of $N$ numbers and perform operations on it. One type of operation sets every element of an interval to a value. The other gives it an interval, and it tells you how many contiguous subarrays inside that interval have an even sum. Steam engine!

Marin covered his eyes with his hand.

Fine, let's try it.

Input

The first line contains natural numbers $N$ and $Q$ ( $1 \le N, Q \le 200\,000$ ), the length of the array given to the steam engine and the number of operations.

The next line contains the initial array of $N$ natural numbers $a_i$ ( $1 \le a_i \le 1\,000\,000$ ).

Each of the next $Q$ lines is one operation, in the order they are performed. Each line has one of the following two forms:

$1$ $L$ $R$ $v$ : Set every element from position $L$ to position $R$ ( $1 \le L \le R \le N$ ) to the value $v$ ( $1 \le v \le 1\,000\,000$ ).
$2$ $L$ $R$ : Ask the steam engine how many contiguous subarrays of the interval from position $L$ to position $R$ ( $1 \le L \le R \le N$ ) have an even sum.

At least one operation has the second form.

Output

For each operation of the second form, print the steam engine's answer on its own line.

Hint

The interval $[2,4]$ contains 6 distinct contiguous subarrays, and 2 of them have an even sum: $[2,3]$ and $[3,4]$ . The second answer is 0 because the fourth element is 5, which is odd. The third answer equals the first because the query was the same.

Examples3

Example 1
Input
```
5 3
8 7 7 5 1
2 2 4
2 4 4
2 2 4
```
Expected output
```
2
0
2
```

Example 2

Input

8 4
8 2 4 8 2 10 2 5
1 5 5 8
2 4 5
2 3 7
2 1 6

Expected output

3
15
21

Example 3

Input

8 4
4 9 3 8 10 1 9 10
1 1 4 3
1 2 6 7
2 1 8
2 3 5

Expected output

16
2