Есеп A. Бауыржан және Ұлы Сандар Тауы

Бауыржан таңертең серуендегенді ұнатады, сол себепті күн шыққанда Ұлы Сандар тауына барды. Ол өзімен бірге $N$ элементтен тұратын сүйікті массивін алып келді, мұнда $i$-ші саны $a_i$-ға тең. Бауыржан өз массивіне тамаша сан тапқысы келеді. Егер барлық $1 <= i < j <= N$ үшін ЕҮОБ$(a_i+x,a_j+x)=1$ орындалса, $x$ саны ұлы болып саналады. Таудағы сандар $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 балмұздақ сатып алады, ал қалғандары бір бірден алады. Барлығы 6 балмұздақ сатылады. Әр балмұздақтан келетін табыс $5$($7 - 2$) теңге, онда барлығы $6 \cdot 5 = 30$ теңге пайда болады.

Есеп C. Жалпы аудан

Альтаирге жиі қызықты сыйлықтар беріледі. Бұл жолы Ариф оған ұшақта әртүрлі нүктелер жиынын берді, әрине ол Арифке алғыс айтты. Бірақ ол бұл нүктелермен не істеу керектігін мүлде білмейді, сондықтан ол есеп ойлап тапты. Альтаир $S$ жиынындағы барлық нүктелерді қамтитын, жақтары координат осьтеріне параллель, ең кішкентай тіктөртбұрыштың ауданын есептейтін $f(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$.