Рассмотрим отрезок \([0, d]\) координатной прямой. В этом отрезке \(n\) фонарей и \(m\) интересных точек.
Для каждого фонаря вы должны выбрать его мощность — целое число от \(0\) до \(d\) (включительно). Фонарь с координатой \(x\) освещает интересную точку с координатой \(y\), если \(|x - y|\) меньше либо равно мощности фонаря.
Способ выбрать мощности для всех фонарей является корректным, если каждая интересная точка освещена хотя бы одним фонарем.
Вам нужно обработать \(q\) запросов. Каждый запрос обозначается одним целым числом \(f_i\). Чтобы ответить на \(i\)-й запрос, вам нужно:
- добавить фонарь в точку \(f_i\);
- посчитать количество корректных способов назначить мощность каждому фонарю, и вывести это количество по модулю \(998244353\);
- удалить только что добавленный фонарь.
Выходные данные
Для каждого запроса выведите ответ на него по модулю \(998244353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 1 1
4
3
3
2 1 5
|
48
47
47
|
|
2
|
6 1 2
4
2 5
2
1 3
|
44
46
|
|
3
|
20 1 2
11
15 7
1
8
|
413
|
|
4
|
20 3 5
5 7 18
1 6 3 10 19
5
4 17 15 8 9
|
190431
187503
188085
189903
189708
|