We have learned your team is good at counting problems. So we ask you a simple problem.

Now you have $$$0-n$$$ permutation, and you need to connect all the numbers in each permutation to make a new valid number and we define the new valid number as $$$S$$$. It is worth noting that if a certain permutation contains leading zero, the permutaion should be eliminated.

For example if $$$n = 2$$$, the set of $$$S$$$ will be $$$102, 120,201,210$$$.

Your task is to count how many $$$S$$$(without leading $$$0$$$) are divisible by $$$m$$$.

There are $$$n$$$ white balls and $$$m$$$ black balls in the box.

Hsueh- randomly takes out a single ball from the box every time until the box is empty.

You need to calculate the probability $$$p$$$ of the number of white balls and black balls outside the box is equal at least once in the process.

You need to output answer modulo $$$998244353$$$. Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

For instance, we consider $$$n = 1$$$ and $$$m = 3$$$, and we appointed "w" to represent the white ball and "b" to represent the black ball.

There are $$$4$$$ possible outcomes:

• "wbbb"
• "bwbb"
• "bbwb"
• "bbbw"

Obviously, two of the results are legal, so the answer should be $$$\displaystyle \frac{1}{2}$$$, and we can get $$$\displaystyle \frac{1}{2} \equiv 499122177 \pmod {998244353}$$$.

This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().

Excellent! pubfso was lucky enough to get a Hoogle Machine Translation Machine.

This is the manual of the Hoogle Machine Translation Machine:

• If you send a word to the machine, it will return the meaning of the word to you.
• If you send two or more words to the machine, i.e. you send $$$x$$$ words to the machine, it will return $$$x$$$ explanations to you. Unfortunately, These $$$x$$$ explanations and $$$x$$$ words do not correspond one-to-one.

  For instance, if we have the correspondence between the following words and explanations:

  • one corresponds to $$$1$$$
  • two corresponds to $$$2$$$
  • three corresponds to $$$3$$$

  If we send $$$\{one, two, three\}$$$ to the Hoogle Machine Translation Machine.

  We may get the one of the following results:

  • $$$\{1, 2, 3\}$$$
  • $$$\{1, 3, 2\}$$$
  • $$$\{2, 1, 3\}$$$
  • $$$\{2, 3, 1\}$$$
  • $$$\{3, 1, 2\}$$$
  • $$$\{3, 2, 1\}$$$

Now, pubfso has $$$n$$$ different words need to translate, he wants your help.

Initially, pubfso will give you $$$n$$$ words.

You can make queries to the Hoogle Machine Translation Machine, Each query is a single line contains $$$x(1 \leq x \leq n)$$$ words which pubfso need to translate. Flush output stream after printing each query. Hoogle Machine Translation Machine will return $$$x$$$ explanations to you.

Your program is allowed to make no more than $$$25$$$ queries (not including printing the answer) to the Hoogle Machine Translation Machine.

When your program ask the meaning of words, i.e. you need to ask $$$x(x \gt 0)$$$ words, print string:

What you need to focus on is, the query "? 0" is invalid, and the jury will return Wrong Answer to you.

If your query is legal, the Hoogle Machine Translation Machine will return Same number of explanations as words to you. As follows:

If we answer with $$$-1$$$ instead of a valid answer, that means you exceeded the number of queries or made an invalid query.

Exit immediately after receiving $$$-1$$$ and you will see wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

When you got the explanation of all the words, you need to print them in order. i.e. print the string:

After printing a query or printing the answer, do not forget to output end of line and flush the output. Otherwise, you will get idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• See the documentation for other languages.

Dup4 has a large number of pebbles. He numbered them $$$a$$$ through $$$b$$$.

Initially, each pebble forms a pile of its own.

But Dup4 hates so many piles. So he can do the following operation to merge the two piles.

Every time, He chooses two pebbles $$$x$$$ and $$$y$$$. If $$$x$$$ and $$$y$$$ have a common prime factor $$$t$$$, and $$$t$$$ greater or equal than $$$p$$$. He can merge the pile of pebbles where $$$x$$$ is and the pile of pebbles where $$$y$$$ is. The premise is that $$$x$$$ and $$$y$$$ belong to two different piles.

He will repeat the above operations until he can no longer merge.

Finally, Dup4 wants to know how many pebble piles will end up.

For instance, if we consider $$$a = 10, b = 20, p = 3$$$, the final result will be:

$$$$$$ [10, 12, 15, 18, 20], [11], [13], [14], [16], [17], [19] $$$$$$

There are $$$7$$$ piles.

If you have solved CrossFire #6XX (Div.998244353) D, you will have the potential to become the king of sum xor.

Today Dup4 meets a problem and he asks you for help. He wants to know whether there exists an array $$$n$$$ non-negative integers $$$a_1, a_2, \cdots ,a_n$$$(the array can be empty) that follow these rules.

• $$$\displaystyle a_1+a_2+\cdots +a_n = S$$$
• $$$\displaystyle a_1 \oplus a_2 \oplus \cdots \oplus a_n = X$$$(Here $$$\oplus$$$ denotes bitwise xor operation)

However, Dup4 thinks the problem is so easy. He thinks he needs to change something.

1. He constructs all arrays that satisfying the requirements.
2. He defines the maximum value of the $$$i$$$-th array as $$$M_i$$$.
3. He finds the minimum $$$M_i$$$ of the all arrays as $$$MIN$$$.
4. He defines a set $$$V$$$ to be composed of arrays which satisfying the condition of $$$M_i = MIN$$$.

Finally, He wants to know the minimum $$$n$$$(the length of the array) of the $$$V$$$.

Hsueh- constructed a matrix of $$$n$$$ rows and $$$m$$$ columns, the label starts from $$$1$$$. He makes the element in the $$$i$$$-th row and $$$j$$$-th column $$$a_{i, j}$$$ equal to $$$i$$$ times $$$j$$$. i.e. $$$a_{i, j} = i \cdot j$$$. You need to find the $$$k$$$-th largest element.

Unfortunately, Hsueh- only has ten fingers, so he can't count numbers with more than ten digits. Therefore, if the answer is strictly greater than $$$9,999,999,999$$$, just output "Oops"(without quotes).

For instance, we consider $$$n = 2$$$ and $$$m = 3$$$, The matrix elements are as follows:

$$$$$$ \left[ \begin{array}{ccc} 1&2&3\\ 2&4&6 \end{array} \right] $$$$$$

• $$$k = 1$$$, the answer is $$$6$$$.
• $$$k = 2$$$, the answer is $$$4$$$.
• $$$k = 3$$$, the answer is $$$3$$$.
• $$$k = 4$$$, the answer is $$$2$$$.
• $$$k = 5$$$, the answer is $$$2$$$.
• $$$k = 6$$$, the answer is $$$1$$$.

The difference between this problem and Hsueh- owns large quantities of apples is more than the data range, please read the statement carefully.

There are $$$n$$$ apples in ltslts's bag, and $$$m$$$ kids around the man. Let's numbered these children $$$1$$$ to $$$m$$$.

ltslts take all of the apples and gave to the first child.

• The first child got $$$n$$$ apples from ltslts. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took a single pile and gave the remaining ($$$x - 1$$$) piles to the second child.
• The second child got $$$\displaystyle \frac{(n - 1)(x - 1)}{x}$$$ apples from the first child. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took a single pile and gave the remaining ($$$x - 1$$$) piles to the third child.
• $$$\cdots$$$
• The $$$i$$$-th child got some apples from the ($$$i - 1$$$)-th child. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took a single pile and gave the remaining ($$$x - 1$$$) piles to the ($$$i + 1$$$)-th child.
• $$$\cdots$$$
• The last child got some apples from the Penultimate child, Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took a single pile and go away.

It should be noted that the number of apples in a pile taken by last child must be a positive integer.

Until the last child go away, Hsueh- wants to know what is a valid $$$n$$$ that meets all requirements.

For instance, we consider $$$m = 2$$$ and $$$x = 3$$$, a valid answer is $$$n = 7$$$.

• The first child got $$$7$$$ apples. Next, he ate an apple and the remaining $$$6$$$ apples could just be divided into $$$3$$$ piles and $$$2$$$ apples per pile. He took a single pile and gave the remaining $$$2$$$ piles to the second child.
• The second child got $$$4$$$ apples. Next, he ate an apple and the remaining $$$3$$$ apples could just be divided into $$$3$$$ piles and $$$1$$$ apple per pile. He took a single pile and go away.

Hsueh- has a keyboard.

There is a string which has $$$x$$$ characters in the textarea.

At present, Hsueh- wants to see a string of length exactly $$$n$$$ in the textarea.

You can use the following operations to meet Hsueh-'s requirements.

• Strike the keyboard once, enter a character.
• Strike the keyboard twice(Ctrl + A), select all characters in the textarea.
• Strike the keyboard twice(Ctrl + C), copy the selected character to the clipboard.
• Strike the keyboard twice(Ctrl + V), paste the characters which in the clipboard(Do not empty the clipboard).
• Strike the keyboard once(Backspace), delete character at the end of the textarea or delete the selected character if some characters are selected.

Hsueh- wants to know the minimum number of strokes required to see a string of length exactly $$$n$$$ in the textarea.

What is different from your traditional perception is, if you press Ctrl + A to select all characters and then enter a character or paste some characters, the selected characters will not be deleted. In other words, if you select all characters in the textarea and then enter a character or paste some characters, it will not replace the selected characters but append the characters you enter or paste at the end.

In another parallel world, ltslts is a fantastic engineer, he build $$$n$$$ rectangular rooms, numbered from $$$1$$$ to $$$n$$$. From a bird's-eye view, the rooms are arranged on a 2-dimensional plane, with axis-aligned. The southern wall of each room has y-coordinate 0.

The $$$i$$$-th rectangular room has southwest corner $$$(L_i, 0)$$$ and the northeast corner $$$(R_i, H_i)$$$. Since houses often have shared regions (such as a common living/dining area), these rooms may overlap with one another. Due to these houses are built on the mountain, the height of these houses is decreasing.

Specifically, let $$$P_i$$$ be the area of the union of rooms $$$1 \cdots i$$$. Note that the area of the overlap only needs to be calculated once, and that the union might not form a single connected polygon.

Although ltslts is a fantastic engineer, his mathematical ability is very poor. Please help compute the product $$$(P_1 \times P_2 \times P_3 \times \cdots \times P_n)$$$. As this product may be very large, you need compute its value module $$$998244353$$$.

Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

It you don't know what is rectangular area union, you just need to remember, the area of the overlap only needs to be calculated once.

For instance, let's consider $$$(L_i, R_i, H_i)$$$ to representing a rectangular, if we have two rectangulars $$$(1, 3, 5)$$$ and $$$(2, 4, 5)$$$, the rectangular area union is $$$15$$$, because the area $$$(2, 3, 5)$$$ is overlap area, just need to calculate once.

The difference between this problem and LTS owns large quantities of apples is more than the data range, please read the statement carefully.

There are $$$n$$$ apples in Hsueh-'s bag, and $$$m$$$ kids around the man. Let's label these children $$$1$$$ to $$$m$$$.

Hsueh- take all of the apples and gave to the first child.

• The first child got $$$n$$$ apples from Hsueh-. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took the $$$x - 1$$$ piles and gave the remaining pile to the second child.
• The second child got $$$\displaystyle \frac{(n - 1)}{x}$$$ apples from the first child. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took the $$$x - 1$$$ piles and gave the remaining pile to the third child.
• $$$\cdots$$$
• The $$$i$$$-th child got some apples from the ($$$i - 1$$$)-th child. Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took the $$$x - 1$$$ piles and gave the remaining pile to the ($$$i + 1$$$)-th child.
• $$$\cdots$$$
• The last child got some apples from the Penultimate child, Next, he ate an apple and the remaining apples could just be divided into $$$x$$$ piles. He took $$$x - 1$$$ piles and go away.

It should be noted that the number of apples in a pile left by last child must be a positive integer.

Until the last child go away, Hsueh- wants to know what is the minimum $$$n$$$ that meets all requirements.

Since $$$n$$$ can be very large, output $$$n$$$ modulo $$$998244353$$$. Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

On a sunny afternoon, ltslts' friends came to visit him. So he decided to buy some wine.

All the wine in the store are known to be on the same shelf, these wine are numbered $$$1$$$ through $$$n$$$ from left to right.

ltslts' friends is very wealthy, so ltslts will buy all the wine. But his drinking capacity is limited, so he only buys a bottle of wine every day.

As we all konw, the longer the wine, the more valuable it is.

In the first, the $$$i$$$-th bottle of wine has a value $$$v_i$$$. On the $$$t$$$-th day, ltslts will buy a bottle of wine on the far left or right side of the shelf, and get the value $$$v_i \cdot t$$$.

Obviously, all the wine will be bought by ltslts on the $$$n$$$-th day, and he wants to know what the maximum value he could get.

For instance, we consider $$$n = 5$$$, and the value of wine are $$$\{1, 3, 1, 5, 2\}$$$.

• On the first day, we buy the wine on the far left and got $$$1$$$ value point, the remaining wine are $$$\{3, 1, 5, 2\}$$$.
• On the second day, we buy the wine on the far right and got $$$4$$$ value point, the remaining wine are $$$\{3, 1, 5\}$$$.
• On the third day, we buy the wine on the far left and got $$$9$$$ value point, the remaining wine are $$$\{1, 5\}$$$.
• On the fourth day, we buy the wine on the far left and got $$$4$$$ value point, the remaining wine are $$$\{5\}$$$.
• On the final day, we got $$$25$$$ value point, and we got a total of $$$43$$$ value point.

We have learned your team is good at geometry problems. So we ask you a simple problem.

Now you have two segments in a $$$2$$$-dimensional plane, you should tell us the length of the intersection of two line segments.

What you need to pay attention to is, if these two line segments intersect at one point, we consider their intersecting length to be $$$0$$$.

Hello everyone! I am your old friend Rikka. Welcome to Hangzhou Normal U. This is an interesting problem, which is problem about the Graph. I promise you all that this should be easiest problem for most people.

A random graph, or a random directed graph, is a graph which edges generated by randomly.

In this problem, we constructed a directed graph by randomly, you need to design a special data structure to support the following operations:

• $$$u \; v$$$, query weather point $$$u$$$ can reach point $$$v$$$ through some edges.

If you are Candidate Master or Master or Grandmaster or Legendary Grandmaster or high level title in Programming competition, you will find that this problem is very easy to solve. Even this problem can be solved on any category of graph. Don't even care of this graph is randomly generated.

So in order to reflect your programming ability, you need to answer these queries online.

To decrease the size of the input, Rikka provides an directed graph via a random number generator with given random seeds , denoted by two integers $$$k_1$$$ and $$$k_2$$$, Supposing the number of vertices and edges in the graph are $$$n$$$ and $$$m$$$ respectively, the following code in C++ tells you how to generate the graph and store the $$$i$$$-th directed edge between the vertex $$$u[i]$$$ and $$$v[i]$$$ in corresponding arrays. You can use the code directly in your submissions.

Initially, you will get the $$$n, m, q, k_1, k_2$$$ and the first queries.

You need to answer the $$$i$$$-th queries correctly before the $$$(i + 1)$$$-th queries will be given to you.

If your answer is legal, Jury will return the next querires to you or terminate the program if the answer is last answer.

If Jury return $$$-1$$$ instead of a next queries, that means you made an invalid answer.

Exit immediately after receiving $$$-1$$$ and you will see wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a answer, do not forget to output end of line and flush the output. Otherwise, you will get idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• See the documentation for other languages.