СуперНим Junior
Ним – это игра для двух игроков, которые по очереди берут предметы, разложенные на несколько кучек. Каждый игрок в свой ход может выбрать одну из непустых кучек и забирать из нее любое ненулевое количество предметов. Проигрывает тот из игроков, кто в свою очередь не сможет сделать ход (то есть последний предмет заберет на предыдущем ходе его соперник).
Данная игра математически полностью проанализирована. Проигрышными позициями в игре называются такие позиции, что при любых дальнейших ходах игрока, который должен делать ход из данной позиции, его соперник имеет возможность делать такие ходы, которые приведут к проигрышу игрока (то есть соперник имеет выигрышную стратегию). Выигрышными – такие, что, каковы бы ни были в дальнейшем действия соперника, игрок, который выполняет ход из данной позиции, имеет возможность делать такие ходы, которые приведут его к победе (то есть игрок имеет выигрышную стратегию). Известно, что выигрышность позиции определяется ним-суммой: p_1 xor p_2 xor ... xor p_N, где p_i – количество предметов в i-ой кучке, xor – операция побитового исключающего "или" (сложение двоичных представлений чисел без учета переносов в следующие разряды). Если эта сумма отлична от нуля, то позиция выигрышная, если равна нулю – проигрышная.
Здесь мы будем иметь дело с огромным количеством кучек. Ваша задача – по заданным размерам кучек определить количество выигрышных вариантов первого хода первого игрока из начальной позиции (то есть такие ходы, при которых выигрышная стратегия все еще будет оставаться у первого игрока).
Input
В первой строке входного файла содержится целое число M, определяющее количество групп кучек. Каждая из последующих M строк описывает соответствующую группу с помощью двух целых чисел a, b. В группе будет b-a+1 кучек c размерами от a до b включительно.
1 ≤ M ≤ 100000, 0 ≤ a ≤ b ≤ 10^12.
Output
Выведите единственное целое число – количество вариантов первого хода, которое допускает выигрышная стратегия.