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

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

Даны два массива целых чисел длинны $n$. Даются $q$ запросов. Каждый запрос состоит из чисел $l$ и $r$, после каждого запроса требуется вывести чему равна сумма квадратов разностей чисел $a[i]$ и $b[i]$ где $i$= $l$, $l$+1,.., $r$.

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

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

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

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

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

Примеры

Вход

3 1
1 0 5
1 2 3
2 3

Выход

8