Given $$$n$$$ functions $$$f_1(x), f_2(x), \cdots, f_n(x)$$$, where $$$$$$ f_i(x) = \left\{ \begin{aligned} |\arctan(k_i\sec(x - a_i))| \; & \; (x \neq a_i + (k+\frac{1}{2})\pi \, (k = 0, \pm 1, \pm 2, \cdots)) \\ \frac{\pi}{2} \; & \; (x = a_i + (k+\frac{1}{2})\pi \, (k = 0, \pm 1, \pm 2, \cdots)) \end{aligned} \right. $$$$$$

For each function $$$f_i(x)$$$, determine if there is an $$$x_i$$$ that $$$\forall j \in \{1, 2, \cdots, i-1, i+1, \cdots, n\}, f_i(x_i) \lt f_j(x_i)$$$.

Note that:

• "$$$\arctan$$$" is the inverse function of "$$$\tan$$$".
• $$$\sec (x) = \frac{1}{\cos(x)}$$$.

Given a permutation $$$P$$$ of $$$\{1,2,\cdots, n\}$$$, determine the number of $$$\{1,2,\cdots, n\}$$$ permutations $$$Q$$$ satisfying that $$$\forall i \in \{1, 2, \cdots, n - 1\}, Q_{i+1} \neq P_{Q_i}$$$. Output the number modulo $$$998244353$$$.

As for a 01-matrix(whose entries are all either 0 or 1, similarly hereinafter) $$$M$$$ of size $$$n\times m$$$, an index set $$$S$$$ of the matrix is considered good if following two conditions are satisfied:

1. $$$M_{u,v}=0$$$, for all $$$(u,v)\in S$$$
2. For each entry $$$M_{i,j}=0(1\le i \le n,1\le j\le m)$$$, there exists an index $$$(u,v)\in S$$$ satisfying the following two conditions at the same time:
   • $$$i=u$$$ or $$$j=v$$$
   • $$$M_{x,y}=0$$$ for all $$$x,y$$$ such that $$$(x-i)(x-u)\le 0$$$ and $$$(y-j)(y-v)\le 0$$$

Moreover, the value of a 01-matrix is the minimum size among all of its good index sets.

Now given a 012-matrix, you should replace all the 2 entries to 0 or 1, and determine the minimum possible value among all replacing schemes. As can be seen, there are totally $$$2^{cnt_2}$$$ replacing schemes, where $$$cnt_2$$$ denotes the number of 2 entries in the given matrix.

Given a positive fraction $$$\frac{p}{q}$$$, you should find two positive integers $$$a,b$$$ that $$$\frac{p}{q} = \frac{a}{b} + \frac{b}{a}$$$. If no such integers, report it.

Given $$$n$$$ integers $$$A_1, A_2, \cdots, A_n$$$ and a parameter $$$k$$$, you should choose some integers $$$A_{b_1}, A_{b_2}, \cdots, A_{b_m} \, (1 \le b_1 \lt b_2 \lt \cdots \lt b_m \le n)$$$ so that $$$\forall 1 \le i \lt j \le m, |A_{b_i} - A_{b_j}| \ge k$$$. Determine the maximum number of the integers you can choose.

Itou Kaiji, a smart gambler, lost all his money once again and owed Hyodo Kazutaka a huge sum of money, who is very cruel and proposes a game to bet on Kaiji's four fingers!

Hyodo has a box with $$$n$$$ nearly identical balls in it, where the $$$i$$$-th ball has an integer number $$$a_i(1\le i \le n)$$$ on it, which is the only difference among the balls. At the first, Kaiji will be blindfolded, which means that he cannot see anything, then Hyodo will arbitrarily choose two close balls(Formally, assuming that the two chosen balls are $$$i$$$ and $$$j$$$, there is no $$$k$$$ that $$$(a_i-a_k)(a_j-a_k) \lt 0$$$), take them out of the box and put them into Kaiji's two hands. After that, Kaiji has to say "left hand" or "right hand", and Hyodo will tell him the number on the ball in the claimed hand. Finally, the most important part, Kaiji will answer the size relationship(greater than, less than, or equal to) between the told number and the number on the ball in the other hand. If Kaiji's answer is correct, he will be forgiven the debt, or he will lose his life.

Now, Kaiji needs your help, he wants to know the highest winning probability that can be guaranteed no matter what Hyodo's strategy is.

Note Kaiji will know all the numbers on balls and the whole rule before he is blindfolded.

Given an undirected connected graph of $$$n$$$ vertices and $$$n-1$$$ edges, where $$$n$$$ is guaranteed to be odd. You want to divide all the $$$n-1$$$ edges to $$$\frac{n-1}{2}$$$ groups under following constraints:

• There are exactly 2 edges in each group
• The 2 edges in the same group share a common vertex

Determine the number of valid dividing schemes modulo $$$998244353$$$. Two schemes are considered different if there are 2 edges that are in the same group in one scheme but not in the same group in the other scheme.

Life is a game.

The world can be regarded as an undirected connected graph of $$$n$$$ cities and $$$m$$$ undirected roads between the cities. Now you, the life game player, are going to play the life game on the world graph.

Initially, you are at the $$$x$$$-th city and of $$$k$$$ social ability points. You can earn social ability points by living and working. Specifically, you can earn $$$a_i$$$ social ability points by living and working in the $$$i$$$-th city. But in this problem, you cannot earn social ability points duplicatedly in one city, so you want to travel the world and earn more social ability points. However, the roads are not easy. Specifically, there is an ability threshold $$$w_i$$$ for the $$$i$$$-th road, you should be of at least $$$w_i$$$ social ability points to go through the road. Moreover, Your social ability point will not decrease when passing roads but just need to be at least $$$w_i$$$ if you want to go through the $$$i$$$-th road.

So as you can see, the life game is just living, working and traveling repeatedly. There are $$$q$$$ game saves. For each game save, the initial city and social ability point is given and the player has not lived or worked in any city. Now you, the real life game player, need to determine the maximum possible number of social ability points you can have in the end of the game and output it for each given game save.

Alice enjoys playing a card game called Steadily Growing Steam (as known as SGS).

In this game, each player will play different roles and have different skills. Players get cards from the deck and use them to play the game. Each card has a numeric label $$$t_i$$$, the point number. In addition, each card has a value $$$v_i$$$.

Now Alice is playing this game with Bob. According to the skill of Alice's role, she can have Bob display $$$n$$$ cards from the top of the deck. After that, Bob must choose some cards from the $$$n$$$ cards and split the chosen cards into two sets that the sum of the cards' point numbers in the two sets are equal. In other words, if one of the sets is $$$S$$$ and another is $$$T$$$ , $$$S\cap T=\emptyset$$$ and $$$\sum_{i\in S} t_i=\sum _{j\in T}t_j$$$ (Note that $$$S\cup T = \{1,2,\cdots n\}$$$ is not necessary). Then, Alice gets all of the cards in set $$$S$$$ and Bob gets the cards in set $$$T$$$.

However, according to the skill of Bob's role, before choosing the two sets, he can choose at most $$$k$$$ different cards and double their point numbers. In other words, he can choose a sequence $$$\{a_1,a_2,\cdots,a_r\},\,(1\le a_1 \lt a_2 \lt \cdots \lt a_r\le n,\, 0\le r\le k)$$$ and for each $$$i\,(1\le i \le r)$$$ , change $$$t_{a_i}$$$ into $$$2t_{a_i}$$$. After that he can continue choosing the two sets.

Alice and Bob are partners in this game. Now given the $$$n$$$ cards from the deck, they want to know the maximum possible sum of the values of the cards they finally get. In other words, determine the maximum $$$\sum_{i\in S \cup T}v_i$$$ among all valid schemes(choose cards to double their point numbers, then choose cards and split them into two sets $$$S,T$$$ of the same point number sum) and output it.

Given an integer $$$n$$$ and two binary strings $$$a_1a_2\cdots a_n$$$ (denoted by $$$A$$$) and $$$b_1b_2\cdots b_n$$$ (denoted by $$$B$$$) of length $$$n$$$.

Define function: $$$$$$ f(l,r)=\begin{cases} 1,& \text{if}\;\sum\limits_{i=l}^r a_i \gt \frac{r-l+1}{2} \\ 0,&\text{otherwise}

\end{cases} $$$$$$

We say an integer $$$k$$$ is lucky, iff for each $$$i\,(1\le i \le n)$$$, $$$f\big(\max(i-k+1,1),i \big)=b_i$$$ holds.

For each integer $$$k\,(1\le k \le n)$$$, determine if it is lucky.

Your friend Lucky is a little elf. Recently, Lucky discovered a magical creature, she named them "Twinkle". Lucky has a magical chain of $$$n$$$ vertices and $$$n-1$$$ edges, where the vertices are connected by the edges one by one. We assume that the vertices are numbered $$$1$$$ to $$$n$$$ from left to right, and the $$$i$$$-th edge connects vertex $$$i$$$ and vertex $$$i+1$$$. She found that Twinkles could live in the magical chain.

Lucky can put some Twinkles on some vertices simultaneously with her magic, but there should be at most one Twinkle in one vertex since the near Twinkles will perish together. Then, every second, each Twinkle will split into two Twinkles simultaneously and they will dash in the opposite directions to the two adjacent vertices.

Formally, a Twinkle in vertex $$$u$$$ splits into two Twinkles, the left splited Twinkle and the right splited Twinkle.

• The left splited Twinkle will dash toward the left and reach the vertex $$$u-1$$$.
• The right splited Twinkle will dash toward the right and reach the vertex $$$u+1$$$.

But unluckily, if one side has no vertex, the Twinkle will dash out of the chain and die out(for the left splited Twinkle in vertex $$$1$$$ and the right splited Twinkle in vertex $$$n$$$). Much more unfortunately, if two Twinkles dash to have a head-on collision (i.e. meet in the same vertex or edge), they will perish together with a tearing crash! Specifically, a crash will happen in two situations:

1. The right splited Twinkle in vertex $$$i$$$ and the left splited Twinkle in vertex $$$i+2$$$ will crash in vertex $$$i+1$$$(assuming that vertex $$$i+1$$$ lives no Twinkle).
2. The right splited Twinkle in vertex $$$i$$$ and the left splited Twinkle in vertex $$$i+1$$$ will crash in the $$$i$$$-th edge.

Lucky hopes there's always some Twinkle living on the chain. In addition, in order to be more convenient for Lucky to check the validity, there should be duplicated configurations within $$$2n$$$ seconds. Specifically, a configuration can be denoted by a binary string $$$S$$$ of length $$$n$$$, where $$$S_i = 1$$$ iff vertex $$$i$$$ lives a Twinkle, and $$$C_i$$$ denotes the configuration after $$$i$$$ seconds. Your task is to find an initial configuration $$$C_0$$$ so that for each $$$i\,(0\le i \le 2n), C_i \neq 00\cdots00$$$ and that there exist two integers $$$i,j\,(0\le i \lt j \le 2n), C_i = C_j$$$.

A poor little penguin has been thrown by a killer whale for a distance of one hundred and eight thousand li. The poor little penguin found itself on a mysterious island then. On the ground there are many graphs. The poor little penguin found that all the vertices are of degree three. "The Dao produced One; One produced Two; Two produced Three; Three produced All things", the poor little penguin recalled this mystical sentence. Suddenly, a quill-pen came into view. A sound said, "Every time you dip the quill-pen in the sea, you can one-touch-draw three edges. That is, you can start at a vertex, pass three different edges to a vertex." It is a parrot with three golden feathers on top of its head, "If all edges of a graph could be drawn once and only once by this way, then we call it a Three-throwable graph. You should find all the Three-throwable graphs, and show me how to throw three! As soon as you're done, I will bestow you the Produced-All-Things Power and send you back to avenge yourself on the killer whale!"

Too many graphs! So the poor little penguin asks you three for help. Please help it, for Light and Justice.

In short, given a graph of $$$n$$$ vertices and $$$m$$$ edges, where $$$n$$$ is even and all the vertices are of degree 3. So it can be seen that $$$m = \frac{3n}{2}$$$ and that $$$m$$$ is multiple of 3. You should try to split the graph into $$$\frac{m}{3}$$$ chains of length 3. Determine if the graph is Three-throwable graph(such chain spliting scheme exists) and output the splited chains if solution exists.

Haha is a humorous god of harmony. Why do I say that? In fact, Haha is forgetful, but Haha thinks that he has an excellent memory. Haha is responsible for balancing the power of various elements in the world. The power is derived from harmony fruits which grow in Hahiland. There are $$$n$$$ tribes in Hahiland, each takes charge of one element, such as fire, water, etc. There is a fertile field in Hahiland, where the soil is suitable for growing the harmony fruits.

Every spring, Haha will divide the field into $$$n$$$ parts, and each part is of the same total area. Then every tribe will choose one part to be their territory, then sow the harmony seeds on it, and give some element power to the seeds. Although the element power helps the plants to grow well, when the fruits are ripe, they could only be harvested by the one who has the same kind of element power.

"My memory is very good. I don't need to record my divide plan at all! These are all in my brain clearly!" Haha said with full confidence. As autumn comes, Haha divides the field into $$$n$$$ parts again from his memory. But it's actually not the same as last time. People are afraid to tell the harmony god that he is wrong. So they discuss how to allot the $$$n$$$ parts in order to guarantee the minimum area of plants each tribe could harvest to be as large as possible.

The members of Hahiland are wondering how large the minimum area of plants each tribe could harvest could be guaranteed no matter how Haha divides the field, for their future generations. Please calculate it with your wisdom, so that they will be not so anxious.

In short, given $$$n$$$, determine: $$$$$$\min\limits_{S, A}\{\max\limits_{p}\{\min\limits_{i=1}^{n}\{|S_i\cap A_{p_i}| \}\}\}$$$$$$ , where $$$S, A$$$ denote the field parts(the whole field and the parts can be denoted by some areas in 2D plane) divided in spring and autumn respectively(so $$$|S_1| = |S_2| = \cdots = |S_n| = |A_1| = |A_2| = \cdots = |A_n|$$$ holds), $$$p$$$ denotes a permutation of $$$\{1,2,\cdots,n\}$$$(so $$$\{p_1, p_2, \cdots, p_n\} = \{1, 2, \cdots, n\}$$$ holds).

Moreover, assume the total area of the whole field is 1 and the shape of the whole field doesn't count in this problem as can be seen.