Ваша подруга является владельцем цветочного магазина. Чтобы подготовиться к следующим праздникам (когда, как обычно, продажи взлетят до небес), она попросила вас написать ей специальную программу, которая поможет проанализировать имеющиеся у нее запасы.
Есть \(n\) различных типов цветов, которые она может заказать, и каждый цветок типа \(i\) стоит \(w_i\). Последние праздники прошли с большим успехом, она продала все цветы, которые у нее были, так что сейчас все ее запасы пусты.
С этого момента она начинает рутинные операции по заказу и продаже цветов, одновременно пытаясь проанализировать, что у нее есть под рукой. Все это можно представить в виде \(m\) запросов трех типов:
- «\(1\) \(i\) \(c\)» — она купила \(c\) цветов типа \(i\);
- «\(2\) \(i\) \(c\)» — она продала \(c\) цветов типа \(i\);
- «\(3\) \(l\) \(r\) \(k\)» — сколько вариантов букетов она может составить, используя только цветы типов \(l, l + 1, \dots, r\) со стоимостью не более \(k\). Для простоты можно представить, что букет — это мультисет цветов, а два букета различны, если они различны как мультисеты. Стоимость букета — это сумма всех цветов, которые в нем есть.
Помогите своей подруге и напишите программу, которая сможет обрабатывать все эти запросы.
Выходные данные
Для каждого запроса третьего типа выведите, сколько вариантов букетов можно составить, используя только цветы типов \(l, l + 1, \dots, r\) со стоимостью не более \(k\). Поскольку ответ может быть слишком большим, выведите его по модулю \(998\,244\,353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 12
1 2 3 2 1
1 1 5
1 2 3
1 3 1
3 1 5 10
3 4 5 100
1 4 4
1 5 1
3 2 5 7
3 1 1 3
3 1 5 100
2 1 5
3 1 5 100
|
40
0
28
3
479
79
|