В системе хранения данных есть массив из n целых чисел a_1, a_2, ..., a_n, где позиции нумеруются с 1.

Система ведёт раздельный учёт значений на нечётных и чётных позициях. Затем поступает q запросов. Каждый запрос задаётся двумя числами l и r и относится к непрерывному отрезку массива [l, r].

Для каждого запроса требуется определить два значения:

• S_odd — сумму элементов массива на нечётных позициях, принадлежащих отрезку [l, r];
• S_even — сумму элементов массива на чётных позициях, принадлежащих отрезку [l, r].

Так как запросов много, необходимо обрабатывать их эффективно.

Входные данные

Первая строка содержит два целых числа n и q — размер массива и количество запросов.

Вторая строка содержит n целых чисел a_i.

В следующих q строках содержится по два целых числа l и r — границы очередного запроса.

Выходные данные

Для каждого запроса выведите в отдельной строке два целых числа: S_odd и S_even.

Ограничения

• 1 <= n, q <= 2 * 10^5
• -10^9 <= a_i <= 10^9
• 1 <= l <= r <= n

Примеры

Пример 1

Входные данные

1 1
5
1 1

Выходные данные

5 0

Пример 2

Входные данные

2 4
-7 8
1 1
2 2
1 2
1 2

Выходные данные

-7 0
0 8
-7 8
-7 8