As you know, you guys are participating in CCPC (Chinese Constructive Problem Contest), and no doubt that the proposition school SYSU, as the kingdom of constructive problems, is going to challenge you to solve some related problems.

Given an $$$n \times n$$$ grid, you are asked to fill each number in $$$[1,k]$$$ into the grid, and it needs to fulfill the following requirements.

1. Each number from $$$1$$$ to $$$k$$$ occurs exactly once.
2. Each cell should be filled with at most one number.
3. Each row and column has at least two numbers.
4. For each integer $$$i\in [1,n]$$$, the greatest common divisor of all numbers in row $$$i$$$ is equal to the greatest common divisor of all numbers in column $$$i$$$.

It's guaranteed that there must be a valid solution under the restriction of the problem.

For any two positive integers $$$a$$$ and $$$b$$$, define the function by the following C++ code:

std::string gen_string(int64_t a, int64_t b) {
  std::string res;
  int64_t ia = 0, ib = 0;
  while (ia + ib < a + b) {
    if ((__int128)ia * b <= (__int128)ib * a) {
      res += '0';
      ia++;
    } else {
      res += '1';
      ib++;
    }
  }
  return res;
}

$$$ia$$$ will equal $$$a$$$ and $$$ib$$$ will equal $$$b$$$ when the loop terminates, so this function returns a bitstring of length $$$a+b$$$ with exactly $$$a$$$ zeroes and $$$b$$$ ones. For example, $$$gen\_string(4,10)=01110110111011$$$.

Given the argument of $$$A, B$$$, you should calculate the number of different subsequences of $$$gen\_string(A, B)$$$, and print it modulo $$$998244353$$$.

NOTE: A sequence $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from b by deleting several (possibly, zero or all) elements.

As a magician and a palindrome lover, you want to make strings become palindromes through magic operation.

In one magic operation, you can erase $$$S[l...r]$$$ of a string $$$S$$$ and concatenate the rest of $$$S$$$ to get the target string, which costs $$$r - l + 1$$$ units of magic potion.

You are given a string $$$str$$$, consisting of $$$n$$$ lowercase Latin letters, and there are $$$m$$$ magic tests.

For each one, you are given two integers $$$l,r$$$, denoting $$$S$$$ as $$$str[l...r]$$$.

You should use at most one magic operation, report the minimal cost of magic potion to make $$$S$$$ become palindrome, and the number of ways to achieve the target with the previous minimized cost.

Specifically, if $$$S$$$ is already a palindrome, just output '$$$\text {0 0}$$$'.

NOTE:

• A palindrome is a string that reads the same from left to right as from right to left. For example, 'aba', 'ccpcc', 'qaq' are palindromes, while 'ccpc' and 'qhd' are not.
• $$$S[l...r]$$$ means the substring of $$$S$$$ which starts from the $$$l$$$-th character and ends with the $$$r$$$-th character.

The girls of SYSU like drinking tea. But one day, they wanted a change and decided to try coffee in the next $$$n$$$ days.

Now Zayin, who always provides food and drinks for SYSU, will go to the shop to buy some coffee. She learns that the price of day $$$i$$$ is $$$a_i$$$. Meanwhile, she has $$$m$$$ coupons - the $$$i$$$ coupon can be used before day $$$r_i$$$ (inclusively) and can reduce the price of coffee on that day by $$$w_i$$$.

Notice that each coupon can be used only once and Zayin can use more than one coupon per day. The price can be a negative number after using the coupons.

Since the girls of SYSU still need to drink tea, Zayin decided to choose some days to buy coffee. Now she wants to know the minimum money she will spend (or the maximum money she can get) if she chooses exactly $$$k\ (1\le k \le n)$$$ days to buy coffee.

Imagine you have a large tape of size $$$n \times m$$$, with $$$n$$$ brushes dipped in different colors arranged in the first column, waiting to color the entire tape.

This image shows an example, where the lines represent the movement path of the brushes.

For each brush, you can move it to the right, up or down for several times. Each cell cannot be colored twice, even if the colors are the same. Your goal is simple - to color all cells of the tape using some operations. Note that the initial positions of the brushes are already colored.

Meanwhile, due to the decorative purpose of the tape, there are some restrictions on coloring. For each restriction, we will provide two cells in the same column and indicate whether the colors of these two cells must be the same or different.

Under these restrictions, how many different color arrangements can the final tape have? Note that in this case, we do not consider flipping or rotating the tape.

The prime minister of the Mathematical Kingdom is a crazy follower of prime numbers, therefore he especially set up a department to solve problems related to prime numbers. The head of this department, Mr.Robert, recently received a letter from his friend Euler.

The letter contains a mystery of prime. There is a sequence $$$a_1, a_2, ..., a_n$$$. Euler considers a sequence beautiful if and only if all elements are $$$\textbf{positive}$$$ integers and the sum of any two adjacent elements is a prime.

Formally,$$$\forall i\in [1, n] \cap \mathbb{N}, a_i \in \mathbb{N}^+,\forall i\in [1, n) \cap \mathbb{N}, (a_i+a_{i+1}) \in \mathbb{P},$$$ where $$$\mathbb{P}$$$ represents the set containing all primes.

Sometimes, the given sequence is not beautiful. Mr.Robert would like to make the least effort to make it beautiful, that is to modify the elements of the sequence and minimize the number of updated elements.

Mr.Robert is busy these days, so he asked you to report the minimum number of updated elements to make the sequence beautiful.

Given an array $$$a$$$ of length $$$n$$$ and an array $$$b$$$ of length $$$m$$$, construct a grid of size $$$n \times m$$$, where the value in cell $$$(x,y)$$$ is denoted as $$$C[x,y]$$$ and calculated as $$$a_x + b_y$$$.

You start from $$$(1,1)$$$, and in each step, you choose a grid cell located at the bottom right to move to, until you reach $$$(n,m)$$$, aiming to maximize the sum of absolute differences between adjacent cells along the path.

Formally, your goal is to find a sequence $$$(x_1,y_1), (x_2,y_2), ..., (x_k,y_k)$$$ that satisfies the conditions

• $$$(x_1,y_1) = (1,1)$$$
• $$$(x_k,y_k) = (n,m)$$$
• $$$x_i \le x_{i+1},\ y_i \le y_{i+1},\ (x_i,y_i) \neq (x_{i+1},y_{i+1})\ \forall i\in [1, k)$$$

The Kingdom of Calamita was a small nation constantly plagued by natural disasters. The people built their villages and towns in the shades of the great Banyan tree that stood at the kingdom's center. Its massive roots provided stability to the land and the villagers always looked to it for guidance and protection.

The great tree is a rooted tree whose root is node $$$1$$$. For other node $$$i\ (i \gt 1)$$$, its parent in the tree is $$$fa[i](1\le fa[i] \lt i)$$$ and there is an edge in between. There were two types of events that took place in the Kingdom of Calamita — quake and rebuild.

1. Quake: When a tremor hit the range $$$[l, r]$$$ with a magnitude of $$$d$$$, it caused the parent node of every node in that range to shift down by d. In other words, $$$\forall i \in [l, r],\ fa'[i] = max(1, fa[i]-d). $$$ The tree structure shifts after that.

2. Rebuild: During the rebuilding after some disasters, the villagers were seeking for economic recovery. To boost the economy, they set a list of nodes $$$[b_1, b_2,..., b_k]$$$ to become the new trade centers and decided to build some temporary transportation hubs to connect all of the new trade centers. Two trade centers are connected if and only if every node on the simple path between these two centers has been built with a temporary transportation hub on it. Obviously, the villagers were only interested in the minimal number of temporary transportation hubs to achieve the goal.

Over time there were $$$m$$$ such events — some quakes shook up the root system, and some rebuilding aimed at economic recovery.

For each rebuild plan, you need to help the villagers figure out the minimal number of temporary transportation hubs to make all trade centers connected.

Note that Two rebuild events are $$$\textbf{independent}$$$, i.e., the temporary transportation hubs will shut down after the previous rebuilding event, and if you want to use it again, you need to rebuild it.

You are given a sequence of length $$$n$$$ and the number $$$k$$$, ask for support $$$m$$$ operations or inquiries:

• $$$\text{C t}$$$: Let the largest number minus $$$k$$$ (the far left one if there is more than one), executed $$$t$$$ times.
• $$$\text{A x}$$$: Ask for the $$$x$$$-th largest number.

Keyi has a strong passion for reading, and she has developed a habit of morning reading every day.

With the college entrance exam approaching, Keyi plans to learn several words from the 'Victor Dictionary' each morning.

However, her method of memorizing words is a bit peculiar. If she learns a word of length $$$k$$$ today, she insists on memorizing all the words in the dictionary that have the same length of $$$k$$$.

But Keyi's daily energy is limited, and she cannot learn more than $$$W$$$ words in a day, or else she won't be able to remember them all.

Keyi is unsure how to efficiently plan which words to study each morning, so that it can minimize the number of days it will take her to complete the entire 'Victor Dictionary'. Therefore, she kindly requests your assistance.

As you know, you guys are participating in CCPC (Chinese Constructive Problem Contest), and no doubt that the proposition school SYSU, as the kingdom of constructive problems, is going to challenge you to solve some related problems.

Given an $$$n \times n$$$ grid, you are asked to fill each cell with a number within $$$[0,4n^2-1]$$$, and it needs to fulfill the following requirements.

1. Each number occurs at most $$$5$$$ times.
2. Each cell should be filled with exactly one number.
3. For any two adjacent cells with a common edge, their bitwise AND value should be exactly equal to $$$0$$$.

Construct a valid solution, or report it's impossible.

You are given a permutation $$$p$$$ of size $$$n$$$. You want to maximize the number of subarrays of $$$p$$$ that are permutations. In order to do so, you must perform the following operation exactly once:

• Select integers $$$i$$$, $$$j$$$, where $$$1\le i,j\le n$$$, then
• Swap $$$p_i$$$ and $$$p_j$$$.

For example, if $$$p=[5,1,4,2,3]$$$ and we choose $$$i=2$$$, $$$j=3$$$, the resulting array will be $$$[5,4,1,2,3]$$$. If instead we choose $$$i=j=5$$$, the resulting array will be $$$[5,1,4,2,3]$$$.

Which choice of $$$i$$$ and $$$j$$$ will maximize the number of subarrays that are permutations?

NOTE:

• A permutation of length $$$n$$$ is an array of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).
• An array $$$a$$$ is a subarray of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deleting several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Given a tree with $$$n$$$ nodes initially numbered from $$$1$$$ to $$$n$$$, and a node sequence of $$$n-1$$$ length, we are going to perform operations on the tree according to the order of the sequence.

For each operation, if the node to be operated is $$$x$$$, firstly create a new node numbered $$$x+n$$$. For any integer $$$i\in [1,n]$$$ that the edge $$$(x,i)$$$ exists:

• If the node $$$i+n$$$ does not exist, we connect $$$(x+n,i)$$$.
• If the node $$$i+n$$$ exists (in this case, the edge $$$(x,i+n)$$$ always exists), we connect $$$(x+n,i+n)$$$ and delete edge $$$(x,i+n)$$$.

For the resulting graph after each operation, calculate the number of spanning trees modulo $$$998244353$$$.