Интернет-магазин ведёт две параллельные последовательности данных по часам работы.

• a_i — количество товаров, проданных в i-й час;
• b_i — цена товара в i-й час.

Для каждого запроса с границами l и r требуется вычислить общую выручку за часы с l по r включительно. Выручка на таком отрезке равна сумме попарных произведений соответствующих элементов:

a_l * b_l + a_{l+1} * b_{l+1} + ... + a_r * b_r.

Для каждого запроса выведите найденную выручку.

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

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

Вторая строка содержит n целых чисел a_1, a_2, ..., a_n — количества проданных товаров.

Третья строка содержит n целых чисел b_1, b_2, ..., b_n — цены товаров.

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

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

Для каждого запроса выведите одно целое число — выручку интернет-магазина на отрезке [l, r].

Ограничения

• 1 <= n, q <= 2 * 10^5
• 0 <= a_i <= 10^4
• 0 <= b_i <= 10^4
• 1 <= l <= r <= n

Примеры

Пример 1

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

1 1
0
5
1 1

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

0

Пример 2

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

5 6
0 1 2 3 4
5 0 2 1 3
1 1
5 5
1 5
2 2
1 2
4 4

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

0
12
19
0
0
3