Boxlunch is on a map which can be modeled as an infinite grid of cells, with cell $$$(i,j)$$$ having value $$$i \times j$$$. Boxlunch starts at cell $$$(a,b)$$$ and is trying to reach cell $$$(n,m)$$$, where $$$n \ge a$$$ and $$$m \ge b$$$.

If Boxlunch is at cell $$$(x,y)$$$, he can either move to cell $$$(x+1, y)$$$ or $$$(x, y+1)$$$.

The total value of his path is the sum of the values of all cells he visits, including his starting and ending cells.

Find the maximum total value of a path he can take to reach cell $$$(n,m)$$$.

For a bitstring $$$s$$$ (meaning $$$s$$$ consists of 0s and 1s), we define $$$f(s)$$$ as the string obtained by replacing each 0 in $$$s$$$ with 001, and each 1 with 01. For example, $$$f(\texttt{001}) = \texttt{00100101}$$$, and $$$f(\texttt{111}) = \texttt{010101}$$$.

We write $$$f^x(s)$$$ to denote applying $$$f$$$ to some string $$$x$$$ times. For example, $$$f^5(s)$$$ means $$$f(f(f(f(f(s)))))$$$.

You are given a list of $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$. You need to find bitstrings $$$s$$$ and $$$t$$$ that satisfy all the following conditions:

• $$$s$$$ and $$$t$$$ have the same length.
• The length of $$$s$$$ and $$$t$$$ is between $$$1$$$ and $$$3 \cdot 10^5$$$ inclusive.
• $$$s$$$ and $$$t$$$ contain the same number of 0s, and the same number of 1s.
• Let $$$S = f^{22}(s)$$$ and $$$T = f^{22}(t)$$$. Then, $$$a$$$ is exactly the list of indices where $$$S$$$ and $$$T$$$ are different. Or more formally: for all $$$1 \leq j \leq |S|$$$, we have $$$S_j \neq T_j$$$ if and only if $$$j$$$ is an element of $$$a$$$.

Note that this last condition implies that all values $$$a_i$$$ must be less than or equal to the length of $$$S$$$ and $$$T$$$.

We guarantee that a solution exists in all tests. If there are multiple solutions, you can output any of them.

You are given a sequence of positive integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$.

A pair of integers $$$x, y$$$ is good if $$$\max(x, y) \lt x \oplus y$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

A set $$$S$$$ of integers counts if all its elements are unique, and all pairs of distinct integers in $$$S$$$ are good.

What is the largest subset of $$$a_1, a_2, \ldots, a_n$$$ that counts?

At X-Camp Academy, students don't just learn to code. In fact, coding is merely 5% of what X-Camp helps students to begin with. Instead, they spend most of their time learning to tackle challenges through algorithms and problem-solving. Many of the methodologies are used in the state-of-the-art research and development of artificial intelligence and other technology or science.

Today's task is straight out of a robotics competition: A fleet of $$$n$$$ autonomous delivery robots are standing in a line, where the $$$i$$$-th robot is currently at position $$$x = i$$$.

But a software bug means they will all be moving at the same speed! At time $$$t = 0$$$ seconds, all robots will start moving to the left (in the negative $$$x$$$ direction) at a constant speed of $$$1$$$ unit per second. If they keep going at this rate, they'll get to their destinations at the wrong time and disrupt the entire system. Fortunately, you have a specialized slow-motion gun that can selectively reduce their speed.

When you fire your slow-motion gun, all robots at positions $$$x \geq 0$$$ have their current speeds halved. You are only allowed to fire at positive integer times, i.e. when $$$t$$$ is an integer and $$$t \gt 0$$$. You are allowed to fire multiple times simultaneously.

You are also given an integer sequence $$$1 \leq a_1 \leq a_2 \leq \ldots \leq a_n$$$. Your goal is to fire the gun exactly $$$a_n$$$ times, so that for all $$$1 \leq i \leq n$$$, the $$$i$$$-th robot gets hit by the ray gun exactly $$$a_i$$$ times.

How many ways are there to achieve the goal? Two ways are different if you fire the gun a different number of times at time $$$t$$$, for some $$$t \gt 0$$$. We can show that the answer is finite, but it may be large, so output the remainder modulo $$$998\,244\,353$$$.

Lunchbox has two arrays $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$, each of length $$$n$$$. It is guaranteed that $$$a_i \leq b_i$$$ for each $$$1 \leq i \leq n$$$.

He is allowed to perform either of the following two operations in any order, as many times as he wants (possibly zero):

• If there are an even number of even elements in $$$a$$$, add a positive even number to any element in $$$a$$$.
• If there are an odd number of odd elements in $$$a$$$, add a positive odd number to any element in $$$a$$$.

Is it possible to turn $$$a$$$ into $$$b$$$?

Lacking the funds to fill the contest floor with argon, BAPC is looking for ways to raise money!

There are $$$n$$$ fundraising activities that BAPC can hold, conveniently numbered $$$1$$$ through $$$n$$$. Holding the $$$i$$$-th activity earns BAPC a profit of $$$a_i$$$ dollars (this number can be positive, zero, or even negative). Furthermore, each activity $$$2 \leq i \leq n$$$ has a prerequisite $$$r_i$$$  — meaning you cannot hold activity $$$i$$$ without also holding activity $$$r_i$$$.

Of course, BAPC wants to maximize their profits, so they will choose a subset of activities that earns the maximum possible profit. If there are multiple such subsets, they choose a subset with the maximum number of activities (gotta look busy!).

So, the subset of activities that BAPC holds can be described by two integers: the profit made, and the number of activities held. We'll call these the optimal profit, and the optimal number of activities respectively.

But now the fundraising team wants to spice things up a bit by changing some $$$a_i$$$ values. You are given $$$q$$$ queries you need to answer, of two types:

• Type $$$1$$$: given an integer $$$v_i$$$ and value $$$x_i$$$, increase the profit of activity $$$v_i$$$ by $$$x_i$$$  — in other words, do $$$a_{v_i} := a_{v_i} + x_i$$$. It is guaranteed that $$$x_i$$$ is positive.
• Type $$$2$$$: given an integer $$$v_i$$$, find the smallest positive integer $$$x_i$$$ such that increasing $$$a_{v_i}$$$ by $$$x_i$$$ will change either the optimal profit made, or the optimal number of activities held.

Type $$$1$$$ updates are persistent, meaning that changes made to $$$a_i$$$ remain in effect for future queries. Type $$$2$$$ updates do NOT change the values of $$$a_i$$$.

Little Bobby Tables loves playing with tables. More specifically, he has a collection of $$$m$$$-by-$$$m$$$ tables, where each cell is either empty or colored in.

For two tables $$$T_1$$$ and $$$T_2$$$, Bobby defines the composition of $$$T_1$$$ and $$$T_2$$$ (denoted $$$T_1 \circ T_2$$$) to be the grid obtained by replacing each colored-in cell in $$$T_1$$$ with a copy of $$$T_2$$$, and each blank cell with a $$$m$$$-by-$$$m$$$ blank grid.

Examples of grid composition.

Two tables $$$T_1$$$ and $$$T_2$$$ are called commutative if $$$T_1 \circ T_2 = T_2 \circ T_1$$$. For example, the two tables in the picture above are not commutative, but two empty tables would be commutative.

You are given Bobby's collection of $$$n$$$ tables $$$T_1, T_2, \ldots, T_n$$$. Count the number of pairs $$$1 \leq i \lt j \leq n$$$ where $$$T_i$$$ and $$$T_j$$$ are commutative.

The skew heap data structure can be represented as a root node storing an integer value, and pointers to its left and right children. Each child is either another node, or an empty heap. We work with a simplified version, as follows.

If we want to insert an integer $$$v$$$ into a heap $$$H$$$:

• If $$$H$$$ is empty, then set $$$H$$$ to a new node storing the value $$$v$$$, and no left or right children.
• Otherwise, swap the left and right children of the root. Then recursively insert $$$v$$$ into the left child of the root.

Farmer John loves inserting elements into skew heaps. Every afternoon, he starts with an empty skew heap $$$H$$$. For all $$$i = 1, 2, \ldots, n$$$ in sequence, he then inserts $$$i$$$ into $$$H$$$.

For example, here is a picture of the skew heap resulting from the insertions $$$1, 2, 3, 4, 5$$$:

Bessie, after watching this process, is curious about what the resulting heap will look like. She has $$$q$$$ queries. In each one, she gives you an integer $$$1 \leq x \leq n$$$, and a string $$$s$$$ consisting of characters L, R, and U, and needs you to answer the following question.

• Suppose you start at the node labeled $$$x$$$, and for each $$$i = 1, 2, \ldots, |s|$$$ in sequence, go to the left child of the current node if $$$s_i = \texttt{L}$$$, go to the right child if $$$s_i = \texttt{R}$$$, and go to the parent if $$$s_i = \texttt{U}$$$. Tell Bessie the value stored in the node you end up at, or report that you go out of bounds of the heap during this process.

After all other jobs were lost to AI, Ezra decided to become a history teacher. To prepare his class for their future careers (also as history teachers), Ezra wants them to keep up with current events.

There will be $$$n$$$ classes in the semester, and $$$m$$$ news events. The $$$i$$$-th news event will take place between classes $$$l_i$$$ and $$$r_i$$$ inclusive. For each class, a subset of the students has already been chosen to present on news events. During that class, each of the chosen students has to present a news event.

Let's take a look at how students pick events to present. A student is characterized by their enthusiasm $$$e_i$$$. Just before a class when this student is supposed to present, suppose there are $$$x$$$ news events that are currently ongoing and that have not been presented in a previous class. Then, this student will choose $$$\min(x, e_i)$$$ of these events, and be prepared to present any one of their chosen events.

During the $$$i$$$-th class, $$$k_i$$$ students, with enthusiasm levels $$$e_1, e_2, \ldots, e_{k_i}$$$, will be presenting. Ezra can choose the order in which these students present. Each chosen student will choose and present one of the events they prepared that has not been presented by another student. But if a student's prepared topics have all already been presented by others, that student will become embarrassed and drop out of the class. Ezra doesn't want this to happen.

Now, Ezra turns to you for help. Is it possible for him to pick the order in which students present in each class, to guarantee that no student becomes embarrassed, no matter how they choose events?

Westin the sheep is playing a parkour game.

In the game, there are $$$n$$$ buildings in a line, conveniently numbered $$$1$$$ through $$$n$$$. The $$$i$$$-th building has height $$$h_i$$$. Westin spawns at building $$$s$$$, and his goal is to visit every building at least once.

Westin has an energy level, which is initially a non-negative integer $$$m$$$. In one move, he can jump from a building to an adjacent building. Jumping to a taller adjacent building costs $$$1$$$ unit of energy, so you cannot jump to a taller adjacent building if your energy level is $$$0$$$. Note that jumping to an adjacent building that is the same height or shorter height does not cost any energy, and is always allowed.

Finally, there are two teleporters in the game  — one to the left of building $$$1$$$, and one to the right of building $$$n$$$. Both of these teleporters are on the ground, so you can jump onto them for no energy cost, as long as you are on either building $$$1$$$ or building $$$n$$$. Jumping on either teleporter takes you to the spawnpoint $$$s$$$, and restores your energy level to the original value, $$$m$$$.

A illustration of the optimal strategy in the last sample test. We first jump all the way to the left teleporter, then all the way to building $$$n$$$.

Now you know all the rules of the game. There's just one thing you don't know  — where will Westin spawn? Solve the following problem for each $$$1 \leq s \leq n$$$:

• Suppose Westin spawns at building $$$s$$$. What's the minimum amount of energy he must start with if he wants to visit every building at least once?

Farmer John has $$$n$$$ cows that he needs to ferry across a river. He has a boat which can take at most $$$k$$$ cows across at a time. Farmer John will repeatedly ride the boat across the river with some (potentially empty) set of cows until all cows are on the other side of the river.

There are $$$m$$$ sets of cows that cannot be left alone, otherwise they will plan the violent seizure of the farm from their human master. Specifically, for each of these subsets of cows, whenever FJ is riding the boat, they cannot all be on the same side of the river (even if they are with other cows).

Find the minimum number of times FJ needs to ride the boat to ferry all cows across the river, or report that it is impossible.