There is a connected graph with $$$n$$$ vertices and $$$m$$$ undirected edges.

You are given $$$Q$$$ queries, each containing $$$4$$$ integers $$$u,v,x,y$$$. For each query, you need to find one path from $$$u$$$ to $$$x$$$ and another from $$$v$$$ to $$$y$$$, or one path from $$$u$$$ to $$$y$$$ and another from $$$v$$$ to $$$x$$$, so that the common edges between these two paths is the least.

Walk_alone is anxious to prepare for a programming contest, and he has ideas for $$$n$$$ problems now. Preparing a problem from scratch requires two jobs: making and validating. He asked $$$m$$$ people to help him with these two jobs.

All these $$$m$$$ people are skilled at making and validating problems, and each person needs exactly $$$1$$$ hour to do one of these two jobs. A job should be done by only one person without interruption (but making and validating one problem can be done by two different people), and a problem must be made before validated. Now Walk_alone wants to know the minimum hours to prepare for the contest if he arranges everyone's job properly.

You are given an integer $$$n$$$ and a set $$$S\subseteq\{0,1,\dots,n-1\}$$$ with $$$m$$$ integers. A graph with $$$2^n$$$ vertices labelled from $$$0$$$ to $$$2^n-1$$$ is built in the following way: for each $$$s\in S$$$ and $$$i\in \{0,1,\dots,2^n-1\}$$$, connect vertex $$$i$$$ and $$$(i+2^s)\text{ mod }2^n$$$ with an undirected edge of length $$$1$$$.

Let $$$d_{i,j}$$$ be the distance between vertex $$$i$$$ and $$$j$$$, and you need to answer:

• The diameter of the graph (i.e., $$$\max_{0\le i\le j \lt 2^n}d_{i,j}$$$) modulo $$$998\,244\,353$$$;
• The number of pairs $$$(i,j)\ (0\le i\le j \lt 2^n)$$$ such that $$$d_{i,j}=\max_{0\le x\le y \lt 2^n}d_{x,y}$$$ modulo $$$998\,244\,353$$$.

It is guaranteed that the graph is connected.

Walk_alone has a sequence $$$a$$$ of length $$$n$$$, he defines function $$$f$$$ as $$$$$$ f(l,r)=\big(\max_{l \leq i \leq r} a_i -\min_{l \leq i \leq r}a_i\big)(r-l+1) $$$$$$

He thinks that calculating the value of the function to a given interval is too boring, so he wants you to output the $$$k$$$-th largest value of the function among all $$$f(l,r)$$$ where $$$1 \leq l \leq r \leq n$$$.

There are $$$n$$$ points $$$P_0,P_1,\dots,P_{n-1}$$$ on a plane, and the coordinates of $$$P_{i}$$$ are $$$(x_i,y_i)\ (0\le i \lt n)$$$.

Let $$$M=(\sum_{0\le i \lt n} x_i, \sum_{0\le i \lt n} y_i)/n$$$, i.e., the mass center of the initial $$$n$$$ points. The following operations will repeat for $$$k$$$ times:

• For each $$$0\le i \lt n$$$, extend segment $$$MP_i$$$ to $$$Q_i$$$ such that $$$|MP_i|=\cos(2\pi/n)\cdot |MQ_i|$$$.
• Let $$$Q_{-1}=Q_{n-1}$$$ and $$$Q_n=Q_0$$$. For each $$$0\le i \lt n$$$, replace $$$P_i$$$ with $$$R_i$$$, the mass center of $$$\triangle P_iQ_{i-1}Q_{i+1}$$$.

You can see the picture below for better understanding.

Constructing $$$R_i$$$ from $$$P_{i-1}$$$, $$$P_i$$$ and $$$P_{i+1}$$$

Let $$$P'_i=\lim_{k\to\infty} P_i\ (0\le i \lt n)$$$ and $$$P'_n=P'_0$$$. It can be proved that $$$P'_i$$$ will always exist when $$$n\ge 7$$$. Now you need to output the value of

$$$$$$ \sum_{0\le i \lt n} \mathop{MP'_i}^{-\hspace{-2pt}-\hspace{-2pt}-\hspace{-2pt}\rightarrow} \times \mathop{MP'_{i+1}}^{-\hspace{-2pt}-\hspace{-2pt}-\hspace{-2pt}\rightarrow\ \ \ } $$$$$$

P.S. You can try to prove that all $$$P'_i$$$ will be on a certain ellipse though it may have nothing to do with the problem.

Walk_alone hates numbers with large exponents, and he considers an integer $$$x$$$ as good if and only if there does not exist a prime number $$$p$$$, such that $$$x$$$ is a multiple of $$$p^k$$$. He hopes to find the number of all good integers in range $$$[l,r]$$$.

Walk_alone is going to primary school! To train his computing ability, Weierstras gives him a game called Nerdle.

In this game, he should guess an equation of length $$$8$$$, and an equation is valid if and only if it satisfies the following rules:

• The length of the equation is $$$8$$$, and an equation must contain exactly one equal sign ('='). The two sides of the equation (called AddExprs) must be equal;
• An AddExpr consists of one or more MulExprs connected by plus signs ('+') or minus signs ('-');
• A MulExpr consists of one or more Numbers connected by multiple signs ('*') or division signs ('/');
• A Number consists of at most one negative sign ('-') and one or more Digits (leading 0s are allowed in this game, and negative signs can connect directly with minus signs);
• The result of each division must be an integer (for example, expression 5/4*4 is not allowed, even if the final result is an integer).

For example, 5*4/4=05, 1--2=1+2 and -1*-2=02 are all valid equations, but 5/4*4=05, 5/4=10/8, 2+---1=1, 1+2+3=07, +12=10+2 or 1=3-2=01 are not.

Formally speaking, all valid equations must satisfy the following Extended Backus-Naur Form:

Equation := AddExpr '=' AddExpr
AddExpr := MulExpr | AddExpr ('+'|'-') MulExpr
MulExpr := Number | MulExpr ('*'|'/') Number
Number := ['-'] Digit {Digit}
Digit := '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'

Now Walk_alone has a pattern of length $$$8$$$, and he asks you to tell him the number of valid equations satisfying the pattern. The pattern consists only of digits, '+', '-', '*', '/', '=' and '?'. If the $$$i$$$-th character in the pattern is '?', it means the $$$i$$$-th character in the equation is not restricted, otherwise the character must be the same as the pattern.

You are given an integer $$$n$$$, and $$$m$$$ pairs of integers $$$(x_i,y_i)\ (1\le i\le m)$$$ with distinct $$$x_i$$$, i.e. $$$x_i\neq x_j$$$ for all $$$i\neq j$$$. You need to find the number of permutation $$$p$$$ of length $$$n$$$ satisfying $$$p_{x_i} \lt p_{y_i}$$$ for all $$$i$$$. Since the number might be too large, you only need to output the answer modulo $$$998\,244\,353$$$.

Recall that a permutation of length $$$n$$$ is a sequence of length $$$n$$$ and contains $$$1,2,\dots, n$$$ exactly once. For instance, $$$\{1,2,3\}$$$ and $$$\{3,1,2\}$$$ are permutations while $$$\{1,2,4\}$$$ and $$$\{1,2,2\}$$$ are not.

Walk_alone loves repetition! He has a lot to say, and he may repeat some information in every sentence (represented as $$$n$$$ strings $$$S_1,S_2,\dots, S_n$$$) he says. Since such information could be important, his teammates want to extract a substring which appears in every sentence for at least $$$k$$$ times. However, some information (represented as string $$$T$$$) is so sensitive that they would not allow it to appear in the information. It is hard to find out the longest information they can extract, so they ask you for help.

Formally, you are given $$$n$$$ strings $$$S_1,S_2,\dots,S_n$$$ and a pattern $$$T$$$. Your task is to find the length of the longest string which appears in every $$${S}_i\ (1\le i\le n)$$$ for at least $$$k$$$ times, and does not have $$$T$$$ as its continuous substring.

Walk_alone loves sequences. For a sequence $$$a_1,a_2,\dots,a_n$$$ of length $$$n$$$, he defines $$$A_i\ (1\le i \lt n)$$$ as

$$$$$$A_i=\bigoplus_{j=1}^i \bigoplus_{k=i+1}^n a_j \,\&\, a_k$$$$$$

where $$$\&$$$ represents the bitwise AND, and $$$\oplus$$$ means bitwise XOR.

Now Walk_alone has an initially empty sequence. He will do $$$q$$$ operations to this sequence, and there will be two types of operations:

• 1 x: add an element $$$x\ (0\le x \lt 2^{20})$$$ to the back of the sequence.
• 2: output $$$\max_{1\le i \lt n}A_i$$$ where $$$n$$$ is the length of sequence $$$a$$$. The answer is $$$0$$$ if $$$n \lt 2$$$.

Walk_alone has a $$$500\times 500$$$ square grid in a plane. The lower-left corner of the grid locates at $$$(0,0)$$$, and all squares in it are of size $$$1\times 1$$$.

There are $$$n$$$ segments in the grid, the $$$i$$$-th of which connecting point $$$(x_i,y_i)$$$ and $$$(x_i-1,y_i-1)$$$. Now you are required to find out the number of triangles in the grid.

On December 4th, ICPC2021 Nanjing was held. During the contest, Walk_alone (abbr. WA) did nothing but be stuck by Problem D, which was an easy data structure problem with a background of an adapted bubble sort. So he has being scolded by his teammates for a long time for losing a gold medal.

Today, his teammates gave him another adjusted sorting algorithm to help him overcome his psychological shadow. But his dread and fear stops him from even thinking about this problem. Help him solve the problem below to avoid being scolded by his teammates again!

Its pseudo-code is shown below.

Obviously not every sequence can be sorted by this algorithm, but it does not matter, and here comes the question:

Given a permutation $$$A=\{a_1,a_2,\cdots, a_n\}$$$. Let $$$A_k=\{a_1,a_2,\cdots, a_k\}$$$. Your task is to count the total number of times $$$m$$$ is assigned if we call $$${\rm SORT}(A_k)$$$ for every $$$k \ (1 \le k \le n)$$$.

Walk_alone has a sequence $$$a$$$ of length $$$n$$$. He can do the following operations for arbitrary times (possibly zero):

• Select an index $$$x$$$ and an integer $$$y$$$ ($$$1 \leq x \leq n, 0 \leq y \lt 2^{30}$$$);
• For all index $$$i$$$ such that $$$i \neq x$$$, change $$$a_i$$$ to $$$a_i \oplus y$$$, where $$$\oplus$$$ denotes bitwise XOR.

Note that Walk_alone can select different $$$y$$$ in different operations.

Now he wants to know if he can change all numbers in the sequence to $$$0$$$.