У Аделины есть сад, в котором растут $$$w$$$ белых и $$$r$$$ красных роз. Девушка хочет собрать букет из цветов, но у нее есть несколько условий:

1. В букете должно быть нечетное количество красных роз;
2. Букет должен содержать не менее чем $$$k$$$ роз.

Определите, сможет ли Аделина собрать букет, удовлетворяющий всем условиям.

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

После того, как Миша и Егор целый день играли в одну небезызвестную компьютерную игру, они решили как следует отдохнуть. Для этого они решили сыграть в «Очередную игру на прямой».

Суть этой игры очень проста — есть бесконечная полоска, разделенная на клетки, все клетки которой пронумерованы целыми числами слева направо. Также есть $$$n$$$ подарков, которые лежат в некоторых клетках полоски. Известно, что $$$i$$$-й подарок находится в клетке с номером $$$a_i$$$.

Сначала Миша ставит свою фишку в произвольную клетку. После этого Егор ставит свою фишку в любую клетку, но ему запрещается выбирать ту же клетку, которую выбрал Миша. Затем начинается сама игра. Игроки ходят по очереди, первым ходит Миша. В свой ход игрок может подвинуть свою фишку на одну клетку влево или вправо. Если фишка игрока оказывается в клетке, в которой находится подарок, игрок забирает подарок себе. Цель каждого из игроков — максимизировать количество подарков, которые он заберет. Если игрок изначально ставит свою фишку в клетку с подарком, то он сразу же забирает этот подарок.

Миша и Егор не новички в данной игре, поэтому они знают, что в этой игре существует выигрышная стратегия. Но они ушли спать, поэтому вам придется выяснить, в какую клетку нужно изначально положить фишку Мише, чтобы максимизировать количество подарков, которые он сможет забрать, при условии, что оба игрока играют оптимально и стремятся максимизировать свой выигрыш.

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Вы уснули на уроке, и вам приснился кошмар — на муниципальный этап ВсОШ по информатике дали задачу на геометрию...

Даны $$$a$$$ прямых, образующих угол $$$0^{\circ}$$$ с осью $$$OX$$$, $$$b$$$ прямых, образующих угол $$$60^{\circ}$$$ с осью $$$OX$$$, а также $$$c$$$ прямых, образующих угол $$$120^{\circ}$$$ с осью $$$OX$$$. Здесь имеются ввиду углы между прямой и положительным направлением оси $$$OX$$$. Если изобразить все прямые на одном рисунке, на нем образуется много треугольников. Легко заметить, что все треугольники являются равносторонними.

Вы не можете проснуться, пока не вычислите количество различных равносторонних треугольников, образовавшихся на рисунке.

Два треугольника считаются различными, если различаются тройки прямых, при помощи которых данные треугольники были образованы. Более формально, пусть $$$(i_1, j_1, k_1)$$$ — номера прямых, образующих первый треугольник, а $$$(i_2, j_2, k_2)$$$ — номера прямых, образующих второй треугольник ($$$1 \le i_1, i_2 \le a$$$, $$$1 \le j_1, j_2 \le b$$$, $$$1 \le k_1, k_2 \le c$$$). Данные треугольники считаются различными, если $$$i_1 \ne i_2$$$ или $$$j_1 \ne j_2$$$ или $$$k_1 \ne k_2$$$.

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Кирилл — маленький зеленый монстрик, который очень любит читать книги. Именно поэтому он поступил в низший университет литературы. Домашнее задание Кирилла было очень простым — ему задали прочитать $$$n$$$ книг, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Известно, что в $$$i$$$-й книге было $$$a_i$$$ страниц. Кирилл должен читать книги именно в том порядке, в котором ему их выдали. Иными словами, он должен сначала прочитать книгу с номером $$$1$$$, затем прочитать книгу с номером $$$2$$$, и так далее.

На это задание Кириллу было отведено ровно $$$m$$$ дней, пронумерованных целыми числами от $$$1$$$ до $$$m$$$. При этом в $$$i$$$-й день он может прочитать только $$$b_i$$$ страниц. Таким образом, в каждый из этих $$$m$$$ дней (сначала в день с номером $$$1$$$, затем в день с номером $$$2$$$, и так далее) Кирилл будет выполнять задание и читать книги. За каждый из $$$m$$$ дней Кирилл может прочитать некоторое (возможно, нулевое) количество книг, соблюдая порядок их прочтения. Разумеется, Кирилл не будет читать одну и ту же книгу дважды.

Кирилл, конечно, умный монстрик, но у него есть одна серьезная проблема — если в какой-то день он не дочитает книгу до конца, то за ночь он все забудет, и на следующий день придется читать ее с самого начала. Также у Кирилла есть $$$k$$$ банок вишневого сока. Если в $$$i$$$-й день мальчик выпивает банку вишневого сока, то он может прочитать дополнительно $$$x$$$ страниц. При этом врач запретил ему пить в день более одной банки, так как это негативно скажется на его здоровье.

Как вы уже поняли, Кирилл поступил в университет литературы, а не программирования, поэтому вам придется посчитать, какое максимальное количество книг он сможет прочитать.

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Саша очень любит комбинаторные задачи, а также он является главным фанатом задачи «Хорошие раскраски», которая появилась на региональном этапе ВсОШ по информатике несколько лет назад. Более того, Саша очень любит играть со спичками. Поэтому мальчик решил придумать свою задачу о хороших раскрасках и порадовать вас своим творением.

Саша выложил в ряд на столе $$$n$$$ квадратов, состоящих из спичек. На рисунке ниже приведен пример получившейся фигуры для $$$n = 3$$$. Можно заметить, что фигура, состоящая из $$$n$$$ квадратов, содержит в себе $$$3n + 1$$$ спичек.

Назовем две спички соседними, если они касаются в углу некоторого квадрата. Например, на рисунке ниже спички, окрашенные синим цветом, являются попарно соседними.

У Саши в распоряжении есть краски $$$k$$$ различных цветов, и, разумеется, он хочет окрасить каждую спичку выложенной фигуры в некоторый цвет. Саша считает раскраску спичек хорошей, если никакие две соседние спички не окрашены в один цвет.

Будучи любителем комбинаторных задач, Саша задумался, сколько существует различных хороших раскрасок спичек. Помогите Саше решить данную тривиальную задачу. Так как ответ может быть достаточно большим, вам необходимо вычислить остаток от деления количества хороших раскрасок на число $$$998\,244\,353$$$.