В результате неудачного стечения обстоятельств Миша оказался на необитаемом острове. Первым делом он, разумеется, выложил из камней большую надпись S.O.S. на пляже. Однако, до прибытия помощи ему нужно чем-то развлечься, поэтому он решил поиграть с оставшимся камнями.
Миша выложил все оставшиеся у него камни в $$$n$$$ кучек таким образом, что в $$$i$$$-й кучке оказалось ровно $$$r_i$$$ камней. После этого мальчик решил взять из каждой кучки некоторое количество камней, чтобы были выполнены следующие условия:
- Из $$$i$$$-й кучки Миша должен взять не менее, чем $$$l_i$$$ и не более, чем $$$r_i$$$ камней;
- Суммарное количество взятых камней должно быть равно $$$s$$$.
После того, как Миша справился с данным заданием он задумался, сколькими способами он может взять камни из кучек таким образом, чтобы описанные условия были выполнены. А именно, для каждой кучки $$$i$$$ он хочет вычислить, сколькими способами он может выбрать некоторое количество камней из $$$i$$$-й кучки, чтобы из остальных кучек можно было выбрать некоторое количество камней, выполнив описанные условия.
К сожалению или к счастью, помощь прибыла слишком быстро, и Миша не успел найти ответ на свой вопрос. Поэтому сделать это предстоит вам.
Первая строка содержит два целых числа $$$n$$$ и $$$s$$$ ($$$1 \le n \le 100\,000$$$, $$$0 \le s \le 10^{18}$$$) — количество кучек с камнями, а также суммарное количество камней, взятых из кучек.
Каждая из следующих $$$n$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \le l_i \le r_i \le 10^9$$$) — минимальное и максимальное количество камней, которые Миша может взять из $$$i$$$-й кучки.
Обратите внимание, что входные данные в этой задаче могут превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Выведите $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$, обозначающих количество способов выбрать некоторое количество камней из $$$i$$$-й кучки, чтобы существовала возможность взять некоторое количество камней из остальных кучек, чтобы выполнить поставленные условия.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Обозначим за $$$m$$$ максимальную разность между $$$r_i$$$ и $$$l_i$$$. Иными словами, $$$m = \max \limits_{i=1}^{n} (r_i - l_i)$$$.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | 0 | Тесты из условия | полная | |
| 1 | 10 | $$$n, m \le 7$$$ | первая ошибка | |
| 2 | 15 | $$$n, m \le 1\,000$$$ | 1 | первая ошибка |
| 3 | 20 | $$$n \le 1\,000$$$ | 1, 2 | первая ошибка |
| 4 | 25 | $$$n \cdot m \le 10^7$$$ | 1, 2 | первая ошибка |
| 5 | 30 | нет | 1, 2, 3, 4 | первая ошибка |
5 101 32 33 30 101 1
3 2 1 4 1
Рассмотрим пример из условия.
Из первой кучки можно выбрать $$$1$$$, $$$2$$$ или $$$3$$$ камня. Для каждого из этих способов из остальных кучек можно выбрать некоторое количество камней таким образом, чтобы суммарно было выбрано $$$10$$$ камней. Например, можно сделать это следующими способами: $$$1 + 2 + 3 + 3 + 1 = 10$$$, $$$2 + 2 + 3 + 2 + 1 = 10$$$, $$$3 + 2 + 3 + 1 + 1 = 10$$$.
Из второй кучки можно выбрать $$$2$$$ или $$$3$$$ камня, например, следующими способами: $$$1 + 2 + 3 + 3 + 1 = 10$$$, $$$1 + 3 + 3 + 2 + 1 = 10$$$.
Из третьей кучки можно выбрать $$$3$$$ камня. Других способов нет, так как $$$l_3 = r_3 = 3$$$.
Из четвертой кучки можно выбрать $$$0$$$, $$$1$$$, $$$2$$$ или $$$3$$$ камня. Способы для выбора $$$1$$$, $$$2$$$ или $$$3$$$ камней уже описаны выше. Способ для $$$0$$$ камней выглядит следующим образом: $$$3 + 3 + 3 + 0 + 1 = 10$$$.
Из третьей кучки можно выбрать $$$1$$$ камень. Других способов нет, так как $$$l_5 = r_5 = 1$$$.
| Name |
|---|