The first man was called George. He likes to play string concatenating games. He has a sequence $$$\{s_1,s_2,...s_n\}$$$ which is composed of $$$n$$$ strings. Sometimes he selects some strings from the sequence and concatenate them together in their original relative order to form a string. It means that he can arbitrarily choose a sequence of integer $$$A=\{a_1,a_2,..,a_k\},\ (1\le k \le n,\ 1\le a_1 \lt a_2 \lt ... \lt a_k\le n)$$$ , and then he will concatenate $$$s_{a_1},s_{a_2},\cdots,s_{a_k}$$$ together to form a new string $$$s_{a_1}+s_{a_2}+...+s_{a_k}$$$, where $$$S+T$$$ means to put string $$$T$$$ right after string $$$S$$$. For example, if his string sequence is $$$\{\text{heh},\text{e},\text{j},\text{ie}\}$$$ and he chooses $$$\{1,3,4\}$$$ ,then he will get a string "$$$\text{hehjie}$$$".

The second man is called Karsh. He likes lucky strings. If a string is the same as itself after reversion, Karsh calls it a lucky string (or palindrome string).

Today day Karsh meets George. He hopes George could choose such a sequence $$$A$$$, concatenate the strings according to the chosen sequence, and finally form a lucky string for him.

Then the problem comes. How many different choices are there to form a lucky string?

Given a sequence $$$A_1, A_2, \cdots, A_n$$$. As for a subsequence $$$A_{b_1}, A_{b_2}, \cdots, A_{b_m} \, (1\le b_1 \lt b_2 \lt \cdots \lt b_m \le n)$$$, we say it magical if and only if $$$m$$$ is even and $$$A_{b_1} + A_{b_2} = A_{b_3} + A_{b_4} = \cdots = A_{b_{m-1}} + A_{b_m}$$$. Determine the maximum length among all magical subsequences of the given sequence.

Given a 1-rooted tree $$$T$$$, where there is a desired color $$$c_u$$$ for each leaf(vertices who have no children) $$$u$$$. The leaves have no color initially, and you should do several operations to make all the leaves painted by their desired colors. For each operation, you can choose a vertex $$$x$$$ and a color $$$c$$$, then make all the leaves in the $$$x$$$-rooted subtree painted by color $$$c$$$. Specially, if a leaf was painted multiple times, only the latest painted color counts. Determine the minimum possible number of operations to make all the leaves painted by their desired colors.

Tang Keke is good at math. She knows how to simplify fractions very well. Even greater, she invented a simplifying method by herself!

The method is to choose some digits which appear in both the top and the bottom and erase them on both sides while keeping the fraction value unchanged. The digits are the same, so they can reduce each other. Sounds very logical, right?

The method may produce multiple simplified results and the one with the least top number is called the most simplified form. Keke prepared some fractions and is going to test if you can get the most simplified form.

Note that the chosen digits form a multiset, you can see the examples for more details.

Given $$$n$$$ non-negative integers $$$A_1, A_2, \cdots, A_n$$$. Determine if there is only one positive integer $$$M$$$ that $$$\forall i \in \{1, 2, \cdots, n\},\, A_i = 2^{i-1} \!\!\mod M$$$. If so, print the integer $$$M$$$, or print "-1".

Here, $$$a \!\!\mod b$$$ denotes the remainder of $$$a$$$ after division by $$$b$$$, where $$$a \in [0,b)$$$ holds. For example, $$$5 \!\!\mod 2 = 1$$$, $$$9 \!\!\mod 3 = 0$$$, $$$1 \!\!\mod 2 = 1$$$.

You are playing Touhou Impershiable Night, a bullet curtain shooting game, and are fighting against Kirisame Marisa, the boss in stage 4B, who launchs master sparks to attack players. Following is a illustration of this scene.

Image that the game area is in a 2D plane. The player is restricted in a rectangle region $$$M~(\{(x,y) \; | \; 0\le x \le X, 0\le y \le Y\})$$$ and the sparks can be described as ribbon regions $$$S_i~(\{(x,y) \; | \; C_i \le A_ix + B_iy \le D_i\})$$$.

Now given $$$X,Y$$$ and $$$n$$$ sparks $$$S_1, S_2, \cdots, S_n$$$, you want to know that if there exists such a point $$$P~(P \in M)$$$ that $$$\forall i \in \{1, 2, \cdots, n\}, P \notin S_i$$$ to avoid all sparks and autowin the game.

Ring Ring Ring ... The bell rang at half past six in the morning. After turning off the alarm, George went on to sleep again. When he woke up again, it was seven fifty and there were ten minutes left for class!

George immediately got up from bed, dressed, packed his backpack, brushed his teeth and washed his face. Then, he immediately rushed out of the dormitory and embarked on the road to the teaching building. On the way, he turned on his mobile phone to locate and saw several yellow shared bicycles nearby. Therefore, he headed to a bicycle and took out his mobile phone to scan the QR code on the bicycle. Unfortunately, the bicycle wasn't unlocked, and a line of words "this bicycle is damaged and can't be unlocked" was displayed on the screen.

Without riding a bicycle, he was late. What a bad day!

Indeed, some bicycles in the school are damaged, but their location will still be displayed on the app. George always rides faster than he walks, but considering that some bicycles are damaged, if George tries one by one, it may take a long time! In this regard, he has made some modeling, and hopes you can help him find the best strategy.

The campus can be modeled as a graph of $$$n$$$ vertices and $$$m$$$ bidirected edges, where the $$$i$$$-th edge is $$$w_i$$$ meters long. George's dormitory is located at vertex $$$1$$$ and Guanghua Tower (the teaching building) is at vertex $$$n$$$, so George has to go from vertex $$$1$$$ to vertex $$$n$$$ to take classes. His walking speed is $$$t$$$ meters per second and his riding speed is $$$r$$$ meters per second. According to the bicycle sharing app, there are $$$k$$$ parked bicycles in the campus. The $$$i$$$-th bicycle is located at vertex $$$a_i$$$, and of probability $$$\frac{p_i}{100}$$$ to be damaged according to George's experience. However, only when George arrives at vertex $$$a_i$$$ and scans the QR code, can he determine whether the $$$i$$$-th bicycle is damaged or not. As soon as a bicycle is confirmed to be undamaged, George will get on it immediately and will not get off until he reaches vertex $$$n$$$.

Now George wants to save time to get to the classroom. So you, George's roommate, should help him find an optimal strategy to minimize the mathematical expectation of the time cost on the way, and then output this value. Or you can let him continue sleeping if vertex $$$n$$$ is not reachable.

In this problem, you should only consider the time of walking and cycling, and you can assume that the other actions(scanning QR code, getting on, getting off, $$$\cdots$$$) cost no time.

What instructs and directs Reyna's analysis and cognition, is his soul together with a sort of sophisticated logic system. In the view of this system, which is blessed with awesome adaptiveness as well as adjustability, everything in a specific metaverse should be readily transformed into some kind of homogeneous expression, for instance, a string. So similarity and equivalency can be explored for further processing.

This afternoon, when wandering on a forest path in NeverLand, Reyna is absorbed by a line of peculiar silver birches. He soon realizes that some of them are essentially identical with the cue given by his logic system. To elaborate this observation, each birch is sparsely coded as a string in Reyna's mind, with a equivalency transition rule due to the sparseness.

A string $$$S$$$ can be represented as an integer sequence $$$S_1, S_2, \cdots, S_l$$$, and according to Reyna's rule, two strings are considered $$$k$$$-equivalent if one can be finitely $$$k$$$-operated to be the other one. For each $$$k$$$-operation, he can choose an integer $$$a\,(1\le a \le l-2k+1)$$$, and then swap $$$S_{a+i}$$$ and $$$S_{a+k+i}$$$ for all $$$i\,(i = 0, 1, \cdots, k-1)$$$.

Now there're $$$n$$$ query tuples $$$(S,\ T,\ k)$$$. For each tuple $$$(S,\ T,\ k)$$$, Reyna would like to query if $$$S$$$ and $$$T$$$ are $$$k$$$-equivalent.

Given a sequence $$$A_1, A_2, \cdots, A_n$$$ whose elements are all positive integers. You should do some operations to make the sequence all zero. For each operation, you can appoint a sequence $$$B_1, B_2, \cdots, B_m \,(B_i \in \{1, 2, \cdots, n\})$$$ of arbitrary length $$$m$$$ and reduce $$$A_{B_i}$$$ by $$$2^{i-1}$$$ respectively. Specially, one element in the given sequence can be reduced multiple times in one operation. Determine the minimum possible number of operations to make the given sequence all zero.

Given a matrix of size $$$n\times m$$$. Determine the number of entries who equals the minimum value among all other entries of the same row or column. Formally, determine the value of $$$$$$\sum_{i=1}^{n}\sum_{j=1}^{m}\left[\min\{M_{u, v} \, | \, u = i \; \mathrm{or} \; v = j \} = M_{i, j}\right]$$$$$$

Note: $$$[A] = 1$$$ if statement $$$A$$$ is true, or $$$[A] = 0$$$.

Ohto Ai holds $$$n$$$ wonder eggs. Each of them has a priority value initially. Let's say $$$p_i$$$ is the $$$i$$$-th egg's priority value. The priority values will change since they are wonder eggs that have miraculous power. Ai has found the changing pattern.

Ai is going to observe the wonder eggs in the next $$$q$$$ moments. At each moment, one of the following events will happen:

1. Ai gets the changing coefficient $$$k$$$ of this time, and she knows for each of the $$$l$$$-th egg to the $$$r$$$-th egg, $$$p_i$$$ will change to $$$k^{p_i}$$$.
2. No priority value changing happens, and Ai calculates the sum of the $$$l$$$-th egg to the $$$r$$$-th egg's priority value.

Ai wants to check if she gets the correct sum values. So for each event of the second type, she wants you to output the sum modulo $$$M$$$.

This season, Karshilov was forced to retirec since he was abandoned by his teammates. However, it does not affect his enthusiasm for studying matching problems.

There are $$$n$$$ lucky digital strings $$$t_1, t_2, \cdots, t_n$$$, where the $$$i$$$-th string has a lucky value $$$w_i$$$.

For any string $$$S$$$, define that $$$f(S)=\sum_{i=1}^n occur(S,t_i)\cdot w_i \pmod {998244353}$$$, where $$$occur(S,t_i)$$$ is the number of occurrences of string $$$t_i$$$ in $$$S$$$. For example, $$$occur(12121,121)=2$$$ and $$$occur(000,0)=3$$$.

Now, Karshilov has a string $$$S$$$ and he will do $$$m$$$ operations one by one. Each operation is of one of the following two types:

1. $$$1\;l\;c$$$. Change all the last $$$l$$$ characters of $$$S$$$, that is, $$$S_{|S|-l+1},S_{|S|-l+2},\cdots,S_{|S|}$$$ into $$$c$$$.
2. $$$2\;l$$$. Determine the value of $$$f(S[1,l])$$$, where $$$S[1,l]$$$ means the string formed by first $$$l$$$ characters of $$$S$$$, which is $$$S_1S_2\cdots S_l$$$.

Can you help Karshilov to find the answers to all operations of the second type?