Знайдіть суми

Це задача з градерами.

Вам дано масив $a$ з $n$ цілих чисел. Також вам дано $q$ запитів у форматі $(l,r)$, що означає, що вам потрібно знайти суму усіх чисел $a_l,a_{l+1},\dots ,a_r$.

Вам потрібно реалізувати наступні функції:

void init(integer n, array of integers a)

• $n$ — ціле число, яке позначає довжину масиву;

• $a$ — масив цілих чисел довжиною $n$;

• ця функція нічого не повертає.

integer ask(integer l, integer r)

• $l$ — ціле число, яке позначає ліву межу запиту;

• $r$ — ціле число, яке позначає праву межу запиту;

• ця функція повертає ціле число — суму усіх чисел на відрізку.

array of integers askAll(integer q, array of integers l, array of integers r)

• $q$ — ціле число, яке позначає кількість запитів;

• $l$ — масив цілих чисел довжиною $q$; $l_i$ позначає ліву межу $i$-го запиту;

• $r$ — масив цілих чисел довжиною $q$; $r_i$ позначає праву межу $i$-го запиту;

• ця функція повертає масив цілих чисел; $i$-те число має бути відповіддю на $i$-й запит.

Input

Перший рядок містить три цілі числа $n$, $q$, $t$ ($1\le n\le 100$; $1\le q\le 100$; $1\le t\le 2$) — кількість чисел, кількість запитів та формат запитів.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 100$) — числа масиву.

Кожен з наступних $q$ рядків містить по два цілі числа $l$ та $r$ ($1\le l\le r\le n$) — межі $i$-го запиту.

Спочатку викличеться функція init рівно один раз.

Якщо $t=1$, то викличеться рівно один раз функція askAll з усіма запитати. Якщо $t=2$, то функція ask викличеться рівно $q$ разів.

Output

Градер виведе $q$ цілих чисел — відповіді на кожен запит.

Examples

Scoring

1. ($50$ балів): $t=1$;

2. ($50$ балів): $t=2$.