F1. Рождественские олени (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственное различие между простой и сложной версией в ограничениях на $$$n$$$ и $$$m$$$. В этой версии $$$n \le 500$$$ и $$$m \le 500$$$.

У вас есть стадо из $$$n$$$ рождественских оленей. Сила $$$i$$$-го оленя равна $$$2^{c_i}$$$.

Грузоподъемность группы из $$$k$$$ оленей рассчитывается следующим образом:

  • силы оленей сортируются в порядке невозрастания. Обозначим отсортированный список сил оленей как $$$c'_1, c'_2, \dots, c'_k$$$, где $$$c'_i \ge c'_{i+1}$$$;
  • грузоподъемность группы оленей равна $$$c'_1 + \lfloor\frac{c'_2}{2}\rfloor + \lfloor\frac{c'_3}{4}\rfloor + \dots + \lfloor\frac{c'_k}{2^{k - 1}}\rfloor$$$.

Обратите внимание, что некоторые олени могут не вносить вклад в грузоподъемность группы.

Вам необходимо обработать запросы трех типов:

  1. добавить оленя с силой $$$2^x$$$ в стадо;
  2. удалить оленя с силой $$$2^x$$$ из стада;
  3. вычислить количество способов выбрать некоторых оленей из стада (возможно, всех) так, чтобы грузоподъемность выбранной группы была не менее $$$x$$$.

Если в стаде есть несколько оленей с одинаковой силой, они считаются разными. Например, если у вас есть два оленя с силой $$$1$$$ каждый, и вам нужно вычислить количество способов выбрать группу с грузоподъемностью не менее $$$1$$$, существует $$$3$$$ способа выбрать ее: выбрать первого оленя, второго оленя или обоих.

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 60$$$), обозначающих силы оленей в стаде: сила $$$i$$$-го оленя равна $$$2^{c_i}$$$.

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

  • $$$1$$$ $$$x$$$ ($$$0 \le x \le 60$$$) — добавить оленя с силой $$$2^x$$$ в стадо;
  • $$$2$$$ $$$x$$$ ($$$0 \le x \le 60$$$) — удалить оленя с силой $$$2^x$$$ из стада;
  • $$$3$$$ $$$x$$$ ($$$1 \le x \le 10^{18}$$$) — вычислить количество способов выбрать группу оленей из стада так, чтобы грузоподъемность выбранной группы была не менее $$$x$$$.

Дополнительное ограничение на входные данные: каждый раз, когда поступает запрос типа $$$2$$$, в стаде в данный момент есть как минимум один олень с силой $$$2^x$$$.

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

Для каждого запроса третьего типа выведите одно целое число — количество способов выбрать группу оленей из стада (возможно, все стадо) так, чтобы грузоподъемность выбранной группы была не менее $$$x$$$. Поскольку это число может быть огромным, выведите его по модулю $$$998244353$$$.

Примеры
Входные данные
3 7
2 1 1
3 5
3 6
1 2
3 6
3 5
2 1
3 5
Выходные данные
3
0
4
10
4
Входные данные
5 5
6 9 2 3 5
3 518
1 4
2 9
1 10
3 1016
Выходные данные
12
32
Входные данные
5 20
56 58 31 56 57
3 584133699915613698
1 26
3 718934517698133644
1 43
3 853795525565803934
3 371128907885602007
1 54
1 25
3 12283451778216771
2 25
3 269837405423769340
1 0
3 81332884431075468
1 23
3 4256984962444022
3 668408003982766102
3 923410222653374550
3 340313743235311415
3 550166282440775769
3 445344499963496530
Выходные данные
0
0
0
24
496
128
416
992
0
0
320
0
0
Примечание

Рассмотрим первый пример. Изначально в стаде три оленя с силами $$$4$$$, $$$2$$$ и $$$2$$$ соответственно.

  • во время первого запроса вам нужно вычислить количество способов выбрать группу с грузоподъемностью не менее $$$5$$$. Существует три возможные группы: $$$\{1, 2\}$$$ (группа, содержащая $$$1$$$-го и $$$2$$$-го оленей), $$$\{1, 2, 3\}$$$ и $$$\{1, 3\}$$$;
  • во время второго запроса вам нужно вычислить количество способов выбрать группу с грузоподъемностью не менее $$$6$$$. Даже все стадо имеет грузоподъемность $$$4 + \lfloor\frac{2}{2}\rfloor + \lfloor\frac{2}{4}\rfloor = 5$$$, так что подходящих способов выбрать группу нет;
  • во время третьего запроса добавляется олень с силой $$$4$$$. Будем считать, что это $$$4$$$-й олень;
  • во время четвертого запроса возможные группы: $$$\{1, 4\}$$$, $$$\{1, 2, 4\}$$$, $$$\{1, 3, 4\}$$$ и $$$\{1, 2, 3, 4\}$$$;
  • во время пятого запроса существует $$$10$$$ возможных групп;
  • во время шестого запроса удаляется олень с силой $$$2$$$. Предположим, что это был $$$2$$$-й олень, так что остаются только олени $$$1, 3, 4$$$;
  • во время седьмого запроса вам нужно вычислить количество способов выбрать группу с грузоподъемностью не менее $$$5$$$. Существует четыре возможные группы: $$$\{1, 3\}$$$, $$$\{1, 4\}$$$, $$$\{1, 3, 4\}$$$, $$$\{3, 4\}$$$.