Honoka's Stone Games

Kotori and Umi are playing a variant of the classic nim game hosted by Honoka. Initially, there are n candidate piles of stones, where the i-th pile contains a_i stones. Honoka will perform q operations. There are two types of operations:

• Type 1: Given three integers l, r and x, for every index i in the range \(l \le i \le r\) update the number of stones in the i-th candidate pile to \(b_i = \max(b_i, x)\), where \(b_i\) is its current value.
• Type 2: Given three integers l, r and x, a game is started using (r - l + 2) piles such that the first (r - l + 1) piles come from \(b_l, b_{l+1}, \dots, b_r\) and an extra pile with x stones is appended as the last pile.

The game follows the standard nim rule: players take turns removing any positive number of stones from one pile; the player unable to make a move loses. Kotori always moves first. For each game (i.e. each Type 2 operation), determine the number of ways Kotori can make her first move to ensure her victory assuming both players play optimally. Note: Two moves are considered different if they involve removing stones from different piles, or from the same pile but with a different number of stones removed.

Hint: In a normal nim game with piles \(p_1, p_2, \dots, p_k\) and overall nim-sum \(S = p_1 \oplus p_2 \oplus \dots \oplus p_k\), the only winning move is to reduce a pile \(p_i\) to \(p_i' = p_i \oplus S\) when \(p_i' < p_i\). This move is unique for each pile satisfying \(p_i \oplus S < p_i\). If \(S = 0\), no winning move exists.

Your task is to simulate all operations and for each Type 2 operation output the number of winning moves for Kotori.

inputFormat

The first line of the input contains two integers (n) and (q) representing the number of candidate piles and the number of operations, respectively. The second line contains (n) integers (a_1, a_2, \dots, a_n) representing the initial number of stones in the candidate piles. Each of the following (q) lines contains an operation in the format:

op l r x

Where op is either 1 or 2. If op = 1, then for every index (i) with (l \le i \le r) update (b_i = \max(b_i, x)). If op = 2, then consider a game with ((r - l + 2)) piles where the first ((r - l + 1)) piles are (b_l, b_{l+1}, \dots, b_r) and the last pile contains x stones.

For each Type 2 operation, you are required to output a single line containing the number of winning moves for Kotori.

outputFormat

For every operation of type 2, print a single line with an integer representing the number of ways Kotori can make a winning move in her first turn.

sample

5 5
1 2 3 4 5
2 2 4 1
1 1 3 3
2 2 5 0
1 1 5 5
2 3 3 2

1
3
1