If b$b$ is even, then only the last digit matters.

Otherwise bk$b^k$ is odd for any k$k$, so each digit is multiplied by odd number. A sum of several summands is even if and only if the number of odd summands is even. So we should just compute the number of even digits.

Let's start with n$n$ pieces of length 1$1$ covering only broken segments and then decrease the number of pieces used. After reducing the number of segments by x$x$, some x$x$ of long uncovered initial segments of unbroken places will be covered. It's easy to see that you should cover the shortest x$x$ segments.

Thus, to make at most k$k$ segments, you should cover n−k$n-k$ shortest initial segments. You can find their total length using sort.

Denote the highest bit of a$a$ as x$x$ (that is largest number x$x$, such that 2x≤a$2^x\le a$) and consider b=(2x−1)⊕a$b=(2^x-1)\oplus a$. It's easy to see that if a≠2x−1$a\ne 2^x-1$ then 0<b<a$0<b<a$ holds. In this, gcd$gcd$ is maximum possible, because a&b=0$a\mathrm{\&}b=0$ и gcd(2x−1,0)=2x−1$gcd(2^x-1,0)=2^x-1$.

Now consider the case when a=2x−1$a=2^x-1$. This implies gcd(a⊕b,a&b)=gcd(2x−1−b,b)=gcd(2x−1,b)$gcd(a\oplus b,a\mathrm{\&}b)=gcd(2^x-1-b,b)=gcd(2^x-1,b)$, since gcd(x,x+y)=gcd(x,y)$gcd(x,x+y)=gcd(x,y)$ (for all x$x$ and y$y$), hence it's sufficient to find the largest non trivial divisor of a$a$ — it will be the desired answer.

Finding the largest divisor can be done in sqrt time which leads to the time O(qm−−√)$O(q\sqrt{m})$ or it's possible to calculate answers for all a=2x−1$a=2^x-1$ beforehand.

First thing to note is that one can try solving this problem with different greedy approaches, but authors don't know any correct greedy.

To solve this problem, note that you can always replace 3$3$ triples of type [x,x+1,x+2]$[x,x+1,x+2]$ with triples [x,x,x]$[x,x,x]$, [x+1,x+1,x+1]$[x+1,x+1,x+1]$ and [x+2,x+2,x+2]$[x+2,x+2,x+2]$. So we can assume that there are at most 2$2$ triples of type [x,x+1,x+2]$[x,x+1,x+2]$ for each x$x$.

Having noted this, you can write dynamic programming solution. Let ans[i][t1][t2] be the answer considering only the first i$i$ denominations, and there are t1$t_1$ triples of type [i−1,i,i+1]$[i-1,i,i+1]$ and t2$t_2$ triples of type [i,i+1,i+2]$[i,i+1,i+2]$. Try all possible number t3$t_3$ of triples of type [i+1,i+2,i+3]$[i+1,i+2,i+3]$, put all the remaining tiles of denomination i+1$i+1$ into triples [i+1,i+1,i+1]$[i+1,i+1,i+1]$ and make a transition to ans[i + 1][t2][t3].

Consider the difference array d1,d2,…,dn−1$d_1,d_2,\dots ,d_{n-1}$, where di=ci+1−ci$d_i=c_{i+1}-c_i$. Let's see what happens if we apply synchronization.

Pick an arbitrary index j$j$ and transform cj$c_j$ to c′j=cj+1+cj−1−cj$c_j^{\prime }=c_{j+1}+c_{j-1}-c_j$. Then:

• d′j−1=c′j−cj−1=(cj+1+cj−1−cj)−cj−1=cj+1−cj=dj$d_{j-1}^{\prime }=c_j^{\prime }-c_{j-1}=(c_{j+1}+c_{j-1}-c_j)-cj-1=c_{j+1}-c_j=d_j$;
• d′j=cj+1−c′j=cj+1−(cj+1+cj−1−cj)=cj−cj−1=dj−1$d_j^{\prime }=c_{j+1}-c_j^{\prime }=c_{j+1}-(c_{j+1}+c_{j-1}-c_j)=c_j-cj-1=d_{j-1}$.

In other words, synchronization simply transposes two adjacent differences. That means that it's sufficient to check whether the difference arrays of two sets of stones are equal and make sure that s1=t1$s_1=t_1$.

Let's answer the queries offline: for each vertex we'll remember all queries for it.

Let's make vertex 1$1$ root and find distances from it to all leaves using DFS. Now for answering queries for vertex 1$1$ we should simply answer some range minimum queries, so we'll build a segment tree for it.

For answering queries for other vertices we will make segment trees with distances to leaves (like we did for handling queries for vertex 1$1$) for all vertices. We will traverse vertices of a tree using DFS and maintain actual distances to leaves in segment tree. Suppose, DFS went through edge (u,v)$(u,v)$ with weight w$w$ where u$u$ is an ancestor of v$v$. Distances to leaves in subtree of v$v$ will decrease by w$w$ and distances to other vertices will increase by w$w$. Since set of leaves in subtree of some vertex is a subsegment of vertices written in euler traversal order, we should simply make range additions/subtractions on segment tree to maintain distances to leaves when passing through an edge.

This way we got a solution with O(nlogn+qlogn)$O(n\log n+q\log n)$ complexity.

To start with, let's notice that the white vertices are not necessary. Actually, you can solve the problem analyzing the cases with the whites as well, but there is an easy way to get rid of them:

Examine the following construction:

That is, replace the white A$A$ with some set of four non-white vertices.

One can notice, that neither white nor black can win on these four vertices. That means that they are actually interested in getting the color of the end of this graph, connected to the remaining graph being of their color — it can help them later.

Let's start the game as white player and paint a vertex A$A$ white. If black player will not paint the vertex B$B$ black, we have a win. Otherwise, two turns have passed now and that means that the "parity" has preserved and it is our turn again. Then we can play as we would have played in the original game, except if the black player paints C$C$ or D$D$ in some point, we should color the remaining one (and the parity will preserve again).

———————

Now let's solve the problem assuming there are no white vertices.

Note, that if there is a vertex of degree 4$4$ or more, then the white player wins, maing the first move into that vertex, and then two moves in some leaves of this vertex.

In case there is a vertex of degree 3$3$ having at least two non-white neighbors, then it's a win as well: we can either collect a path going through this vertex or going through non-leave neighbor somewhere else.

Now, note that if there are at least 3$3$ vertexes of degree 3$3$, this implies the case above.

So we are left with a case when there are at most three vertices of degree 3$3$ and all other have degree 1$1$ or 2$2$.

It's natural to claim (and many got wa2 for that), that all remaining cases are draws. But it's not true:

It's easy to see, that this game (picture above) is winning for white. Applying the same argument, as before, we can deduce that the game above is equivalent to the game below. Which is clearly winning for white.

Actually, any path having odd number of vertices and colored in white on both ends is winning for white (make a move into the vertex colored blue on the picture below):

This actually meains, that in our solution, in which we got rid of all white vertices, the winning cases are «bones» having odd number of vertices.

It's possible to show, that in all other cases the game will end in draw.

Set of modest numbers could be represented by set of size approximately (|l|+|r|)⋅10$(|l|+|r|)\cdot 10$ of regular expressions of form d0d1d2…dk−1[0−9]{e}$d_0{d}_1{d}_2\dots d_{k-1}[0-9]\{e\}$, where |l|$|l|$ and |r|$|r|$ are lengths of numbers l$l$ and r$r$ correspondingly, and di$d_i$ are digits. Set of regular expressions can be build in the following way. Consider prefix of l$l$ of length x$x$. Then for every q>lx$q>l_x$ let's make the following expression: l0l1l2…lx−1q[0−9]{|l|−x−1}$l_0{l}_1{l}_2\dots l_{x-1}q[0-9]\{|l|-x-1\}$. Similarly for r$r$, but here q<rx$q<r_x$. Also for all |l|<x<|r|$|l|<x<|r|$ we should make regular expressions [1−9][0−9]{x−1}$[1-9][0-9]\{x-1\}$, this is equal to nine expressions of our form. Notice that every modest number would satisfy exactly one regular expression and no other number would satisfy any expression.

Let's call wildcard of length x$x$ tail of regular expression of form [0−9]{x}$[0-9]\{x\}$. Let's build Aho-Corasick automaton for all prefixes of regular expressions until wildcards. For every regular expression put in corresponding node length of wildcard. After that task could be solved using dynamic programming. State would be length of prefix of answer and node of the automaton. From state (i,v)$(i,v)$ we can go by digit d$d$ to the state (i+1,u)$(i+1,u)$, u$u$ is node where d$d$ leads from v$v$. Value for (i+1,u)$(i+1,u)$ should be updated by value for (i,v)$(i,v)$ plus number of wildcards with lengths not exceeding n−i−1$n-i-1$, placed in nodes reachable from u$u$ by suffix links in automaton. This value can be calculated beforehand for every pair node and length. Asymptotics of solution is O((|l|+|r|)⋅n⋅Σ2)$O((|l|+|r|)\cdot n\cdot {\mathrm{\Sigma }}^2)$, where Σ$\mathrm{\Sigma }$ is size of alphabet, i.e. 10$10$.