Being a student of Belarusian State University (BSU) is an earnest reason for pride. While studying the Theory of Algorithms course, you are obliged to solve many challenging problems before you are admitted to the final exam. Here is one of these problems.

You are given a positive integer $$$n$$$ and $$$4n$$$ integers $$$c(i, j, k)$$$ which can be equal to $$$0$$$ or $$$1$$$ ($$$0 \le i \lt n$$$, $$$j \in \left\{0, 1\right\}$$$, $$$k \in \left\{0, 1\right\}$$$).

Consider two integers $$$x$$$ and $$$y$$$ between $$$0$$$ and $$$2^n - 1$$$, inclusively. Let $$$x = \sum\limits_{i = 0}^{n - 1}{x_i\cdot 2^i}$$$ and $$$y = \sum\limits_{i = 0}^{n - 1}{y_i \cdot 2^i}$$$ be their binary representations ($$$x_i, y_j \in \left\{0, 1\right\}$$$). Define $$$f(x, y) = \sum\limits_{i = 0}^{n - 1}{c(i, x_i, y_i)\cdot 2^i}$$$. Clearly, $$$f(x, y)$$$ is also an integer between $$$0$$$ and $$$2^n - 1$$$.

Given two multisets $$$A$$$ and $$$B$$$, find the multiset of values $$$f(a, b)$$$ over all pairs $$$(a, b)$$$, where $$$a \in A$$$, $$$b \in B$$$.

You are a happy possessor of the powerful tool called Beautiful Sequence Unraveler (BSU). This tool works with beautiful sequences. A beautiful sequence is an array $$$a_1, a_2, \ldots, a_n$$$ of $$$n$$$ integers for which the following statement holds: there are no integers $$$i$$$ such that $$$1 \le i \lt n$$$ and $$$\max\{a_1, \dots, a_i\} = \min\{a_{i + 1}, \dots a_n\}$$$.

BSU deals with beautiful sequences pretty well, but you do not know how frequently such sequences occur. So you want to calculate the number of beautiful sequences among all the arrays of length $$$n$$$ which consist of integers between $$$1$$$ and $$$k$$$, inclusively. Since this number may be large, you are required to calculate it modulo prime number $$$p$$$.

You are a member of the Brave Seekers of Unicorns (BSU), the secret magical order. The BSU is fond of seeking unicorns. Recently, they have agreed to call an array $$$a_1, a_2, \ldots, a_k$$$ of $$$k$$$ integers a unicorn if it satisfies the following conditions:

• the array is not empty ($$$k \gt 0$$$);
• there are no three consecutive elements with their bitwise XOR equal to zero ($$$a_i \oplus a_{i+1} \oplus a_{i+2} \ne 0$$$ for all $$$1 \le i \le k - 2$$$);
• the array is strictly increasing ($$$a_i \lt a_{i+1}$$$ for all $$$1 \le i \le k - 1$$$);
• the elements of the array are integers between $$$1$$$ to $$$n$$$, inclusively ($$$1 \le a_i \le n$$$ for all $$$1 \le i \le k$$$).

For example, if $$$n = 10$$$, then the array $$$[1, 4, 5, 9]$$$ is not a unicorn because $$$1 \oplus 4 \oplus 5 = 0$$$, but the array $$$[2, 4, 7, 9]$$$ is a unicorn.

The Grand Master of the BSU has commanded you to calculate the number of unicorns. Since the number can be pretty large, you must compute it modulo $$$998\,244\,353$$$.

The Bytelandian government has issued the Bank Security Unification law (or, shortly, the BSU law). The recent law regulates the usage of Wi-Fi routers in banks and other financial institutions.

According to the BSU law, all the $$$n$$$ Wi-Fi routers in a bank must be located in a straight line. Suppose that the $$$i$$$-th router operates at the frequency $$$f_i$$$. Denote the security of a connection between two adjacent routers as $$$f_{i}\,\, \&\,\, f_{i+1}$$$, where $$$\&$$$ is the bitwise AND operation.

A set of at least two routers numbered $$$1 \le i_1 \lt i_2 \lt \dots \lt i_k \le n$$$ must be chosen as active. All other routers will be kept inactive so that they can replace the active ones if any of them would break. Denote the security of the network as the sum of the securities of all connections between adjacent active routers. In other words, the security of the network is calculated as $$$\sum\limits_{j=1}^{k-1} f_{i_j}\,\,\&\,\,f_{i_{j+1}}$$$.

You are an employee of a large Bytelandian bank. Surely, the bank is obliged to comply with the BSU law. The routers are already placed in a line, and their placement cannot be changed. Now you want to choose some of the routers as active to maximize the security of the network.

Egor learned about the secret organization called Brief Statements Union (BSU), whose ultimate goal is to make statements of all competitive programming problems clear and concise, and eliminate those long, boring, and unnecessary tales in the statements.

Egor decided to join the organization. For this purpose, he wrote the following problem with a short statement:

You are given an integer $$$\textbf{n}$$$ and $$$\textbf{k}$$$ conditions. The $$$\textbf{i}$$$-th condition states that bitwise AND of all integers $$$\textbf{a}_{\textbf{l}_\textbf{i}}, \textbf{a}_{\textbf{l}_\textbf{i} + 1}, \ldots, \textbf{a}_{\textbf{r}_\textbf{i}}$$$ is equal to $$$\textbf{x}_\textbf{i}$$$.

For each condition $$$\textbf{i}$$$, determine if there exists an array $$$\textbf{a}_1, \textbf{a}_2, \ldots, \textbf{a}_\textbf{n}$$$ of $$$\textbf{n}$$$ integers which satisfies all the conditions except the condition $$$\textbf{i}$$$. Note that it is OK if the array satisfies the condition $$$\textbf{i}$$$ too.

The committee of the organization liked Egor's problem statement. And this is how he got accepted into the organization. Now, Egor has decided to offer the problem to this contest, so you have to solve it.

There is a large organization called Border Similarity Undertaking (BSU) which is located in Bytelandia. The head of the organization has a large map of this glorious country. The map is represented as a matrix $$$A$$$ with $$$n$$$ rows and $$$m$$$ columns. Each element of the matrix is a lowercase Latin letter.

BSU has decided to construct a new factory. The factory may be of any size, but it must be rectangular and its sides must be parallel to the sides of the map. Moreover, as you can deduce from the name of the organization, it is required that all the letters on the border of the rectangle are the same.

The head of BSU hasn't decided where to build a factory yet. So BSU has hired you to calculate the number of possible factory locations.

Formally speaking, you are to find the number of tuples of integers $$$(x_1, y_1, x_2, y_2)$$$ such that $$$1 \le x_1 \lt x_2 \le n$$$, $$$1 \le y_1 \lt y_2 \le m$$$, and $$$A_{i,y_1} = A_{x_1, j} = A_{x_2, j} = A_{i, y_2}$$$ for all $$$i \in [x_1, x_2]$$$, $$$j \in [y_1, y_2]$$$.

You are developing a software kit named Biological Software Utilities (BSU). The kit includes a program that is dedicated to tree recognition. Recall that a tree is a connected undirected graph without cycles.

In nature, when a tree grows, two neighboring vertices are added at the same time. Thus, you consider a tree to be plausible if, after removing some edges, the resulting graph consists only of connected components with $$$2$$$ vertices. In other words, a tree is plausible if and only if it has a perfect matching.

Now you are to implement a new function for BSU to calculate the number of plausible trees that have $$$n$$$ vertices numbered with distinct integers between $$$1$$$ and $$$n$$$. Two trees are considered different if there is an edge $$$(u, v)$$$ which is present in exactly one of the trees.

Since the number of plausible trees can be very large, you have to calculate it modulo $$$998\,244\,353$$$.

There are so many natural wonders in the Bytelandia States Union (BSU)! But the most mysterious wonder is, undoubtedly, the Murbeda Rectangle. Here time and space behave in a rather unusual way. Bytelandian scientists still haven't found a reason why such anomalies occur, even after many years of research. Luckily, they managed to understand how physics works at the Murbeda Rectangle.

Consider the Murbeda Rectangle as a large rectangle. The scientists have divided the rectangle into a grid of $$$2 \cdot 10^9 \times 2 \cdot 10^9$$$ small squares. Each square has coordinates $$$(x, y)$$$, where the $$$x$$$-axis goes from north to south, and the $$$y$$$-axis goes from west to east. So, the northwestern square is at $$$(1, 1)$$$, and the southeastern square is at $$$(2 \cdot 10^9, 2 \cdot 10^9)$$$. There is a portal in the square $$$(x_2, y_2)$$$ which is the only way to connect the Murbeda Rectangle to the outer world.

Suppose you are in the square $$$(x, y)$$$ of the rectangle. You can move in one of four directions (north, south, east, or west), thus increasing or decreasing one of the coordinates by one. You cannot go out of the rectangle: for instance, you cannot go south from the square $$$(2\cdot 10^9, 42)$$$ or go west from the square $$$(42, 1)$$$. If you do, you may fall into a deep canyon filled with poisonous snakes.

The most fascinating thing is the amount of time you spend on moving in some direction. If you are in the square $$$(x, y)$$$, then:

• going south (increasing the $$$x$$$-coordinate by one) takes $$$f_s(x, y) = 2xy^2 + 2y^2 + x^2$$$ seconds;
• going north (decreasing the $$$x$$$-coordinate by one) takes $$$f_n(x, y) = -2xy^2 + 2y^2 + x^2$$$ seconds;
• going east (increasing the $$$y$$$-coordinate by one) takes $$$f_e(x, y) = 2x^2y + 2x^2 + y^2$$$ seconds;
• going west (decreasing the $$$y$$$-coordinate by one) takes $$$f_w(x, y) = -2x^2y + 2x^2 + y^2$$$ seconds.

The scientists intend to rescue $$$n$$$ people from the Murbeda Rectangle. For a person who stands in the square $$$(x_1, y_1)$$$, they need to determine the minimum time needed to reach the portal. One can prove that such a minimal amount of time exists, so no one can reach an infinitely small moment by walking around.

Since the place is extremely unusual, each of the $$$n$$$ persons may require a different portal.

Alexey and Boris are playing a game called Binary Supersonic Utahraptors (BSU).

Initially, Alexey has $$$n$$$ utahraptors, and Boris has $$$m$$$ utahraptors. Each utahraptor is either yellow or red.

Then, the players take $$$k$$$ turns described by integers $$$s_1, s_2, \ldots, s_k$$$. The $$$i$$$-th turn is performed as follows. First, Alexey chooses $$$s_i$$$ utahraptors that belong to him and gives them to Boris. Then, Boris chooses $$$s_i$$$ utahraptors that belong to him (the utahraptors that Alexey has just given to him may also be chosen) and gives them to Alexey.

When the $$$k$$$ moves are done, the score of the game is calculated. The score is equal to $$$|a_y - b_r|$$$, where $$$a_y$$$ is the number of yellow utahraptors Alexey has, and $$$b_r$$$ is the number of red utahraptors Boris has. Alexey's goal is to minimize the score, and Boris wants to maximize it.

Write a program that calculates the score of the game if both players use their optimal strategies.

Alexander is going to install an important update package called Burnished Security Updates (BSU) on his computers. He owns a network which consists of $$$n$$$ computers connected by $$$m$$$ bidirectional cables.

Eventually, BSU will be installed on every computer in the network. But Alexander doesn't know how the system will behave after the update, so he will first install the update on some non-empty set of computers that satisfies the following conditions:

• no two updated computers are connected directly by a cable;
• each cable must have at least one updated computer as its endpoint;
• the set of the updated computers must be as small as possible.

Formally speaking, if we represent the computer network as a graph, Alexander wants to find an independent set of the graph such that it forms a vertex cover of the same graph. Among all possible sets, he wants to choose one with the least possible size.

Now, you need to help Alexander and find the number of computers on which BSU will be installed. Note that sometimes it can be impossible to find a set satisfying the conditions above at all.

You work in Bookcase Solidity United (BSU), a company that tests furniture under various load and measures its reliability. Right now, they are testing a bookcase with $$$n$$$ shelves, placed from top to bottom.

The bookcase will be tested by putting heavy iridium balls on some of the shelves and observing them break. We assume that all balls are the same and BSU has infinitely many of them.

The engineers measured that the $$$i$$$-th shelf from the top can endure strictly less than $$$a_i$$$ balls. If there are $$$x \ge a_i$$$ balls on the shelf, it breaks and the balls fall. If there are no unbroken shelves, all the balls fall on the floor. Otherwise, $$$\left\lfloor \frac x 2 \right\rfloor$$$ balls fall on the nearest unbroken shelf $$$j$$$ below, and the rest of the balls fall on the floor. (Don't worry, the floor is solid enough to hold all the balls.) If, after this operation, the number of balls on the $$$j$$$-th shelf is not less than $$$a_j$$$, then the $$$j$$$-th shelf breaks, the balls fall from the shelf in the same way as described above, and so on. The process terminates either when all the balls are on the floor or the next shelf is solid enough to hold the balls which fell on it.

To measure the reliability, the employees of BSU put the balls one by one on some of the shelves. The goal is to break $$$k$$$ upmost shelves using the minimum possible number of balls. As trying various placement variants is costly, time-consuming, and produces much noise from heavy falling balls, the management of the company has ordered you to calculate the least number of balls to break $$$k$$$ upmost shelves, for each $$$k$$$ from $$$1$$$ to $$$n$$$.

Business Semiconductor Units (BSU) is a large international corporation that focuses on selling fast and reliable computers to business clients. Recently, they have decided to develop a new processor model which will work even faster and more reliably than its predecessors.

The R&D department of the company is responsible for designing the instruction set and processor architecture. After the deadline, they should demonstrate the working prototype to the head of the company. Unfortunately, the whole department was playing Minecraft most of the time instead of doing their job, so the presented prototype supports only three simple instructions.

Let's take a closer look at their masterpiece. The new processor has $$$16$$$ registers named from r0 to r15, each of them can store an unsigned $$$16$$$-bit integer. There is also main memory consisting of $$$2^{16} + 1$$$ eight-bit cells.

The program for this processor is a sequence of instructions. The instructions are executed sequentially, neither jumps nor loops are supported. The processor executes the same sequence of instructions $$$5000$$$ times. That is, the following procedure is repeated $$$5000$$$ times: go over the instructions from the start to the end and execute them.

Below you can see the list of available instructions. For clarity, let's call $$$x\text{ mod } 2^8$$$ the lower part of the number $$$x$$$, and $$$\left\lfloor \frac{x}{2^8} \right\rfloor$$$ the upper part of the number $$$x$$$. The number in the $$$i$$$-th main memory cell is denoted $$$mem_i$$$.

• imm r, b: load the constant number $$$b$$$ ($$$0 \le b \lt 2^{16}$$$) into the register named $$$r$$$;
• ld x, y: suppose that the register named $$$y$$$ stores the number $$$b$$$. Then, the number $$$mem_{b+1}\cdot 2^8 + mem_b$$$ is put into the register $$$x$$$;
• st x, y: suppose that the register named $$$x$$$ stores the number $$$a$$$, and the register $$$y$$$ stores the number $$$b$$$. Then, the lower part of $$$b$$$ is put into $$$mem_a$$$, and the upper part of $$$b$$$ is put into $$$mem_{a+1}$$$.

As you can see, the instruction set is pretty lean, and the R&D department is unsure whether the processor is capable of doing anything non-trivial or not. To make it run some useful programs, they hired you and gave you an assignment. Now, you need to write a program for the new processor that multiplies $$$n$$$ non-negative $$$16$$$-bit numbers modulo $$$2^{16}$$$.

Technically, this problem is an output-only interactive problem. [Sounds weird, isn't it? :)]

In each test, the interactor first reads the instructions you wrote to the output. Next, it reads the integer $$$n$$$ and $$$n$$$ integers $$$a_i$$$ from the test ($$$1 \le n \le 4000$$$, $$$0 \le a_i \lt 2^{16})$$$. The number $$$n$$$ is placed into the register r0. For each $$$1 \le i \le n$$$, the lower part of $$$a_i$$$ is placed into $$$mem_{2\cdot i - 2}$$$, and the upper part is placed into $$$mem_{2\cdot i - 1}$$$. All other registers and memory cells are zeroed initially.

Then, the interactor executes your program. The instructions are performed sequentially, and the execution of the program is performed exactly $$$5000$$$ times.

After that, the interactor reads your answer from the register r0 and compares it with $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n$$$ modulo $$$2^{16}$$$.

Anton has $$$n$$$ umbrellas, each of them has a different number from $$$1$$$ to $$$n$$$ written on it. He wants to arrange some of the umbrellas in line so that they would form a brilliant sequence of umbrellas (BSU). A sequence of $$$k$$$ umbrellas with numbers $$$a_1, a_2, \ldots, a_k$$$ is considered a BSU if the following rules apply:

• $$$a_i \gt a_{i-1}$$$ for all $$$2 \le i \le k$$$;
• $$$\text{gcd}(a_i, a_{i-1}) \gt \text{gcd}(a_{i-1}, a_{i-2})$$$ for all $$$3 \le i \le k$$$. Here, $$$\text{gcd}(x, y)$$$ denotes the greatest common divisor of integers $$$x$$$ and $$$y$$$.

Anton would like to create a long BSU. Making the longest one doesn't bother him, he thinks that a BSU of length at least $$$\left\lceil\frac{2}{3}\sqrt{n}\right\rceil$$$ is quite enough.

Anton is busy reading fascinating books about lighthouses, so he asks you to find a BSU that would satisfy him.

You are the responsible holder of a competition called Best Solution Unknown (BSU). The rules of this competition are simple but rather quirky.

First, all the $$$n$$$ participants stand in a row. Then, $$$n-1$$$ matches are held. In each match, jury chooses two adjacent players. The chosen players are given an NP-hard problem, and they try their best to come up with a good solution. The one who provides a better solution wins a round, the other one leaves the competition. After that, players shift to form a valid row again, so the player adjacent to the player that has left the competition becomes adjacent to the winner of the round. As you can see, after all the $$$n-1$$$ matches, only one player remains, and this player is declared a winner of the competition.

You know the competitors well, so you know the strength of each player before the competition. The strength of the $$$i$$$-th player, counting from the left of the row, is $$$a_i$$$. You also know that a player with greater strength wins the match. If the players have equal strength, both have a chance to win. You have noticed that victories motivate the players, so the strength of the winner of a match increases by one.

However, you do not know who plays in each match and who wins a match in case of equal strengths. So, you are wondering who can become the winner of the competition. You thought it was a good problem for the participants of BSU, but, unfortunately, it is not NP-hard, so you have to solve it yourself.