Мияко приехала в гости в страну блох с укулеле. Она подружилась с блохами и исполняла им прекрасную музыку каждый день.
В благодарность за это блохи изготовили для нее большое укулеле: всего не нем \(n\) струн, на каждой струне \((10^{18} + 1)\) лад, лады пронумерованы от \(0\) до \(10^{18}\). Блохи описывают это укулеле массивом \(s_1, s_2, \ldots, s_n\), что означает, что \(j\)-й лад на \(i\)-й струне издает ноту \(s_i + j\).
Мияко скоро уедет из страны блох, но те попросили ее ответить на несколько вопросов.
Каждый вопрос имеет следующий вид: «Сколько всего различных нот находятся на ладах с \(l\)-го по \(r\)-й (включительно), если рассматривать все струны?»
У Мияко нет времени отвечать на вопросы. Найдите ответы, чтобы помочь ей!
Формально, дана таблица из \(n\) строк и \((10^{18}+1)\) столбцов, где в ячейке в \(i\)-м ряду в \(j\)-м столбце (\(0 \le j \le 10^{18}\)) написано число \(s_i + j\). Вам нужно ответить на \(q\) запросов, в \(k\)-м запросе нужно вычислить число различных чисел в таблице в столбцах с \(l_k\)-го по \(r_k\)-й, включительно.
Выходные данные
Выведите одно целое число для каждого вопросы: число различных нот.
Примечание
В первом примере ноты на \(6\) струнах выглядят так: \(\) \begin{matrix} \textbf{Лад} & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \ldots \\ s_1: & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\ s_2: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_3: & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & \dots \\ s_4: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_5: & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \dots \\ s_6: & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & \dots \end{matrix} \(\)
На ладу \(7\) есть \(5\) различных нот: \(8, 10, 11, 12, 16\).
На ладах \(0, 1, 2\) есть \(10\) различных нот: \(1, 2, 3, 4, 5, 6, 7, 9, 10, 11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 1 4 1 5 9
3
7 7
0 2
8 17
|
5 10 18
|
|
2
|
2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000
|
2 1500000000000000000
|