SuperNim Junior#2878
Nim is a game for two players who take turns picking up items that are distributed into several piles. On each turn, a player chooses a non-empty pile and removes any nonzero number of items from it. The player who cannot make a move on their turn (that is, whose opponent made the last move and took the last item) loses.
This game has been completely analyzed mathematically. Losing positions are those positions such that, whatever moves the player to play from that position makes, their opponent can always respond so that they will eventually win (i.e., the opponent has a winning strategy). Winning positions are those from which, regardless of how the opponent plays, the player making the move can always respond so as to ultimately win (i.e., the player has a winning strategy).
It is known that the winning status of a position is determined by the nim-sum:
where p_i is the number of items in the -th pile, and denotes the bitwise exclusive OR operation (i.e., adding the binary representations of the numbers without carrying over). If the nim-sum is nonzero, the position is winning; if it is zero, the position is losing.
In this problem, you are given a very large number of piles. Your task is: given the sizes of the piles, determine the number of ways for the first player to make a first move from the initial position such that the first player still has a winning strategy afterward (i.e., the move leaves the first player with a winning position).
The first line contains an integer , the number of groups of piles. Each of the next lines describes a group by two integers and . The group consists of b-a+1 piles with sizes to , inclusive.
1 \leq M \leq 100000, 0 \leq a \leq b \leq 10^{12}.
Print a single integer — the number of possible first moves that allow a winning strategy for the first player.
Example 1