The following is the current ranking rules for the ICPC Asia EC Online Qualifiers, and there will be two online contests.

1. In each contest, only the rank of the top-ranked team from each university will be taken as the score of that university;

2. In each contest, participating universities will be ranked according to their scores;

3. The two rankings of universities are combined using the merge sorting method. For any two universities that obtain the same ranking in different contests, the university that received this ranking in the first contest will be ranked first.

4. Delete duplicate universities and obtain the final ranking of all participating universities (only the highest rankings for each university are retained).

Now assuming that there are $$$n$$$ teams in the first contest and $$$m$$$ teams in the second contest.

For each contest, given the ranking of each team and the university to which it belongs, please output the final ranking of all participating universities according to the above rules.

You can better understand this process through the sample.

Given two strings $$$S_1$$$ and $$$S_2$$$ of equal length (indexed from $$$1$$$).

Now you need to answer $$$q$$$ queries, with each query consists of a string $$$T$$$.

The query asks how many triplets of integers $$$(i, j, k)\ (1\le i \le j \lt k\le |S_1|)$$$ satisfy the condition $$$S_1[i,j]+S_2[j+1,k]=T$$$.

Here $$$S[l,r]$$$ denotes the substring of $$$S$$$ with index form $$$l$$$ to $$$r$$$, and "+" denotes concatenation of strings.

Given $$$n$$$ pairs $$$(a_1,b_1),(a_2,b_2),\dots,(a_n,b_n)$$$, you need to perform $$$q$$$ operations. Each operation has one of the following forms:

• "1 $$$k$$$ $$$a$$$ $$$b$$$" ($$$1\leq k\leq n$$$, $$$1 \leq a,b \leq 10^9$$$): Modify the $$$k$$$-th pair into $$$(a,b)$$$.
• "2 $$$x$$$ $$$l$$$ $$$r$$$" ($$$1 \leq x \leq 10^9$$$, $$$1\leq l\leq r\leq n$$$): Find the maximum value of $$$a_i\times x+b_i$$$, where $$$l\leq i\leq r$$$.

Given a simple undirected graph with $$$n$$$ vertices and $$$m$$$ edges, and it's guaranteed that $$$m \lt \frac{n(n-1)}{2}$$$ .

We define an undirected graph to be transitive if and only if for any two different vertices $$$u, v$$$ :

If there exists a path starting from $$$u$$$ and ending at $$$v$$$ in the graph, then there should exists an edge connected $$$u$$$ and $$$v$$$ in the graph.

Now you should add some undirected edges to the graph (add at least one edge). You need to ensure that after adding edges, the graph is still a simple undirected graph and is transitive.

The question is, how many edges need to be added at least?

Recall that a simple undirected graph is an undirected graph that does not have more than one edge between any two vertices and no edge starts and ends at the same vertex.

For a prime number $$$n$$$, if a pair of positive integers $$$(x, y)$$$ satisfies the congruence relation: $$$$$$x^y\equiv y^x \pmod n.$$$$$$ Then we consider $$$(x, y)$$$ to be magical.

We want to know how many ordered pairs of positive integers $$$(x, y)$$$ are magical for a given prime number $$$n$$$, where $$$0 \lt x, y \le n^2 - n$$$. Since the answer could be large, we will output it modulo 998244353.

You are watching Alice and Bob playing a game.

The game is played on an array of length $$$n$$$. Alice and Bob take turns in action, Alice goes first.

In each turn, the current player can select two different numbers $$$a_i$$$ and $$$a_j$$$ in the array, and then change their values. Assume after changes the values of them are $$$a_i'$$$ and $$$a_j'$$$ , then an operation is legal if and only if $$$a_i+a_j=a_i'+a_j'$$$ and $$$|a_i'-a_j'| \lt |a_i-a_j| $$$. Those who cannot perform legal operations lose.

After playing a few games, You decided to help Alice, because Alice, who was always overloaded when faced with a bunch of numbers, always unable to think in front of the genius Bob.

Before the start of each game, You will help Alice remove several numbers (could be $$$0$$$) to reduce the burden on her brain, and you always leave exactly three numbers. And in order to give Alice a greater chance of winning, You will always leave Alice with a winning state, that is, there must be some kind of operating strategy that makes Alice must win no matter how Bob acts.

Now the question is how many ways there are to remove the numbers.

Two ways for removing numbers are considered different if and only if there exists an integer $$$i\ (1\le i\le n)$$$ such that $$$a_i$$$ is not removed in one way and is removed in the other way.

We generate a spanning tree of $$$n$$$ nodes according to the following random process:

Initially, there are no edges connecting the $$$n$$$ nodes.

Then process the following $$$n-1$$$ operations:

• For the $$$i$$$-th operation, two integers $$$a_i$$$ and $$$b_i$$$ will be input, and it's guaranteed that the two nodes are not connected before.
• Select a node $$$u_i$$$ from the connected block where $$$a_i$$$ is located with uniform probability, then select a node $$$v_i$$$ from the connected block where $$$b_i$$$ is located with uniform probability, and then add an edge to connect $$$u_i$$$ and $$$v_i$$$ .

It can be proved that no matter which two nodes are selected in each operation, after all operations are processed, a spanning tree of $$$n$$$ nodes will be formed.

Now given a spanning tree of $$$n$$$ nodes. What is the probability that the spanning tree formed by the random process is exactly this spanning tree?

You only need to output the value of the probability modulo $$$998244353$$$ .

Please note that the probability could be $$$0$$$, which means that you can never generate this spanning tree.

For a string $$$w=w_1w_2\dots w_{len}$$$, we say that an integer $$$p$$$ is a period of $$$w$$$ if $$$w_i = w_{i+p}$$$ holds for all $$$i$$$ ($$$1 \leq i \leq len - p$$$) and $$$1\leq p\leq len$$$.

You will be given a string $$$d=d_1d_2\dots d_n$$$ to generate $$$n+1$$$ strings $$$S_0,S_1,S_2,\dots,S_n$$$, where $$$S_0$$$ is an empty string, and for all $$$i$$$ ($$$1 \leq i \leq n$$$):

• When $$$d_i$$$ is a lowercase English letter, $$$S_i=d_i+S_{i-1}$$$.
• When $$$d_i$$$ is an uppercase English letter, assume its lowercase version is $$$c_i$$$, then $$$S_i=S_{i-1}+c_i$$$.

Here, "+" denotes concatenation of strings.

You will then be given a sequence of integers $$$p_1,p_2,\dots,p_m$$$. You need to answer $$$q$$$ queries, in each query, you will be given three integers $$$k$$$, $$$l$$$ and $$$r$$$. You need to find the minimum number among $$$p_{l},p_{l+1},\dots,p_{r-1},p_r$$$ such that it is a period of string $$$S_k$$$, or determine there is no answer.

You need to log into a mysterious system, but you realize you've forgotten your password. The system does not support resetting password, so the only way to log in is to keep trying.

Fortunately, you still remember some information about the password:

Firstly, you are sure that the length of the password is $$$n$$$ .

Then the information you remember can be described by a string $$$s$$$ of length $$$n$$$.

let $$$s_i$$$ represent the $$$i$$$-th character of $$$s$$$ :

• if $$$s_i$$$ is an uppercase letter or a digital character, then the $$$i$$$-th character of the password must be $$$s_i$$$;
• if $$$s_i$$$ is an lowercase letter, then the $$$i$$$-th character of the password might be $$$s_i$$$ or the uppercase form of $$$s_i$$$;
• if $$$s_i$$$ is a question mark '?' , then the $$$i$$$-th character of the password might be any uppercase letters, lowercase letters, and digital characters.

It's guaranteed that the string $$$s$$$ only contains uppercase letters, lowercase letters, digital characters, and question marks '?'.

In addition, the system also has several requirements for passwords:

• At least one uppercase letter appears in the password;
• At least one lowercase letter appears in the password;
• At least one digital character appears in the password;
• Any two adjacent characters in the password cannot be the same.

Now you want to know, how many possible passwords are there? A possible password should fits both your memory and the system's requirements, and it's guaranteed that there exists at least one possible password.

You know that this answer will be very large, so you just need to calculate the result modulo $$$998244353$$$ .

Please note the unusual memory limit.

Recall that on a two-dimensional plane, the Manhattan distance between two points $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$|x_1-x_2|+|y_1-y_2|$$$. If both coordinates of a point are all integers, then we call this point an integer point.

Given two circles $$$C_1,C_2$$$ on the two-dimensional plane, and guaranteed the $$$x$$$-coordinates of any point in $$$C_1$$$ and any point in $$$C_2$$$ are different, and the $$$y$$$-coordinates of any point in $$$C_1$$$ and any point in $$$C_2$$$ are different.

Each circle is described by two integer points, and the segment connecting the two points represents a diameter of the circle.

Now you need to pick a point $$$(x_0,y_0)$$$ inside or on the $$$C_2$$$ such that minimize the expected value of the Manhattan distance from $$$(x_0,y_0)$$$ to a point inside $$$C_1$$$ , if we choose this point with uniformly probability among all the points with a real number coordinate inside $$$C_1$$$.

One day you are surviving in the wild. After a period of exploration, you determine a safe area, which is a convex hull with $$$n$$$ vertices $$$P_1,P_2,\dots,P_n$$$ in counter-clockwise order and any three of them are not collinear.

Now you are notified that there will be $$$q$$$ airdrop supplies, and for the $$$i$$$-th supply, its delivery range is described by a circle $$$C_i$$$ , which means the supply will landed with uniformly probability among all the points with a real number coordinate inside $$$C_i$$$.

You need supplies so much that you decide to predetermine a starting point for each supply, and the starting point of two different supplies can be different. Every starting point should be inside the safe area and have the smallest expected value of the square of the Euclidean distance to the corresponding supply landing point.

Recall that On a two-dimensional plane, the Euclidean distance between two points $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$$. If both coordinates of a point are all integers, then we call this point an integer point.

Setting the time limit for algorithm competition questions is a very skillful task. If you set the time limit too tight, many people will scold you for being too demanding on details. On the other hand, if you set the time limit too loosely and allow an algorithm with unexpected time complexity to pass, then many people will scold you too.

When preparing problems, people usually set the time limit to at least twice the running time of the standard program, but sometimes contestants still feel that the time limit is too tight.

Now you have the standard program for a problem and another $$$n$$$ programs considered "should pass the problem". Given the running time of each program, please find the smallest integer $$$k\ge 2$$$, so that when the time limit is set to $$$k$$$ times the running time of the standard program, all the provided programs can pass. A program can pass if and only if its running time less or equal to the time limit.