Задача A. Баука и Гора Великих Чисел

Баука любит прогуливаться по утрам, из-за этого с восходом солнца он пошел на гору Великих Чисел. С собой он взял любимый массив из $N$ элементов, где $i$-е число равно $a_i$. Баука хочет найти великое число для своего массива. Число $x$ считается великим, если для него выполняется такое условие, что НОД$(a_i+x,a_j+x)=1$ для всех $1 <= i < j <= N$. Числа на горе представлены в виде $Q$ запросов. В каждом запросе дается одно число. Помогите Бауке определить, будет ли данное число великим для его массива. В первой строке находятся два целых числа $N$ и $Q$ ($2 <= N <= 10^5,1 <= Q <= 10^4$) - количество чисел и запросов. Во второй строке находятся $N$ целых числа $a_1, a_2, \cdots, a_n$ ($1 <= a_i <= 10^5$). В следующих $Q$ строках дано по одному целому числу $x$ ($1 <= x <= 10^5$). На каждый из $Q$ запросов выведите <>, если число является великим, иначе выведите <>.

Пример:

Вход

5 2
1 13 4 7 9
4
11

Ответ

YES
NO

Замечание

Рассмотрим первый запрос. После того как мы добавим 4 к каждому числу у нас получится массив: 5 17 8 11 13. Если мы возьмем НОД(Наибольший общий делитель) каждой пары из полученного массива то он не превысит 1, значит ответ YES. Во втором запросе нужно добавить к изначальному массиву число 11. В полученном массиве первое число будет равно 12, второе 24. НОД(12, 24) = 12, отсюда следует что ответ NO.

Задача B. Цена за мороженное

Вы продаете мороженное. Себестоимость одного мороженного $k$ тенге. Это значит, что если вы продаете одно мороженное по $x$ тенге, тогда прибыль с одного мороженного будет $x - k$ тенге. Есть $n$ клиентов, для каждого клиента $i$ известно максимальная сумма денег $s_i$ тенге, которую он готов потратить на мороженное. Каждый клиент купить столько мороженного, сколько сможет купить. Выберите цену мороженного таким образом, чтобы максимизировать суммарную прибыль. В первой строке находятся два целых числа $n,k$($1 <= n <= 2 \cdot 10^5$, $0 <= k <= 10^6$) — количество клиентов и себестоимость одного мороженного. Во второй строке находятся $n$ целых числа $s_1, s_2, \cdots, s_n$($1 <= s_i <= 10^6$). Выведите максимальную возможную прибыль. Вход

5 2
8 9 10 15 12

Ответ

30

Вход

3 20
15 10 20

Ответ

0

В первом примере одно мороженное выгодно продавать по $7$ тенге. Тогда четвертый клиент купить 2 мороженное, а остальные 4 по одному. Всего продадим 6 мороженных. Прибыль с одного мороженного $5$($7 - 2$) тенге, тогда суммарная прибыль $6 \cdot 5 = 30$ тенге.

Задача C. Суммарная площадь

Альтаиру часто дарят интересные подарки. На этот раз Ариф подарил множество различных точек на плоскости, он конечно поблагодарил Арифа. Но он совсем не знает что делать с этими точками, поэтому он придумал задачу. Альтаир определил функцию $f(S)$, которая считает площадь минимального прямоугольника со сторонами параллельными осям координат, который покрывает все точки из множества $S$ (точка покрыта прямоугольником, когда находится внутри него или на его границе). Но подсчет такой функции кажется ему чем-то слишком простым и скучным, поэтому он хочет посчитать сумму значений функции $f$ по всем возможным непустым подмножествам точек. Так как Альтаир не умеет использовать большие числа, а ответ может быть уж слишком большим, поэтому нужно посчитать его остаток при делении на $10^9 + 7$. В первой строке дано одно натуральное число $n$ ($1 <= n <= 10^5$) — количество точек в подарке. Далее следуют $n$ строк, в $i$-й записана пара чисел $x_i$, $y_i$ ($1 <= x_i, y_i <= 10^9$) — координаты $i$-й точки. Выведите одно число - ответ на задачу по модулю $10^9 + 7$. Вход

3
4 10
5 7
7 9

Ответ

19

Рассмотрим пример. В этом примере есть 7 непустых подмножеств. Площадь прямоугольника для подножества из первой и второй точки: $f(\{1, 2\}) = 3$. $f(\{1\}) = f(\{2\}) = f(\{3\}) = 0$ $f(\{1, 2\}) = 3$ $f(\{1, 3\}) = 3$ $f(\{2, 3\}) = 4$ $f(\{1, 2, 3\}) = 9$ Сумма по всем $f(S)$ -- $19$.