Дворецкий Остин хочет показать Аркадию, что ряды из нечетного числа фонтанов — это красиво, а ряды из четного числа фонтанов — нет.
Дворецкий хочет показать Аркадию n садов. Каждый сад представляет из себя ряд из m клеток, в i-м из садов в каждой клетке с li по ri включительно находится фонтан, и больше фонтанов в этом саду нет. Проблема в том, что некоторые из садов все-таки имею четное число фонтанов, что недопустимо показывать Аркадию.
Остин хочет выбрать два числа a ≤ b и показать из каждого сада лишь участок, начинающийся в клетке a и кончающийся в клетке b. Конечно, подойдут лишь такие участки, что в каждом саду на этом отрезке либо нет фонтанов, либо нечетное число фонтанов. Кроме того, необходимо, чтобы хотя бы в одном саду на участке клеток от a до b был хотя бы один фонтан.
Помогите Остину найти суммарную длину всех таких участков, то есть, просуммируйте величину (b - a + 1) для каждой подходящей пары (a, b).
Выходные данные
Выведите одно число — суммарную длину всех подходящих участков.
Примечание
В первом примере подходят следующие пары (a, b): (1, 2), (1, 4), (1, 5), (2, 2), (2, 4), (2, 5), (3, 3), (4, 4), (4, 5).
Во втором примере подходят следующие пары (a, b): (1, 2), (1, 5), (2, 2), (2, 5), (3, 3), (4, 4), (4, 6), (5, 5), (6, 6).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 5
2 4
|
23
|
|
2
|
3 6
2 4
3 6
4 4
|
19
|