Маленькая девочка Маргарита — большая любительница спортивного программирования. Особенно она любит задачи про массивы и запросы к ним.
Недавно ей подарили массив \(a\) размером в \(10^9\) элементов, который заполнен следующим образом:
- \(a_1 = -1\)
- \(a_2 = 2\)
- \(a_3 = -3\)
- \(a_4 = 4\)
- \(a_5 = -5\)
- И так далее...
То есть значение \(i\)-го элемента массива \(a\) вычисляется по формуле \(a_i = i \cdot (-1)^i\).
Она сразу же придумала \(q\) запросов к этому массиву. Каждый запрос задаётся двумя числами: \(l\) и \(r\). Ответом на запрос является сумма всех элементов массива на позициях от \(l\) до \(r\) включительно.
Маргарита очень хочет узнать ответ на каждый из запросов. Вручную она это всё считать не хочет, но и программу, решающую задачу, к сожалению, написать не смогла. Она обратилась к вам — лучшему программисту.
Помогите ей найти ответы!
Выходные данные
Выведите \(q\) строк, по одному числу в каждой — ответы на запросы.
Примечание
В первом запросе нужно найти сумму элементов массива от позиции \(1\) до позиции \(3\). Эта сумма равна \(a_1 + a_2 + a_3 = -1 + 2 -3 = -2\).
Во втором запросе нужно найти сумму элементов массива от позиции \(2\) до позиции \(5\). Эта сумма равна \(a_2 + a_3 + a_4 + a_5 = 2 -3 + 4 - 5 = -2\).
В третьем запросе нужно найти сумму элементов массива от позиции \(5\) до позиции \(5\). Эта сумма равна \(a_5 = -5\).
В четвёртом запросе нужно найти сумму элементов массива от позиции \(4\) до позиции \(4\). Эта сумма равна \(a_4 = 4\).
В пятом запросе нужно найти сумму элементов массива от позиции \(2\) до позиции \(3\). Эта сумма равна \(a_2 + a_3 = 2 - 3 = -1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 3
2 5
5 5
4 4
2 3
|
-2
-2
-5
4
-1
|