H. Рандомный Шард
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Метаданные пользователей Яндекс.Почты лежат в БД PostgreSQL и разбиты на $$$N$$$ шардов (теоретически $$$N$$$ может быть очень большим). У каждого шарда есть вес, который постоянно пересчитывается пропорционально загрузке процессора на мастере шарда. Новому пользователю при регистрации автоматически присваивается шард рандомно с учётом веса этого шарда. Нужно реализовать класс который хранит веса шардов и отвечает на следующие типы запросов:

  1. Обновить вес какого-то шарда.
  2. Получить по заданному $$$weight$$$ номер шарда $$$i$$$ такого, что сумма весов шардов c номерами, находящимися на отрезке $$$[0, i]$$$ меньше или равна заданному весу, а сумма весов шардов c номерами, находящимися на отрезке $$$[0, i + 1]$$$ строго больше. Если сумма весов всех шардов не превосходит заданный вес, нужно вывести $$$n - 1$$$. Если вес нулевого шарда больше, чем $$$weight$$$, то надо вывести $$$-1$$$.
Входные данные

Первая строка содержит два целых числа $$$n$$$ ($$$1 \le n \le 10^6$$$) — количество шардов (шарды нумеруются с 0); $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.

Каждая из следующих $$$q$$$ строк содержит запрос. Запрос описан в одном из форматов:

  • $$$+\ shard\ weight\ (0 \le shard \lt n, 1 \le weight \le 10 ^ 7)$$$ — означает, что надо увеличить вес шарда с номером $$$shard$$$ на $$$weight$$$ единиц.
  • $$$?\ weight\ (0 \le weight \le 10^{15})$$$ — означает, что надо отдать номер шарда $$$i$$$ который удовлетворяет следующему условию: сумма весов шардов c номерами, находящимися на отрезке $$$[0, i]$$$, не превосходит $$$weight$$$, а сумма весов шардов c номерами, находящимися на отрезке $$$[0, i + 1]$$$, превосходит $$$weight$$$. При этом если сумма весов всех шардов не превосходит $$$weight$$$, то надо вывести $$$n - 1$$$. Если вес нулевого шарда больше, чем $$$weight$$$, то надо вывести $$$-1$$$.
Выходные данные

Для каждого запроса формата 2 выведите номер шарда, который удовлетворяет условию, описанному выше.

Пример
Входные данные
1 5
+ 0 2
+ 0 1
+ 0 3
? 6
? 5
Выходные данные
0
-1