Note $$$maxp$$$ as the maximum index of the maximum value in $$$a$$$.

For $$$1 \leq k \leq maxp-1$$$,they do not meet the condition.

For $$$maxp+1 \leq k \leq n$$$,they all meet the condition.

You need to be careful of $$$k==maxp$$$,it meet the condition if and only if there is only one maximum value in $$$a$$$.

Note $$$a_1$$$ as the first $$$\lceil{n/2}\rceil$$$ numbers of $$$a$$$,and $$$a_2$$$ as the last $$$n-\lceil{n/2}\rceil$$$ numbers of $$$a$$$.

Through observation,we found that the following processes will be repeated cyclically:

• erase the leftmost number of $$$a_1$$$

• erase the leftmost number of $$$a_2$$$

• erase the rightmost number of $$$a_1$$$

• erase the rightmost number of $$$a_2$$$

In conclusion:

• If $$$|a_1|>|a_2|$$$(i.e. $$$n$$$ is odd),the answer is the number in the middle of $$$a_1$$$

• If $$$|a_1|=|a_2|$$$(i.e. $$$n$$$ is even),the answer is the number in the middle of $$$a_2$$$

We notice we can convert condition $$$3$$$ to $$$c0(a,l_1,r_1)-c1(a,l_1,r_1)=c1(b,l_2,r_2)-c0(b,l_2,r_2)$$$.

This provides us with convenience: we can independently calculate the left and right value ranges.

If two ranges intersect, the answer is $$$YES$$$,otherwise the answer is $$$NO$$$.

Let's calculate the left value ranges.Make all $$$a_i=0$$$ to $$$1$$$ and $$$a_i=1$$$ to $$$-1$$$,it is the value range of all subarrays of appropriate length.

In fact,we only need to find max subsegment sum and min subsegment sum.It's a classic problem.

You may have already guessed:if $$$x_1<y_1$$$,and you get $$$minsum,maxsum$$$,the range of values is continuous — $$$[minsum,maxsum]$$$.Why?

You also need to be careful of the edge cases that $$$x_i=y_i(1 \leq i \leq 2)$$$.

We notice we can calculate each bit independently.

In other words,note $$$f(a_i,j)$$$ as the $$$j^{th}$$$ bit under the binary representation of $$$a_i$$$,the answer is $$$\Sigma_{i=0}^{i=30} 2^{i}*(\Sigma f(a_l,i)⊕...⊕f(a_r,i))$$$.

Let's calculate the sum of the $$$0^{th}$$$ bit.

$$$a_{i,0}=0,1,0,1,...$$$

Note $$$pre_{i,0}=a_{1,0}⊕...⊕a_{i,0}$$$,then

$$$pre_{i,0}=0,1,1,0,0,1,1,0,...$$$

We noticed that the loop section of this sequence is $$$4$$$ and can calculate the total number of $$$'1'$$$(note it as $$$c_1$$$).The total number of subarrays with xor-value $$$1$$$ is $$$c_1*(n+1-c_1)$$$.

For the $$$1,2,...30^{th}$$$ bit,use the similar method to calculate it.

Consider an easier problem:for a fixed score $$$x_1*x_2*...*x_k$$$($$$x_i$$$ is one of the prefix minimum value and note the set of them as $$$X$$$),how to calculate the number of schemes?

Consider such a sequence construction process: put all $$$0$$$'s, all $$$1$$$'s, and all $$$2$$$'s,...

If you want the prefix minimum value of $$$i$$$ to appear in $$$a$$$, what should you do?We can get:at least one $$$i$$$ must be placed at the head of the current sequence.

This is actually equivalent to the classical problem: $$$m_i$$$ balls are put into $$$(m_1+...+m_{i-1}+1)$$$ boxes, the first box must have at least one ball,count the number of schemes.

The answer is:

$$$U_i=C(m_i-1+(m_1+...+m_{i-1}),(m_1+...+m_{i-1}))$$$.

If you want the prefix minimum value of i not to appear in $$$a$$$, what should you do?We can get:no $$$i$$$ must be placed at the head of the sequence.Solve it in a similar way as above.

The answer is:

$$$V_i=C(m_i+(m_1+...+m_{i-1})-1,(m_1+...+m_{i-1})-1)$$$.

Let's go back to the easier problem.The number of schemes is $$$\Pi_{i∈X}U_i * \Pi_{i∉X}V_i$$$.

Finally, how to calculate the total score?We can convert the formula into:$$$(1*U_1+V_1)(2*U_2+V_2)...(n*U_n+V_n)$$$.

There's another dp solution:$$$dp_i=(i-1)*U_{i-1}*dp_{i-1}+V_{i-1}*dp_{i-1}$$$.It's actually do the same thing.

Note $$$c_{i,j}=a_{i,j}⊕b_{i,j}$$$.The problem is equivalent to turning $$$c$$$ into a zero matrix.

Consider $$$l=2$$$.What about the solution?

We can easily get:the answer is $$$YES$$$ if and only if the xor-sum of all numbers is $$$0$$$.

Now let’s consider $$$l=3$$$.The method can be extended to $$$l=k$$$.

We notice we can do:

$$$0000->1110->1001$$$

If we can only filp $$${a_{x,y},a_{x,y+3}}$$$ and $$${a_{x,y},a_{x+3,y}}$$$,what about the answer?

We group the elements in the matrix $$$c$$$ like:

$$$1231231... $$$

$$$4564564... $$$

$$$7897897... $$$

$$$1231231... $$$

$$$... $$$

Note $$$XOR(i)$$$ as xor-sum of all numbers in group $$$i$$$.We can get:if all $$$XOR(i)$$$ are $$$0$$$,the answer is $$$YES$$$.

Now let’s consider the origin flip. In essence,there are only $$$6$$$ different operations:

• Flip $$$XOR(1),XOR(2),XOR(3)$$$;

• Flip $$$XOR(4),XOR(5),XOR(6)$$$;

• Flip $$$XOR(7),XOR(8),XOR(9)$$$;

• Flip $$$XOR(1),XOR(4),XOR(7)$$$;

• Flip $$$XOR(2),XOR(5),XOR(8)$$$;

• Flip $$$XOR(3),XOR(6),XOR(9)$$$.

Construct a $$$l*l$$$ matrix $$$d$$$,$$$d_{i,j}=XOR((i-1)*l+j)$$$.We find that we can turn it into a classical problem:

https://mirror.codeforces.com/problemset/problem/1475/F.