Задача №113872. Выбор отрезка
Планету Марс можно представить в виде нескольких площадок, расположенных подряд и пронумерованных от 1 до n . На каждой площадке лежит a i камней.
Aex'hrie участвует в марсианском турнире по игре Ним. Турнир состоит из нескольких раундов. В очередном раунде Aex'hrie играет против ведущего игры. Он играет отдельные игры на всех возможных подотрезках некоторого отрезка площадок планеты Марс и во всех играх ходит первым (то есть при заданных l и r , играются все возможные игры с кучками камней с площадок с i по j , такие, что l ≤ i ≤ j ≤ r ). Кроме того, у Aex'hrie есть кучка из k камней, которая участвует во всех этих играх (то есть к каждой из игр добавляется кучка из k камней).
Для каждого раунда вам известны l и r . Aex'hrie хочет выяснить, сколько игр в каждом раунде он проиграет даже при идеальной стратегии игры.
В первой строке даны целые числа n , m и k ( 1 ≤ n , m ≤ 100 000, 0 ≤ k ≤ 2 20 - 1 ) — количество площадок, количество раундов и количество камней в кучке Aex'hrie соответственно.
Во второй строке записаны n целых чисел a i ( 0 ≤ a i ≤ 2 20 - 1 ) — количество камней на каждой из площадок.
Дальше идут m строк. В i -й строке записаны числа l i и r i ( 1 ≤ l i ≤ r i ≤ n ), описывающие i -й раунд турнира.
Выведите m строк: количество заведомо проигрышных игр в каждом раунде, в порядке их описания во входном файле.
6 2 3 1 2 1 1 0 3 1 6 3 5
7 0
5 3 1 1 1 1 1 1 1 5 2 4 1 3
9 4 4