J. Цветочный магазин
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваша подруга является владельцем цветочного магазина. Чтобы подготовиться к следующим праздникам (когда, как обычно, продажи взлетят до небес), она попросила вас написать ей специальную программу, которая поможет проанализировать имеющиеся у нее запасы.

Есть $$$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$$$. Для простоты можно представить, что букет — это мультисет цветов, а два букета различны, если они различны как мультисеты. Стоимость букета — это сумма всех цветов, которые в нем есть.

Помогите своей подруге и напишите программу, которая сможет обрабатывать все эти запросы.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 1000$$$; $$$1 \le m \le 1000$$$) — количество типов цветов и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 1000$$$) — стоимость одного цветка каждого типа.

Следующие $$$m$$$ строк содержат запросы — по одному на строке. Каждый запрос имеет один из трех типов:

  • $$$1$$$ $$$i$$$ $$$c$$$ ($$$1 \le i \le n$$$; $$$1 \le c \le 5000$$$);
  • $$$2$$$ $$$i$$$ $$$c$$$ ($$$1 \le i \le n$$$; $$$1 \le c \le 5000$$$). Гарантируется, что в этот момент есть по крайней мере $$$c$$$ цветов типа $$$i$$$;
  • $$$3$$$ $$$l$$$ $$$r$$$ $$$k$$$ ($$$1 \le l \le r \le n$$$; $$$1 \le k \le 5000$$$)

Гарантируется, что общая стоимость всех цветов в магазине после каждого запроса не превышает $$$5000$$$.

Выходные данные

Для каждого запроса третьего типа выведите, сколько вариантов букетов можно составить, используя только цветы типов $$$l, l + 1, \dots, r$$$ со стоимостью не более $$$k$$$. Поскольку ответ может быть слишком большим, выведите его по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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