Алиса уже много лет дарит подарки Бобу, а потому знает, что больше всего ему нравится делать побитовый XOR интересных чисел, при этом интересными Боб считает такие целые положительные числа \(x\), для которых выполнено \(x \not\equiv k (\bmod 2^i)\). Поэтому в этом году на его очередной день рождения она подарила ему сверхмощный «XORофикатор 3000», самую последнюю модель.
Бобу подарок очень понравился, ведь благодаря нему он мог мгновенно делать XOR всех интересных чисел на любом отрезке от \(l\) до \(r\) включительно, а что, в самом деле, ещё нужно человеку для счастья? Но, к сожалению, прибор оказался настолько мощным, что в какой-то момент сделал XOR с самим собой и исчез. Боб был очень расстроен, и Алиса, чтобы хоть как-то подбодрить его, попросила вас написать свою версию «XORофикатора».
Выходные данные
Для каждого запроса выведите одно число — XOR всех чисел \(x\) на отрезке \([l, r]\) таких, что \(x \not\equiv k \mod 2^i\).
Примечание
В первом запросе на отрезке \([1, 3]\) интересными являются числа \(1\) и \(3\), поэтому ответом будет число \(1 \oplus 3 = 2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 3 1 0
2 28 3 7
15 43 1 0
57 2007 1 0
1010 1993 2 2
1 1000000000 30 1543
|
2
2
13
0
4
1000000519
|