또 다른 돌 게임

코토리와 우미는 호노카가 주최하는 돌 게임을 한다. 규칙은 고전적인 돌 게임과 같다. 여러 개의 돌 더미가 있고 두 사람이 번갈아 가며 한 더미에서 양의 개수만큼 돌을 가져간다. 합법적인 수를 둘 수 없는 사람이 진다.

이번에는 상황이 조금 다르다. 주최자인 호노카는 $n$개의 후보 더미로 게임을 준비하는데, $i$번째 더미에는 처음에 $a\_i$개의 돌이 있다. 호노카는 다음 두 종류의 연산을 $q$번 수행한다.

1. 세 정수 $l$, $r$, $x$가 주어지면, 모든 $l \le i \le r$에 대해 $i$번째 후보 더미의 돌 개수를 $\max(b\_i, x)$로 바꾼다. 여기서 $b\_i$는 $i$번째 후보 더미의 현재 돌 개수이다.
2. 세 정수 $l$, $r$, $x$가 주어지면, $(r-l+2)$개의 더미로 이루어진 돌 게임을 시작한다. $1 \le i < (r-l+2)$인 $i$번째 더미에는 $b\_{l-1+i}$개의 돌이 있고, $(r-l+2)$번째 더미에는 $x$개의 돌이 있다. 이 연산은 답을 구하기 위한 질의일 뿐이며 $n$개의 후보 더미 상태에는 영향을 주지 않는다.

코토리가 항상 선공이다. 코토리의 열렬한 팬인 당신은, 두 사람이 최선의 전략을 사용할 때 코토리가 첫 번째 수로 두어 승리를 확정지을 수 있는 방법의 수를 각 돌 게임마다 알고 싶어 한다. 코토리가 서로 다른 더미에서 돌을 가져가거나, 같은 더미에서 서로 다른 개수의 돌을 가져가는 두 경우를 서로 다른 방법으로 본다.

각 테스트 파일에는 테스트 케이스가 하나만 있다.

입력의 첫 번째 줄에는 두 정수 $n$과 $q$ ($1 \le n, q \le 2 \times 10^5$)가 주어지며, 이는 후보 더미의 수와 연산의 수이다.

두 번째 줄에는 $n$개의 정수 $a\_1, a\_2, \cdots, a\_n$ ($0 \le a\_i \le 2^{30}-1$)이 주어지며, $a\_i$는 $i$번째 더미의 처음 돌 개수이다.

다음 $q$개의 줄 중 $i$번째 줄에는 네 정수 $op\_i$, $l\_i$, $r\_i$, $x\_i$ ($op\_i \in \{1, 2\}$, $1 \le l\_i \le r\_i \le n$, $0 \le x\_i \le 2^{30}-1$)가 주어지며, $i$번째 연산을 나타낸다. $op\_i$는 연산의 종류이고 나머지는 연산의 매개변수이다. 연산은 수행되는 순서대로 주어진다.

두 번째 종류의 연산마다 답을 나타내는 정수 하나를 한 줄에 출력한다.

첫 번째 연산에 대해 플레이어들은 각 더미에 $1$, $2$, $1$, $1$개의 돌이 있는 돌 게임을 한다. 코토리가 이길 수 있는 유일한 수는 돌이 $2$개인 더미를 $1$개로 줄이는 것이다.

두 번째 연산 후 후보 더미의 돌 개수는 각각 $1$, $3$, $3$, $4$, $1$로 바뀐다.

네 번째 연산에 대해 플레이어들은 각 더미에 $1$, $3$, $3$, $4$, $4$개의 돌이 있는 돌 게임을 한다. 코토리가 이길 수 있는 수는 돌이 $1$개인 더미를 $0$개로 줄이거나, 돌이 $3$개인 더미 중 아무거나 $2$개로 줄이는 것이다.