Районная олимпиада по информатике 2019 года за 8 класс | Казахстанские олимпиады

Задача C. Сумма квадратов

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

Даны два массива целых чисел длинны nn. Даются qq запросов. Каждый запрос состоит из чисел ll и rr, после каждого запроса требуется вывести чему равна сумма квадратов разностей чисел a[i]a[i] и b[i]b[i] где ii= ll, ll+1,.., rr.

Формат входного файла

Первая строка содержит числа n,q,(1n,q100000)n, q, (1 \leq n, q \leq 100000)\newline Вторая строка содержит массив n целых чисел(массив a)\newline Вторая строка содержит массив n целых чисел(массив b)\newline (100000a[i],b[i]100000)(-100000 \leq a[i], b[i] \leq 100000), ii = 1, 2, ... , nn\newline Следующие qq строк содержат числа l,r,(1lrn)l, r, (1 \leq l \leq r \leq n)

Система оценки:\newline Для 40% тестов - (1n,q100)(1 \leq n, q \leq 100)\newline Для 60% тестов - (1n,q100000)(1 \leq n, q \leq 100000)

Формат выходного файла

В каждой строке выведите ответы на запросы

Примеры

Вход

3 1
1 0 5
1 2 3
2 3

Выход

8