\textit{Автор задачи и разработчик: Павел Скобелин}
\vspace{0.2em}

Будем решать задачу в \texttt{offline}. Для начала отсортируем запросы по увеличению умения работать в команде. Заметим, что если какой-то из обитателей имеет умение работать в команде меньшее, чем нужно~--- в таком случае он не сможет помочь ни в текущем запросе, ни в одном из следующих. Значит, алгоритм такой: пока умение работать в команде у $i$-го обитателя меньше, чем нужно в запросе, давайте увеличивать умение его работать в команде с помощью особого трюка. Несложно показать, что суммарно таких изменений произойдет не очень много: ведь если $c_i>1$, то таких изменений произойдет не более $\log M$, а если $c_i=1$, человек по сути имеет бесконечный скилл работы в команде. 

Тогда давайте поддерживать текущие умы обитателей в дереве отрезков: в точке $x_i$ будет содержаться текущий ум человека номер $i$. Тогда, отвечать на запросы можно с помощью бинарного поиска по ответу: нужно проверить, что сумма умов обитателей на отрезке $[y_j - mid; y_j + mid]$ хотя бы $s_j$. 

Можно реализовать этот алгоритм с помощью неявного дерева отрезков. Но, если воспользоваться техникой сжатия координат, то невность не пригодится~--- и можно будет даже использовать дерево Фенвика для более быстрого ответа на запросы, но для полного решения задачи это не требовалось.

Итоговая асимптотика $\mathcal{O}(n \log M \log n + q \log^2 n)$