wqs Weighted Game

In this problem, we consider a game played on an array \(\{a_i\}\) and a corresponding binary string \(\{b_i\}\). If \(b_i=0\), then \(a_i\) is assigned to the '博' player, and if \(b_i=1\), it is assigned to the '奕' player. The game is played on a given interval \([l,r]\) where each owner, in order, decides whether to select his or her number. Each player may select any number of elements, and both players act according to optimal strategies.

The twist is that although the winning condition is defined as follows: if the bitwise XOR (denoted by \(\oplus\)) of all selected numbers is nonzero then '奕' wins, otherwise '博' wins, the '博' player is so magnanimous that she will yield to '奕' and choose actions to help him win whenever possible.

Thus, for every interval \([l,r]\), we define a function \(w(l,r)\) such that \(w(l,r)=1\) if '奕' wins and \(w(l,r)=0\) if '博' wins. Under the optimal (and cooperative) play, it turns out that if at least one number in \(\{a_l, a_{l+1}, \ldots, a_r\}\) is nonzero then the players can force the final XOR to be nonzero; if, however, all numbers are zero then the XOR remains zero.

Your task is, for each query, given two integers \(L\) and \(R\), to compute the sum

[ S = \sum_{l=L}^{R} \sum_{r=l}^{R} w(l,r) \bmod 2^{32}. ]

Special Note: Due to massive input/output sizes, when \(tp \neq 0\) the input configuration will be generated in a special way. However, the correct solution should not rely on these special methods.

inputFormat

If \(tp=0\), the input is given as follows:

1. The first line contains two integers \(n\) and \(q\) denoting the length of the sequence and the number of queries.
2. The second line contains \(n\) integers: \(a_1, a_2, \ldots, a_n\).
3. The third line contains a binary string of length \(n\) where the \(i\)-th character is \(b_i\) (either '0' or '1').
4. Each of the next \(q\) lines contains two integers \(L\) and \(R\), representing a query.

If \(tp \neq 0\), a special input method is used; however, your solution should produce the correct answer regardless.

outputFormat

For each query, output a single line containing an integer representing the sum

[ \sum_{l=L}^{R}\sum_{r=l}^{R} w(l,r) \bmod 2^{32} ]

.

sample

0
5 2
0 1 0 0 2
01010
1 3
2 5

4
7