Пастбище Фермера Джона можно рассматривать решётку из квадратных ячеек размером n * m (как большая шахматная доска). Ячейка в строке x сверху в колонке y обозначается как (x, y) для каждого x ∈ [1, n], y ∈ [1, m]. Далее для каждого y ∈ [1, m], y-ая колонка ассоциируется со стоимостью cy (1 ≤ cy ≤ 109).

Беси начинает в ячейке (1, 1). Если она находится в ячейке (x, y), то может выполнить одно из следующих действий:

• Если y < m, Беси может переместиться в следующую колонку (увеличивая y на 1) за цену x2.
• Если x < n, Беси может переместиться в следующую строку (увеличивая x на 1) за цену cy.

Вам даются q независимых запросов, каждый в виде (xi, yi) (xi ∈ [1, n], yi ∈ [1, m]), вычислите минимально возможную цену для Беси переместиться из (1, 1) в (xi, yi). Вычислите минимально возможную сумму.

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

Первая строка содержит n и m (2 ≤ n ≤ 109, 2 ≤ m ≤ 2 * 105).

Вторая строка содержит m целых чисел c1, c2, ..., cm.

Третья строка содержит q (1 ≤ q ≤ 2 * 105).

Каждая из последующих q строк содержит два целых числа xi и yi.

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

Выведите q строк, содержащих ответы на каждый запрос.

Заметим, что ответ требует использования 64-битного целого, например "long long" в C/C++).

Пример

Этот же вывод в формате решётки:

    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|
  *--*--*--*--*