Nim
Contest: Educational Codeforces Round 173 (Rated for Div. 2)
Difficulty rating: 2700
Tags: bitmasks, brute force, combinatorics, dp, games, greedy, implementation, shortest paths

Recall the rules of the game "Nim". There are $$$n$$$ piles of stones, where the $$$i$$$-th pile initially contains some number of stones. Two players take turns choosing a non-empty pile and removing any positive (strictly greater than $$$0$$$) number of stones from it. The player unable to make a move loses the game.

You are given an array $$$a$$$, consisting of $$$n$$$ integers. Artem and Ruslan decided to play Nim on segments of this array. Each of the $$$q$$$ rounds is defined by a segment $$$(l_i, r_i)$$$, where the elements $$$a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$$$ represent the sizes of the piles of stones.

Before the game starts, Ruslan can remove any number of piles from the chosen segment. However, at least one pile must remain, so in a single round he can remove at most $$$(r_i - l_i)$$$ piles. He is allowed to remove $$$0$$$ piles. After the removal, the game is played on the remaining piles within the segment.

All rounds are independent: the changes made in one round do not affect the original array or any other rounds.

Ruslan wants to remove as many piles as possible so that Artem, who always makes the first move, loses.

For each round, determine:

1. the maximum number of piles Ruslan can remove;
2. the number of ways to choose the maximum number of piles for removal.

Two ways are considered different if there exists an index $$$i$$$ such that the pile at index $$$i$$$ is removed in one way but not in the other. Since the number of ways can be large, output it modulo $$$998\,244\,353$$$.

If Ruslan cannot ensure Artem's loss in a particular round, output -1 for that round.

Input format:
The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — the size of the array and the number of segments for which the answers need to be calculated.

The second line of input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 50$$$) — the elements of the initial array.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the bounds of the segment on which the boys want to play the game during the $$$i$$$-th round.

Output format:
For each round:

- if Ruslan can win, print two integers — the maximum number of piles that can be removed, and the number of ways to remove the maximum number of piles, taken modulo $$$998\,244\,353$$$;
- otherwise print -1.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Example input:
9 5
0 1 2 1 3 4 5 6 0
1 5
2 5
3 5
4 5
1 9

Example output:
4 1
2 1
0 1
-1
8 2

Editorial:
Let's recall the condition for the second player to win in the game of "Nim". The XOR of the sizes of the piles must be equal to $$$0$$$. That is, we are asked to remove as many piles as possible so that the XOR becomes $$$0$$$.
Notice the following fact. Suppose there are $$$c$$$ piles of size $$$x$$$ on a segment. If we remove an even number of piles, the XOR does not change. If we remove an odd number, it changes by $$$x$$$. Therefore, there is no point in keeping more than $$$2$$$ piles. If we keep $$$t > 2$$$ piles, we can remove another $$$2$$$ piles, and it will not change anything at all.
We will answer the queries independently. Let's find the count of each of the $$$51$$$ elements in the given segment. For example, we can precompute how many times each element appears in each prefix.
Now we can write the following dynamic programming solution. $$$\mathit{dp}[i][j][f]$$$ represents a pair of (maximum amount of removed elements, number of ways to remove that amount), where we have considered the first $$$i$$$ of the $$$51$$$ values, the current XOR among the non-removed values is $$$j$$$, and $$$f = 1$$$ if at least one element is not removed and $$$0$$$ otherwise.
Let the amount of the current value be $$$c$$$. From each state, there are at most three transitions:
• remove all elements with that value — $$$1$$$ way;
• keep $$$1$$$ element — $$$c$$$ ways;
• keep $$$2$$$ elements — $$$\frac{c(c-1)}{2}$$$ ways.
The base case is $$$\mathit{dp}[0][0][0] = (0, 1)$$$, the rest are filled with $$$(-1, -1)$$$, for example. The final state is $$$\mathit{dp}[51][0][1]$$$. If it's equal to $$$(-1, -1)$$$, there's no answer.
Since the XOR cannot exceed $$$63$$$, the number of states in the dynamic programming solution is $$$51 \cdot 64 \cdot 2$$$. From each state, there are three transitions, which fits within the time constraints.