Flip

각 원소가 0 또는 1인 길이 $n$의 배열이 주어진다. $1 \le \ell \le r \le n$인 모든 쌍 $(\ell, r)$에 대해 $[a[\ell], a[\ell+1], \ldots, a[r]]$를 배열 $[a[1], a[2], \ldots, a[n]]$의 부분배열이라 한다. 배열 $[a[1], a[2], \ldots, a[n]]$의 부분배열 $[a[\ell], a[\ell+1], \ldots, a[r]]$이 교대 부분배열이라 함은 $a[\ell] \ne a[\ell+1] \ne \cdots \ne a[r]$인 경우를 말한다. 즉, 부분배열의 모든 원소가 부분배열 내의 이웃한 원소와 다른 경우이다. 교대 부분배열의 정의는 부분배열 내부의 원소만 고려하므로, $[1, 0, 1]$은 $[1, 1, 0, 1, 1]$의 교대 부분배열이다.

이 문제에서는 주어진 배열에 두 종류의 연산이 적용된다.

• 1 ℓ r: 모든 $i \in [\ell, r]$에 대해 $a[i]$를 $1 - a[i]$로 바꾼다.
• 2 ℓ r: $\ell \le x \le y \le r$이고 부분배열 $[a[x], a[x+1], \ldots, a[y]]$가 교대 부분배열인 쌍 $(x, y)$의 개수를 출력한다.

주어진 배열을 유지하는 프로그램을 작성하라. 프로그램은 개수를 효율적으로 출력해야 한다.

첫째 줄에 두 정수 $n$과 $q$가 주어진다. $n$은 주어진 배열의 길이, $q$는 연산의 개수이다. 둘째 줄에 주어진 배열 $[a[1], a[2], \ldots, a[n]]$을 나타내는 $n$개의 수 $a[1], a[2], \ldots, a[n]$이 공백으로 구분되어 주어진다. 이어서 $q$개의 줄이 주어지며, $i$번째 줄에는 3개의 정수 $t_i, \ell_i, r_i$가 주어진다. $i$번째 연산은 $t_i\ \ell_i\ r_i$이다.

두 번째 종류의 연산마다 해당 개수를 한 줄에 출력한다.

• $1 \le n \le 200000$
• $1 \le q \le 200000$
• 모든 $i \in \{1, 2, \ldots, n\}$에 대해 $a[i] \in \{0, 1\}$이다.
• 모든 $j \in \{1, 2, \ldots, q\}$에 대해 $t_j \in \{1, 2\}$이다.
• 모든 $j \in \{1, 2, \ldots, q\}$에 대해 $1 \le \ell_j \le r_j \le q$이다.