와트

와트가 방에 뛰어들었다. 그는 그 장치를 이미 가지고 있었다. 마침내 그 뒤의 수학을 풀어서 이제 모두에게 보여줄 수 있게 되었다. 그는 처음부터 옳았다.

• 증기 기관! - 와트가 외쳤다.

모두가 믿기지 않는다는 듯 그를 쳐다보았다.

• 그 '증기 기관'은 대체 뭘 하는 건데, 와트? - 마린이 의심스럽게 물었다.
• $N$개의 수로 이루어진 배열을 주고, 그 위에서 연산을 한다. 한 종류의 연산은 구간의 모든 원소를 어떤 값으로 바꾸는 것이다. 다른 종류는 구간을 주면, 그 안에서 합이 짝수인 연속 부분 수열이 몇 개인지 알려주는 것이다. 증기 기관!

마린이 손으로 눈을 가렸다.

• 좋아, 그럼 한번 해 보자.

첫 줄에 자연수 $N$과 $Q$($1 \le N, Q \le 200\,000$)가 주어진다. $N$은 증기 기관에 주어지는 배열의 길이이고, $Q$는 실행할 연산의 수이다.

다음 줄에는 증기 기관에 주어진 길이 $N$의 초기 배열 $a_i$($1 \le a_i \le 1\,000\,000$)가 주어진다.

다음 $Q$개의 줄에는 실행된 연산이 순서대로 주어진다. 각 줄은 다음 두 형태 중 하나이다.

• $1$ $L$ $R$ $v$: $L$번째부터 $R$번째 원소($1 \le L \le R \le N$)까지 모든 원소를 값 $v$($1 \le v \le 1\,000\,000$)로 바꾼다.
• $2$ $L$ $R$: $L$번째부터 $R$번째 원소($1 \le L \le R \le N$)까지의 구간에서 합이 짝수인 연속 부분 수열이 몇 개인지 증기 기관에 묻는다.

두 번째 형태의 연산이 적어도 하나 있다.

두 번째 형태의 각 연산에 대해, 증기 기관의 답을 한 줄에 하나씩 출력한다.

구간 $[2,4]$에는 서로 다른 연속 부분 수열이 6개 있고, 그중 합이 짝수인 것은 2개이다. 그것은 $[2,3]$과 $[3,4]$이다. 네 번째 원소가 5, 즉 홀수이므로 두 번째 답은 0이다. 질문이 같았으므로 세 번째 답은 첫 번째 답과 같다.