В школе магии инновационного города Глинополис на уроках теоретической информатики проходят множество интересных объектов.
Рассмотрим, например, магическое мультимножество. Если попробовать добавить в него число, которое уже присутствует во множестве, мультимножество раздваивается. Например, при добавлении в мультимножество \(\{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\).
Выходные данные
Для каждого запроса второго типа выведите сумму размеров мультимножеств на отрезке.
Так как ответы могут быть слишком большими, выводите их по модулю \(998244353\).
Примечание
В первом примере после первых двух запросов мультимножества равны \([\{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\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 1 2 1
1 1 2 2
1 1 4 1
2 1 4
|
10
|
|
2
|
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
|