Пасовище Фермера Джона можна розглядати як гартку із квадратних комірок розміром \(N\times M\) (\(2\le N\le 10^9\), \(2\le M\le 2\cdot 10^5\)) (як велика шахівниця). Коммірка у рядку \(x\) зверху в колонці \(y\) позначається як \((x,y)\) для кожного \(x\in [1,N], y\in [1,M]\). Далі для кожного \(y\in [1,M]\), \(y\)а колонка асоціюється з вартістю \(c_y\) (\(1\le c_y\le 10^9\)).

Бесі починає в комірці \((1,1)\). Якщо вона знаходиться в комірці \((x, y)\), вона може виконати одну з таких дій:

• Якщо \(y<M\), Бесі може переміститися в наступну колонку (збільшуючи \(y\) на 1) за ціну \(x^2\).
• Якщо \(x<N\), Бесі може переміститися в наступний рядок (збільшуючи \(x\) на 1) за ціну \(c_y\).

ВАМ даються \(Q\) (\(1\le Q\le 2\cdot 10^5\)) незалежних запитів, кожен у вигляді \((x_i,y_i)\) (\(x_i\in [1,N], y_i\in [1,M]\)), обчисліть мінімально можливу ціну для Бесі переміститися з \((1,1)\) \((x_i,y_i)\).

Формат вхідних даних

Перший рядок містить \(N\) та \(M\).

Другий рядок містить \(M\) розділених пробілом цілих чисел \(c_1,c_2,\ldots,c_M\).

Третій рядок містить \(Q\).

Кожен із наступних \(Q\) рядків містить два цілих числа \(x_i\) і \(y_i\).

Формат вихідних даних

\(Q\) рядків, що містять відповіді на кожен запит.

Зауважимо, що відповідь вимагає використання 64-бітового цілого, наприклад "long long" C/C++).

Приклад вхідних даних

5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4

Приклад вихідних даних

0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69

Цей самий висновок у форматі гратки:

    1  2  3  4
  *--*--*--*--*
1 | 0| 1| 2| 3|
  *--*--*--*--*
2 | 1| 5| 9|13|
  *--*--*--*--*
3 | 2|11|20|29|
  *--*--*--*--*
4 | 3|19|35|49|
  *--*--*--*--*
5 | 4|29|54|69|
  *--*--*--*--*

ОЦІНЮВАННЯ:

• У тестах 1-3 \(N,M\le 2000\).
• У тестах 4-8 \(c_2>c_3>\cdots>c_M\).
• У тестах 9-15 \(N\le 2\cdot 10^5\).
• У тестах 16-20 немає додаткових обмежень.