Online 01 Sequence Maintenance

We are given a binary sequence \(a\) of length \(n\) (each element is either 0 or 1). You need to process \(m\) operations on this sequence. The operations are given in online fashion: for each operation, the parameters \(l\) and \(r\) are given, but before using them you must update them via

\(l = l \oplus last\) and \(r = r \oplus last\),

where \(last\) is the answer of the previous query operation (operation 7), or \(0\) if there was no previous query.

The operations are:

• 1 l r: For every index \(i\) with \(l \le i \le r\), set \(a_i = 0\).
• 2 l r: For every index \(i\) with \(l \le i \le r\), set \(a_i = 1\).
• 3 l r: Simultaneously, for every index \(i\) with \(l \le i \le r-1\), update \(a_i\) to \(a_i \lor a_{i+1}\) (bitwise OR).
• 4 l r: Simultaneously, for every index \(i\) with \(l+1 \le i \le r\), update \(a_i\) to \(a_i \lor a_{i-1}\) (bitwise OR).
• 5 l r: Simultaneously, for every index \(i\) with \(l \le i \le r-1\), update \(a_i\) to \(a_i \land a_{i+1}\) (bitwise AND).
• 6 l r: Simultaneously, for every index \(i\) with \(l+1 \le i \le r\), update \(a_i\) to \(a_i \land a_{i-1}\) (bitwise AND).
• 7 l r: Query the sum of elements in the interval \([l, r]\).

Note: All intervals are 1-indexed. If after XOR the computed \(l\) is greater than \(r\), swap them before processing.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq \text{small constraints}) \) — the length of the sequence and the number of operations.

The second line contains a string of length \(n\) consisting of characters '0' and '1' representing the initial sequence \(a\).

Then follow \(m\) lines, each describing an operation in the format:

op l r

Before processing each operation, update \(l\) and \(r\) as: \(l = l \oplus last\) and \(r = r \oplus last\), where \(last\) is the answer from the previous query (operation 7), or 0 if there was no previous query. If \(l > r\) after XOR, swap \(l\) and \(r\).

outputFormat

For each query operation (operation 7), output a single line with one integer — the sum of \(a_i\) for \(l \le i \le r\).

sample

5 3
10101
2 1 3
3 2 4
7 3 5

2