Two frogs, Thomas and Waymo, are attempting to cross a pond.

Currently, they are both at the starting shore of the pond. In the pond, there are $$$N$$$ rows of unoccupied lily pads. In each row, there are two lily pads, a left lily pad and a right lily pad. One of them is afloat, and one of them is underwater. Also, each lily pad can hold at most one frog.

A frog may jump from the starting shore to an unoccupied and afloat lily pad in the first row, or from a lily pad in one row to an unoccupied and afloat lily pad in the next row, or from a lily pad in the last row to the ending shore.

When a frog jumps from a lily pad, that lily pad goes underwater, and the other lily pad in its row goes afloat. If a frog jumps from the right lily pad in a row, the right lily pad will go underwater, and the left lily pad will go afloat, and vice versa. Also, the frogs are polite. Thus, when one frog is mid-jump, the other frog will not jump.

Thomas and Waymo will jump in any order, obeying the above rules, until they both have made it to the ending shore. When a frog lands on a lily pad on the right, it gains a point. What is the maximum number of points total that Waymo and Thomas can gain?

You have been hired as a Temporary Part-Time Assistant Manager of the Executive Municipal Internet Service Provider Administration!

Your job is to set up cell towers to provide internet to homes in The City.

The City can be visualized as a very large rectangular grid. The rows are numbered starting from $$$1$$$, from south to north. The columns are numbered starting from $$$1$$$, from west to east. There are also $$$n$$$ houses on this grid, denoted by $$$(r, c)$$$, where $$$r$$$ is the number of the row the house is in, and $$$c$$$ is the number of the column the house is in.

You are trying to install cell towers for the houses. However, the cell towers have a peculiar set of rules.

A cell tower can only provide signal to a right isosceles triangle that extends south and east from it. More formally, a cell tower at $$$(r, c)$$$ covers all houses $$$(r', c')$$$, such that $$$c \leq c'$$$, and $$$r' + c' \leq r + c$$$.

If a cell tower is set at $$$(3, 1)$$$, it can only provide signal to houses at $$$(3, 1), (2, 1), (1, 1), (2, 2), (1, 2), (1, 3)$$$. Here is a diagram of the range of a cell tower at $$$(3, 1)$$$:

Because the terrain gets rougher the further north you go, the cost of a cell tower is equal to the number of the row it is installed. For instance, installing a cell tower at $$$(3, 1)$$$ has a cost of $$$3$$$.

A cell tower may be installed on top of houses, and it will still provide coverage as usual (despite protests from homeowners).

The City is a bit indecisive about how many cell towers they would like to install. Thus, for every $$$i$$$ from $$$1$$$ to $$$n$$$, find the minimum cost to cover all houses with at most $$$i$$$ cell towers.

In the following undirected graph, count the number of walks from $$$A$$$ to $$$A$$$ that visit nodes $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ exactly $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ times, respectively, modulo $$$998244353$$$.

You encounter a triangle. The first thing you can tell about it is that it is most certainly not Japanese.

The triangle contains $$$n$$$ rows, the $$$i$$$th from top contains $$$i$$$ numbers, $$$a_{i,1}, a_{i,2} \dots a_{i,i}$$$. The numbers are not written in Japanese.

The triangle then speaks to you, but not in Japanese. It wagers $$$100$$$ points that you cannot find the sum of the numbers in each of its rows.

You confidently accept the challenge. But before you begin, the triangle puts on a not Japanese shirt, obscuring all rows from $$$1$$$ to $$$n-1$$$, and only the numbers in row $$$n$$$ remain visible.

Fortunately, the shirt has some not Japanese text that reveals an important property: Every hidden number is the minimum of two numbers directly below it. In other words, $$$a_{i,j} = min(a_{i+1,j}, a_{i+1, j+1})$$$ for all $$$1 \leq i \leq n-1$$$ and $$$1 \leq j \leq i$$$.

Can you find the sum of the not Japanese numbers in each not Japanese row of the not Japanese triangle?

Yam is racing robots! Unfortunately, his robots are out of control, so he has to stop them before they crash.

Yam has $$$N$$$ robots, each with speed $$$a_i$$$ ($$$a_i$$$ is non-decreasing). They are all positioned at the start (i.e., position $$$0$$$) of a track of length $$$L$$$ meters. For each subarray, Yam does the following:

First, he divides the robots in the subarray into $$$k$$$ groups of robots, where each robot must belong to exactly one group, and each group has at least one robot. Every second, every robot will advance $$$a_i$$$ meters forward. Then, after every second, Yam chooses a group and shoots every robot in the group, stopping them from moving forward in the future. If any robot crosses the end of the track (i.e., its position is strictly greater than $$$L$$$), then it spontaneously combusts. Define the score of this subarray as the maximum number of groups that Yam can form while ensuring that no robot spontaneously combusts. (Yam can choose to group the robots strategically to maximize the score.)

Yam thinks this is too easy, so he challenges you to find the sum of scores over all subarrays.

Let $$$f(x)$$$ be the number of positive integers $$$y$$$ such that $$$y \lt x$$$ and $$$\text{popcount}(y) \gt \text{popcount}(x)$$$, where $$$\text{popcount}(z)$$$ is equal to the number of $$$1$$$s in the binary representation of $$$z$$$.

Given $$$t$$$ testcases of $$$x$$$ in its binary representation, find $$$f(x)$$$ for each test case. Because this number might be too large, output the answer modulo $$$998244353$$$.

Note: $$$|x|$$$ represents the length of $$$x$$$ in its binary representation. Also, some values of $$$x$$$ might be too large to convert to an integer, even with $$$64$$$ bits.

Let $$$f(x)$$$ be the number of positive integers $$$y$$$ such that $$$y \lt x$$$ and $$$\text{popcount}(y) \gt \text{popcount}(x)$$$, where $$$\text{popcount}(z)$$$ is equal to the number of $$$1$$$s in the binary representation of $$$z$$$.

Given $$$l$$$, $$$r$$$ $$$(1 \leq l \leq r)$$$ in their binary representation, find $$$\sum_{x=l}^{r} f(x)$$$. Because this number might be too large, output the answer modulo $$$998244353$$$.

Note: $$$|x|$$$ represents the length of $$$x$$$ in its binary representation. Also, some values of $$$x$$$ might be too large to convert to an integer, even with $$$64$$$ bits.

Alex like math, and permutations are math. So he made a problem about permutations.

A permutation is a list of distinct integers from $$$1 \dots N$$$. Alex gives you two permutations, of length $$$N$$$: $$$a_1, a_2, \dots, a_N$$$ and $$$b_1, b_2, \dots, b_N$$$.

Alex is interested in permutation composition. Thus, he created two operations on the permutations:

Type 1 operation:

Compute $$$a'_i = b_{a_i}$$$ for all $$$1 \leq i \leq N$$$. Then, assign $$$a_i = a'_i$$$ for all $$$1 \leq i \leq N$$$.

Type 2 operation:

Compute $$$b'_i = a_{b_i}$$$ for all $$$1 \leq i \leq N$$$. Then, assign $$$b_i = b'_i$$$ for all $$$1 \leq i \leq N$$$.

He will then apply those operations $$$Q$$$ times and ask you to print out both permutations after all the operations.

However, Alex realized this problem was too hard for him to solve. So he decided to make it harder by making the operations more complicated:

Type 1 operation:

Compute $$$a'_i = a_{b_{a_i}}$$$ for all $$$1 \leq i \leq N$$$. Then, assign $$$a_i = a'_i$$$ for all $$$1 \leq i \leq N$$$.

Type 2 operation:

Compute $$$b'_i = b_{a_{b_i}}$$$ for all $$$1 \leq i \leq N$$$. Then, assign $$$b_i = b'_i$$$ for all $$$1 \leq i \leq N$$$.

Alex will now apply the new operations instead of the old operations to the permutations $$$Q$$$ times and asks you to print out both permutations after all the operations.

Alex like math, and permutations are math. So he made a problem about permutations.

A permutation is a sequence of integers from $$$1$$$ to $$$N$$$ of length $$$N$$$ containing each number exactly once. You are given a permutation $$$p_1, p_2 \dots p_N$$$, and another list of integers $$$w_1, w_2 \dots w_K$$$.

For $$$1 \leq i \leq N$$$, and $$$1 \leq j \leq K$$$, define $$$a_{i, j} = k$$$ if $$$k$$$ is the $$$j$$$th largest index among those satisfying $$$p_k \gt p_i$$$ and $$$k \lt i$$$. If fewer than $$$j$$$ such indices satisfy the condition, $$$a_{i, j} = 0$$$.

For each index $$$1 \leq i \leq N$$$, please find $$$\sum_{j = 1}^K a_{i, j} w_j$$$.

For some test cases, you will need to process the permutation online. You must answer all the indices in order, and you won't know later values of the permutation until you've answered all the earlier indices.

There is a triangular array with $$$n+1$$$ rows, which is an equilateral triangle pointing up. Each cell has a coordinate $$$(x, y, z)$$$ representing the number of rows it is away from the right slanted side, the bottom side, and the left slanted side respectively. All coordinates satisfy $$$x + y + z = N$$$ and $$$0 \leq x, y, z \leq N$$$.

Each cell contains a value which is initially $$$0$$$.

The triangular array when $$$N = 4$$$. The black triples are coordinates. The red numbers are values.

You can perform operations on the array.

In one operation, you can pick a number, then add that number to a parallelogram of cells which has one vertex coinciding with a vertex of the triangle and has edges which are aligned with the edges of the triangle adjacent to that vertex.

More formally, you can perform the following operations on the triangular array:

An operation of the form $$$X \ q_y \ q_z \ c$$$ will add $$$c$$$ to all cells $$$(x, y, z)$$$ such that $$$y \leq q_y$$$ and $$$z \leq q_z$$$. The restrictions on $$$q_y, q_z$$$ and $$$c$$$ are: $$$0 \leq q_y, q_z, q_y + q_z \leq N$$$, and $$$-10^{15} \leq c \leq 10^{15}$$$.

An operation of the form $$$Y \ q_z \ q_x \ c$$$ will add $$$c$$$ to all cells $$$(x, y, z)$$$ such that $$$z \leq q_z$$$ and $$$x \leq q_x$$$. The restrictions on $$$q_z, q_x$$$ and $$$c$$$ are: $$$0 \leq q_z, q_x, q_z + q_x \leq N$$$, and $$$-10^{15} \leq c \leq 10^{15}$$$.

An operation of the form $$$Z \ q_x \ q_y \ c$$$ will add $$$c$$$ to all cells $$$(x, y, z)$$$ such that $$$x \leq q_x$$$ and $$$y \leq q_y$$$. The restrictions on $$$q_x, q_y$$$ and $$$c$$$ are: $$$0 \leq q_x, q_y, q_x + q_y \leq N$$$, and $$$-10^{15} \leq c \leq 10^{15}$$$.

For instance, after the operation $$$X \ 1 \ 2 \ 3$$$, the triangular array would look as follows:

The affected cells are the cells in the green parallelogram. ($$$y \leq 1$$$, and $$$z \leq 2$$$). Their values increase by $$$3$$$.

You are also given a triangular region $$$T$$$. Your objective is to use these operations to change the value of all cells in a given triangular region, $$$T$$$, into $$$1$$$, while leaving the rest of the triangular grid as $$$0$$$.

That triangular region will be specified by $$$q_x$$$, $$$q_y$$$, and $$$q_z$$$, $$$0 \leq q_x, q_y, q_z, q_x+q_y, q_y+q_z, q_z+q_x \leq N$$$.

If $$$q_x + q_y + q_z \leq N$$$, then $$$T$$$ contains all cells $$$(x, y, z)$$$ such that $$$x \geq q_x$$$, $$$y \geq q_y$$$, $$$z \geq q_z$$$.

If $$$q_x + q_y + q_z \gt N$$$, then $$$T$$$ contains all cells $$$(x, y, z)$$$ such that $$$x \leq q_x$$$, $$$y \leq q_y$$$, $$$z \leq q_z$$$.

For instance, if $$$q_x = 1$$$, $$$q_y = 1$$$, and $$$q_z = 1$$$, then $$$T$$$ would look as follows:

The purple triangle is $$$T$$$. The red values are the desired ending state of the triangular array.

And, if $$$q_x = 2$$$, $$$q_y = 2$$$, and $$$q_z = 2$$$, then $$$T$$$ would look as follows.

The purple triangle is $$$T$$$. Note that it is in the opposite orientation. The red values are the desired ending state of the triangular array.

Construct a sequence of at most $$$1000$$$ operations to accomplish the objective.

After barely surviving her finals, Bocchi has decided to tour the country to do some sightseeing!

The country can be described by $$$n$$$ cities connected by $$$n - 1$$$ roads. The $$$i$$$-th road connects cities $$$u_i$$$ and $$$v_i$$$ with length $$$l_i$$$. It is possible to visit all the cities starting from any city using a sequence of roads.

Being an introvert, Bocchi hasn't seen much of the country, so she wants to visit as many cities as possible. However, she won't think a city is exciting if she has visited it within the last $$$k$$$ weeks. For example, if she visits some city on week $$$w,$$$ regardless of whether or not she thinks the city is exciting, she will not find the city exciting again before week $$$w+k$$$, at which point she will find it exciting again.

Bocchi is planning on going on $$$q$$$ tours. Specifically, for her $$$i$$$-th tour, she will start on week $$$w_i$$$ (there are many weeks in the strange land of Bocchi!) and start from city $$$u_i.$$$ But because Bocchi doesn't like being on the road for too long, she will travel to every city she can reach, as long as the length of each individual road does not exceed $$$s_i$$$. Each tour takes one week, and she can't be on multiple tours in the same week.

Bocchi is lazy and doesn't want to replan her tours. Please help her determine, for each tour, how many exciting cities she visits.

Given positive integers $$$n,m,k$$$. Count the number of pairs of arrays $$$(a,b)$$$ consisting of only positive integers, such that:

• $$$a$$$ has length $$$n$$$,
• Each entry of $$$a$$$ is at most $$$m$$$,
• $$$b$$$ has length $$$k$$$,
• $$$\displaystyle \sum^n_{i=1} a=\displaystyle \max^k_{j=1} b$$$.

Since the above is too easy, there are $$$q$$$ queries. Each query specifies a $$$k$$$, and you have to answer the above. The values of $$$n$$$ and $$$m$$$ are fixed throughout the test case.