OLO's global tournament, ISM, is in full swing and Shizuku is a big fan of GNR which is taking part in the tournament. OLO is a game where two teams of five players play against each other. PENTA KILL is considered an unbelievable achievement in the game, which means one player kills five pairwise distinct opponents in a row. We assume that a player will be resurrected immediately after his death, and the death will not affect the verdict of his PENTA KILL.

Normally, PENTA KILL will be displayed in the game. However, sometimes due to unintended disparity in latency between competing teams, it is not displayed properly in the game. After the game, Shizuku gets a chronological list of kills during the game. She wants to know whether a player has achieved PENTA KILL in this game.

Yukikaze is studying number theory. She wonders whether she can arrange all positive integers between $$$1$$$ and $$$n$$$ ($$$n$$$ is a positive even integer) into several disjoint cycles such that each cycle contains at least three integers, and the sum of any two adjacent integers is a prime number in any cycle.

Prime numbers are integers greater than $$$1$$$ and cannot be exactly divided by any positive integer other than itself and $$$1$$$.

Formally speaking, Yukikaze wants to find $$$k$$$ sequences $$$A_1, A_2, \ldots, A_k$$$ that satisfy the following conditions:

1. Each sequence contains at least three integers.
2. Each integer between $$$1$$$ and $$$n$$$ appears in exactly one sequence.
3. For any sequence $$$A_i = \{ a_{i,1}, a_{i,2}, \ldots, a_{i,l} \}$$$, $$$a_{i,j}+a_{i,j+1}$$$ is a prime number for any $$$1 \leq j \lt l$$$, and $$$a_{i,1}+a_{i,l}$$$ must be a prime number too.

Tom likes playing a video game recently. The rules of this game are as follows. The game is played on an $$$x$$$-axis. There are a total of $$$n+1$$$ pillars in the game, which are arranged in a row from left to right. The pillars are numbered from $$$0$$$ to $$$n$$$. The coordinate of the pillar numbered $$$i$$$ is $$$x=i$$$. There is also an infinite platform in the game in the range of $$$[n+1,+\infty)$$$. Players can win by jumping to any position within this range.

Players start from the pillar numbered $$$0$$$ and can only jump from left to right, i.e. the coordinates must increase. And he can only jump on the pillars or the platform, otherwise, he will fall into the void and fail the game. In addition, his jumping ability is limited, and the distance of each jump does not exceed $$$p$$$.

Except for the pillar numbered $$$0$$$, there will be a treasure chest on each remaining pillar. The treasure chest on the pillar numbered $$$i$$$ will have $$$a_{i} $$$ gold coins. However, there are some trap chests ($$$a_{i} \lt 0$$$) where he will lose $$$|a_{i}|$$$ gold coins.

This game has $$$n$$$ levels. Tom can only jump to the pillars numbered with multiples of $$$i$$$ in the $$$i$$$-th level. Now there are $$$q$$$ queries, each of which contains a number $$$x$$$, asking the maximum number of gold coins Tom can get when he wins at level $$$x$$$. It's possible that Tom opens too many trap chests on the way and gets negative gold coins.

You are given three integers $$$n$$$, $$$k$$$ and $$$q$$$ along with a sequence $$$a_1,a_2,...,a_n$$$. You have to process $$$q$$$ queries.

For each query, you will be given two integers $$$l$$$, $$$r$$$. Then, you should find a sequence of length $$$2m$$$ that consists of pairwise distinct integers, denoted as $$$b_1,b_2,...,b_{2m}$$$, such that $$$l\leq b_1,b_2,...,b_{2m}\leq r$$$, and for each $$$i\in [1,m]$$$, $$$|b_{2i-1}-b_{2i}|=k$$$. $$$m$$$ is a non-negative integer determined by you. Among all the valid sequences, you should find the maximum value of $$$a_{b_1}+a_{b_2}+...+a_{b_{2m}}$$$, and output it for each query.

Alice and Bob are playing cards. Each of them has been given $$$n$$$ cards with a number on each card. They will play the cards for $$$n$$$ rounds, and in each round, each player will play a card that hasn't been played before. After both Alice and Bob play a card in a round, they will compare the number written on the cards, and the person who plays a card with a larger number will win this round. In the case that the numbers written on two cards are exactly the same, this round will be a draw.

Alice has a very strong competitive heart. She doesn't want to lose in any round. If in any round she discovered that the number on the card played by her is smaller than the one played by Bob, she will cheat several times. Cheating once, she can increase the number written on her card by $$$k$$$, and she will keep cheating in a round until the number on her card is not smaller than the number on Bob's card.

However, cheating is very risky, therefore she wants to minimize the times of cheating. To achieve that, she managed to know the sequence of cards that will be played by Bob, and she can determine the order to play the cards in her hands. Please help her calculate the minimum cheating times.

Formally, we can denote the cards in Alice's hands by $$$a_1,a_2,\ldots,a_n$$$, and denote the sequence of cards that will be played by Bob by $$$b_1,b_2,\ldots,b_n$$$. You should find a permutation of $$$n$$$ denoted by $$$c_1,c_2,\ldots,c_n$$$, such that

$$$$$$ \sum\limits_{i=1}^n\left\lceil \frac{\max(b_i-a_{c_i},0)}k\right\rceil $$$$$$

is minimized. You should output the minimized value and a possible sequence $$$c_1,c_2,\ldots,c_n$$$.

Luna is shopping at a magic shop, where $$$n$$$ kinds of items are on sale. The value of the $$$i$$$-th kind of item is $$$v_i$$$, and the weight is $$$w_i$$$. The number of items is infinity. Luna's pocket can carry items with a total weight of no more than $$$k$$$. Each time, Luna can take one item of any kind. She can take at most $$$m$$$ times.

In order to take more items, Luna uses magic so that if the number of items she buys is $$$i$$$, she can carry a total weight of at most $$$i+k$$$. Her happiness of shopping is the product of the value over all the items she buys. If she buys nothing, the happiness is $$$1$$$.

There are many ways to buy items, and she wants to know the sum of happiness of all the possible ways of shopping. Since the number can be very large, just tell her the number modulo $$$998244353$$$.

Two ways of shopping are considered different if the number of times to take items are different or she takes a different kind of item at one time.

Given a full bipartite graph with $$$n$$$ nodes on the left and $$$m$$$ nodes on the right where any node on the left is connected to all nodes on the right. Your task is now to assign values to the nodes such that any integer $$$i \in [1,n+m]$$$ occurs exactly once and that for any cycle, the GCD (Greatest Common Divisor) of the values of all the nodes on the cycle is equal to $$$1$$$.

The GCD of some positive integers is the maximum integer that divides all the integers. For example, $$$\text{GCD}(4,6)=2$$$, $$$\text{GCD}(6,9,15)=3$$$.

Ponyville is on its annual math festival! The ponies who are able to overcome this problem would be honored as $$$\text{Super Gray Pony}$$$. Get yourself prepared for the problem and try your best!

In this problem, the $$$i$$$-order Gray Code is defined recursively as $$$a^{(i)}$$$ - an array of binary numbers with $$$2^i$$$ elements numbered from $$$0$$$ to $$$2^i-1$$$. Note that in this problem leading zeros are added to make each element a strictly $$$i$$$-bit binary number. The specific rules are as follows:

1. For $$$i = 1$$$, $$$a^{(1)}=[0,1]$$$, $$$a^{(1)}[0]=0$$$, $$$a^{(1)}[1]=1$$$.
2. For $$$i \gt 1$$$, the first half of $$$a^{(i)}$$$ $$$(a^{(i)}[0], ..., a^{(i)}[2^{i - 1} - 1])$$$ can be obtained by adding a digit $$$0$$$ in front of the highest bit of each element in $$$a^{(i-1)}$$$.
3. For $$$i \gt 1$$$, the second half of $$$a^{(i)}$$$ $$$(a^{(i)}[2^{i - 1}], ..., a^{(i)}[2^{i} - 1])$$$ can be obtained by adding a digit $$$1$$$ in front of the highest bit of each element in $$$a^{(i-1)}$$$ and then arrange these elements in a reversed order.

For example:

• $$$a^{(1)}=[0,1]$$$
• $$$a^{(2)}=[00, 01] + \text{rev}([10, 11])=[00, 01, 11, 10]$$$
• $$$a^{(3)}=[000, 001, 011, 010] + \text{rev}([100, 101, 111, 110])=[000, 001, 011, 010, 110, 111, 101, 100]$$$

Given $$$S$$$ and $$$k$$$, $$$S_k$$$ is defined as:

$$$$$$ S_k=\underbrace{a^{(n)}[a^{(n)}[\ldots a^{(n)}}_{k \times a^{(n)}}[S]\ldots ]] $$$$$$

Now given $$$S$$$ and $$$k$$$, you need to calculate the exact value of $$$S_k$$$. In this problem, $$$S$$$ is given in the form of an $$$n$$$-bit binary number, possibly with leading zeros.

Given a string $$$S$$$ of length $$$n$$$ consisting of lowercase English characters. We denote $$$\text{Suffix}_i$$$ as the suffix of $$$S$$$ starting from the $$$i$$$-th character. We define $$$w_{i,j}$$$ as the length of the LCP of $$$\text{Suffix}_i$$$ and $$$\text{Suffix}_j$$$. LCP is the longest common prefix of two strings. For example, the LCP of $$$\texttt{abca}$$$ and $$$\texttt{abd}$$$ is $$$\texttt{ab}$$$.

You should divide the integers from $$$1$$$ to $$$n$$$ into two non-empty complementary sets $$$T_1, T_2$$$. We define the value of this partition as follows.

$$$$$$ \sum\limits_{i\in T_1}\sum\limits_{j\in T_2}w_{i,j} $$$$$$

Please find a partition to minimize the value.

A binary tree $$$T$$$ is called super balanced if $$$T$$$ is empty or satisfies the following three conditions at the same time:

1. The left subtree of $$$T$$$ is super balanced.
2. The right subtree of $$$T$$$ is super balanced.
3. The number of nodes of the left subtree and the right subtree differs at most $$$1$$$.

Please calculate the number of super balanced trees consisting of $$$n$$$ nodes. Since the answer can be very large, just output the answer modulo $$$2^{64}$$$.

Vasily Tadokorov is a stringologist. He thinks a string is fragrant if it can be divided into two parts: nunhehheh as the prefix and a number of (excluding $$$0$$$) a as the suffix. For example, nunhehhehaaaaaa is fragrant, but nunhehheh and nunhehhehoooaaa are not fragrant.

Today Vasily Tadokorov has some strings consisting of lowercase English letters. For each string, he wants to know how many subsequences of this string are fragrant. A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (including $$$0$$$) characters.

The above is a problem of string that Vasily came up with. As we know, a problem usually has several examples for better understanding. However, Vasily gets buried in making some fragrant examples. After 2000 years, he finally makes two perfect examples as follows.

Example 1:

• Input: $$$\texttt{nunhehhehahaahahahahahahaahaahahahahha}$$$
• Output: $$$\text{114514}$$$

Example 2:

• Input: $$$\texttt{nunhehhehhehhahaahahahaahaahahaaaahaa}$$$
• Output: $$$\text{1919810}$$$

Vasily is not clever enough. He doesn't want to work for another 2000 years, so he asks you for help. He gives you $$$T$$$ tasks, each of which contains an integer $$$n$$$, and you should construct a string consisting of only lowercase English letters that has exactly $$$n$$$ fragrant subsequences.

Our best explorer, Vingying, finds a deep cave that is full of diamonds! Well, he is a very careful man, so he decides to do some research before collecting them.

The diamonds can be divided into three kinds, noted as $$$\text{A,B,C}$$$ for convenience. There are a total of $$$n$$$ diamonds in a row, which can be regarded as a sequence $$$s_1,s_2,\dots,s_n$$$ from left to right. Vingying will perform the operation several times, which consists of the following three steps in order.

1. Choose an index $$$i$$$ ($$$1\le i \le n - 2$$$) satisfying $$$s_i = \text{A}$$$, $$$s_{i+1}=\text{B}$$$, $$$s_{i+2}=\text{C}$$$.
2. If the index is odd, then collect $$$s_i$$$ and $$$s_{i+2}$$$; otherwise, collect $$$s_{i+1}$$$.
3. Update $$$n$$$ to the number of diamonds left and reindex the diamonds.

For example, $$$s=\text{ABCABC}$$$. We can choose index $$$1$$$ and collect $$$1,3$$$, then $$$s$$$ becomes $$$\text{BABC}$$$ indexed $$$1,2,3,4$$$. But if we choose index $$$4$$$ and collect $$$5$$$, then $$$s$$$ becomes $$$\text{ABCAC}$$$ indexed $$$1,2,3,4,5$$$.

Vingying wants to know the maximum number of operations (not the diamonds) he can do.