G. Магические мультимножества
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В школе магии инновационного города Глинополис на уроках теоретической информатики проходят множество интересных объектов.

Рассмотрим, например, магическое мультимножество. Если попробовать добавить в него число, которое уже присутствует во множестве, мультимножество раздваивается. Например, при добавлении в мультимножество $$$\{1, 2, 3, 3\}$$$ элемента $$$2$$$, мультимножество превратится в $$$\{1, 1, 2, 2, 3, 3, 3, 3\}$$$.

Если же добавляемый элемент отсутствует во множестве, то он просто добавляется в мультимножество. Например, при добавлении в мультимножество $$$\{1, 2, 3, 3\}$$$ элемента $$$4$$$, мультимножество превратится в $$$\{1, 2, 3, 3, 4\}$$$.

Рассмотрим также массив из $$$n$$$ изначально пустых мультимножеств, пронумерованных от $$$1$$$ до $$$n$$$.

Вам требуется ответить на $$$q$$$ запросов вида «добавить ко всем мультимножествам с номерами $$$l, l + 1, \ldots, r$$$ число $$$x$$$» или «вычислить сумму размеров мультимножеств с номерами $$$l, l + 1, \ldots, r$$$». Так как ответы на запрос второго типа могут быть большими, выведите каждый из них по модулю $$$998244353$$$.

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

В первой строке расположены два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^{5}$$$) — число магических мультимножеств в массиве и количество запросов, соответственно.

Следующие $$$q$$$ строк описывают запросы по одному в строке. В каждой строке сначала записано целое число $$$t$$$ ($$$1 \leq t \leq 2$$$) — тип запроса. В случае, если $$$t$$$ равно $$$1$$$, далее даны три целых числа $$$l$$$, $$$r$$$, $$$x$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq x \leq n$$$), что обозначает, что вы должны добавить во всем мультимножества с номерами от $$$l$$$ до $$$r$$$ включительно число $$$x$$$. Если же $$$t$$$ равно $$$2$$$, то далее даны два целых числа $$$l$$$, $$$r$$$ ($$$1 \leq l \leq r \leq n$$$), что означает, что вы должны вычислить сумму размеров мультимножеств с номерами от $$$l$$$ до $$$r$$$ включительно.

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

Для каждого запроса второго типа выведите сумму размеров мультимножеств на отрезке.

Так как ответы могут быть слишком большими, выводите их по модулю $$$998244353$$$.

Примеры
Входные данные
4 4
1 1 2 1
1 1 2 2
1 1 4 1
2 1 4
Выходные данные
10
Входные данные
3 7
1 1 1 3
1 1 1 3
1 1 1 2
1 1 1 1
2 1 1
1 1 1 2
2 1 1
Выходные данные
4
8
Примечание

В первом примере после первых двух запросов мультимножества равны $$$[\{1, 2\},\{1, 2\},\{\},\{\}]$$$, а после третьего $$$[\{1, 1, 2, 2\},\{1, 1, 2, 2\},\{1\},\{1\}]$$$.

Во втором примере первое мультимножество проходит такой путь:

$$$\{\} \to \{3\} \to \{3, 3\} \to \{2, 3, 3\} \to \{1, 2, 3, 3\} \to \{1, 1, 2, 2, 3, 3, 3, 3\}$$$.