The 2022 SDUT Summer Trials
A. Ginger's number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ginger have two positive integers $$$x, y$$$, you have to do exactly one operation:

Choose two positive integers $$$a, b$$$, change $$$x$$$ to $$$\dfrac{x}{a}$$$, and change $$$y$$$ to $$$\dfrac{y}{b}$$$, ($$$a$$$ must be a divisor of $$$x$$$, $$$b$$$ must be a divisor of $$$y$$$ and $$$\gcd(\dfrac{x}{a}, \dfrac{y}{b}) = 1$$$).

Find the minimum value of $$$a \times b$$$.

Input

The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 10 ^ 5)$$$ — the number of input test cases.

For each test case, the only line of input contains two positive integers $$$x, y$$$ $$$(1 \le x,y \le 10 ^ 9)$$$.

Output

Print the minimum value of $$$a \times b$$$.

Example
Input
1
114514 1919810
Output
2

B. Ginger's game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ monsters with $$$a_1,a_2,\dots,a_n$$$ HP in game. Before the start of the game, Ginger can set the HP $$$a_i$$$ of each monster to any non-negative integer less than or equal to $$$a_i$$$. When the game starts, Ginger can choose any position $$$i$$$ $$$(1 \le i \le n)$$$, and then Ginger must kill the monsters in the order of $$$i, i - 1, \cdots, 1$$$, and the HP of the attacked monsters must follow the order of non-strict decreasing, Ginger will get $$$\sum_{j = 1} ^ {i} a_j$$$ money.

Find the maximum money.

Input

The first line contains a integer $$$n$$$ $$$(1 \le n \le 2 \times 10 ^ 5)$$$ indicating the number of monsters HP.

The second line contains $$$n$$$ integers $$$a_1,a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10 ^ 9)$$$ indicating the monsters HP.

Output

Print the maximum money.

Example
Input
5
8 5 4 7 2
Output
19
Note

For test case:

Before the start of the game, the monster's HP is set to $$$[4 , 4 , 4 , 7 , 2]$$$.

When the game starts, Ginger chooses position $$$i = 4$$$, Ginger will get $$$7 + 4 + 4 + 4 = 19$$$ money.

C. Ginger's sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ginger gives you a sequence of length $$$n$$$, please ask if there are two non-empty different subsequences in this sequence, such that $$$s_1 \equiv s_2 \pmod k$$$, $$$s_1, s_2$$$ are the sum of the two subsequences respectively.

If there exist, output $$$\text{YES}$$$, otherwise output $$$\text{NO}$$$.

Input

The first line contains two integers $$$n, k$$$ $$$(1 \le n,k \le 10 ^ 5)$$$ indicating the lenth of sequence and modulo.

The second line contains $$$n$$$ integers $$$a_1,a_2, \dots, a_n$$$ indicating the sequence.

Output

Print $$$\text{YES}$$$ or $$$\text{NO}$$$.

Example
Input
5 10
1 2 3 4 5
Output
YES
Note

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

D. Ginger's line
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ginger have $$$n$$$ straight lines $$$y = a_i x + b_i$$$, now Ginger wants to know how many pairs of straight lines $$$i,j(i \lt j)$$$ intersect.

Input

The first line contains a integer $$$n$$$ $$$(1 \le n \le 5 \times 10 ^ 3)$$$ indicating the number of lines.

The next $$$n$$$ lines contains two integers $$$a_i, b_i$$$ $$$(-10 ^3 \le a_i, b_i \le 10^3)$$$ indicating line $$$y = a_i x + b_i$$$.

Output

Print the pairs of intersections of lines.

Examples
Input
5
1 1
2 2
3 3
4 4
5 5
Output
10
Input
2
1 0
1 0
Output
0
Note

Note that overlapping lines do not intersect.

E. Ginger's coloring
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an permutation $$$p_1, p_2, \dots,p_n$$$ of length $$$n$$$, now color each number from $$$1$$$ to $$$n$$$ in black and white.

Define $$$\texttt{Ginger coloring}$$$ as:

for all $$$i$$$ $$$(1 \le i \le n)$$$, the color of $$$i$$$ not equal to the color of $$$p_i$$$.

How many ways of coloring make permutation $$$p$$$ become $$$\texttt{Ginger coloring}$$$ modulo $$$998\,244\,353$$$.

Input

The first line contains a integer $$$n$$$ $$$(1 \le n \le 10 ^ 5)$$$ indicating the lenth of permutation.

The next line contains $$$n$$$ integers $$$p_1,p_2,\cdots,p_n$$$ $$$(1 \le p_i \le n)$$$ indicating the permutation.

Output

Output the ways of coloring modulo $$$998\,244\,353$$$.

Example
Input
6
2 3 4 1 6 5
Output
4

F. Ginger's treasure
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Although Ginger is the king of the algorithm world, Ginger's performance in Tivat has been disappointing. Because Ginger devotes all his time to the algorithm, the abyss gets hung up every issue. Now that Ginger needs you to help him maximize the strength of his lineup, can you help Ginger go further in the abyss?

Ginger's treasure trove contains numerous weapons, which are placed in weapon slots for easy selection. Each weapon has its own attack power, and due to some restrictions, Ginger can only choose $$$k$$$ from the weapons. You need to help Ginger to maximize the product of these weapons.

Input

The first line contains a string $$$s$$$ $$$(1 \le |s| \le 2 \times 10 ^ 6)$$$ indicating all weapons, $$$|s|$$$ denotes the size of the string.

The string contains the attack power of all weapons $$$x_i$$$ $$$(-10 ^ 9 \le x_i \le 10 ^ 9)$$$, the weapons are separated by several "|". Each weapon is numbered starting at $$$1$$$ in the order in which it appears in the string.

The second line is the number of choices $$$k$$$. Guarantee that $$$k$$$ is less than or equal to the number of weapons, and $$$1 \le k$$$.

Output

Print the $$$k$$$ selected weapon in ascending order separated by spaces, representing the number of the selected weapon. If there are multiple solutions, output the answer with the smallest lexicographical order.

Examples
Input
|12|31|-12|1|
1
Output
2
Input
|||1|||31||-12|12|
2
Output
2 4
Input
||13|13||13|13
3
Output
1 2 3

G. Ginger's password
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ginger forgot his password, but Ginger has a habit of setting passwords, except for the first bit, each bit is not lexicographically smaller than the previous bit, in another word, the entire password string is non-descending, and each letter has a number limit.

Now Ginger only remembers a subsequence of the password string $$$s$$$ and the length of the original password string $$$k$$$. Can you help Ginger calculate how many possible original password string modulo $$$998\,244\,353$$$.

If the original password is not found, output $$$\text{NO SOLUTION!}$$$

Input

The first line contains two integers $$$n, k$$$ $$$(1\le n,k \le 2 \times 10 ^ 3)$$$ indicating the lenth of the password string subsequence that Ginger remembers and the lenth of entire password string.

The second line contains $$$26$$$ integers $$$a_1,a_2,\cdots,a_n$$$ $$$(0 \le a_i \le 10 ^ 9)$$$ indicating Occurrence limit of each letter from $$$\texttt{a}$$$ to $$$\texttt{z}$$$.

The third line contains a string $$$s$$$, contains only lowercase letters.

Output

Print the ways of possible original password string modulo $$$998\,244\,353$$$ if it's exist,

otherwise print $$$\text{NO SOLUTION!}$$$

Examples
Input
3 3
1 1 4 5 1 4 1 9 1 9 8 1 0
1 1 4 5 1 4 1 9 1 9 8 1 0
abc
Output
1
Input
3 4
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
aab
Output
NO SOLUTION!
Note

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

H. Ginger's clone
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a matrix of size $$$n \times n$$$, each cell of the matrix has a number. Initially, Ginger stands in the upper left grid and the initial direction is downward, and Ginger's clone is in the lower right grid and the initial direction is upward.

Ginger and his clone will continue to walk in one direction, until the next grid is walked or beyond the matrix range, will turn 90° to the left and change direction to continue walking.

Finally, output the numbered sequence that Ginger and the clone walked through.

Note that if Ginger and his clone walk to a grid at the same time, the number of the grid is regarded as Ginger walking, not Ginger's clone.

Input

The first line contains a integer $$$n$$$ $$$(2 \le n \le 200)$$$ indicating side length of square matrix.

The next line, contains the matrix of size $$$n \times n$$$, indicating the number of each grid (there is no grid with the same number in the matrix, and guarantee the number must be in the range of positive integers).

Output

The output consists of two lines. The first line represents the number sequence of Ginger's walk, and the second line represents the number sequence of the clone's walk.

Examples
Input
3
1 2 3
4 5 6
7 8 9
Output
1 4 7 8 5 
9 6 3 2
Input
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Output
1 5 9 13 14 15 11 7 
16 12 8 4 3 2 6 10
Note

In test case $$$1$$$, Ginger and the clone will arrive at the grid numbered $$$5$$$ at the same time, which is regarded as Ginger.

I. Ginger's balance
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ginger has a balance. Each plate can only hold $$$n$$$ items(the balance has two plates). Now Ginger has $$$m$$$ items, one of which is a light item, the rest of the items are the same weight, and Ginger wants to know the minimum number of times he weighs to be sure to find the bad item.

Input

The first line contains two integers $$$n$$$ $$$(1 \le n \le 10 ^ 4)$$$, $$$m$$$ $$$(1 \le m \le 10 ^ 6)$$$.

Output

Print the minimum times.

Examples
Input
2 4
Output
2
Input
100 10
Output
3

J. Ginger's cow
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ginger has a total of $$$n$$$ cows, he has $$$m$$$ old cows and $$$n-m$$$ small cows. Old cows can feed small cows, Ginger wants to pair as many cows with small cows as possible.

Ginger wants to know the maximum number of small cows that can be fed

Input

The first line contains three integers $$$m$$$ indicating the number of old cows, $$$n$$$ indicating the number of cows, $$$q$$$ indicating feeding relationship. $$$1 \le m \le n \le 100$$$, $$$1 \le q \le 10 ^ 3$$$

Next $$$q$$$ lines, each line has two strings $$$u, v$$$, representing old cows $$$u$$$ can feed small cows $$$v$$$

Output

Print the maximum number of small cows that can be fed.

Example
Input
5 10 10
A G
A H
B F
B I
B J
C G
C H
D G
D H
E J
Output
4

K. Ginger's palindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ginger has $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$, the value of $$$a_i$$$ is $$$c_{i}$$$. Ginger will choose some of these numbers so that put together it is a palindrome, the same number can be chose multiple times.

Ginger wants to know the minimum value.

Input

The first line contain a integer $$$n$$$ $$$(1\le n \le 40)$$$ indicate number of numbers.

The next $$$n$$$ line, each line contains two integers $$$a_i, c_i$$$ $$$(0\le a_i, c_i \le10^{9})$$$

Output

Print the minimum value.

Example
Input
5
12 21
21 13
13 111
45 19
331 12
Output
34
Note

If there is a number chose multiple times, the value is the value of the number $$$\times$$$ number of choices.

L. Ginger's function
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$\texttt{Ginger}$$$ has a function

$$$$$$ G(x) = \prod_{i=1}^{n}(1-x^{\lfloor \frac{f_i}{2} \rfloor}-x^{f_i}) $$$$$$

$$$\texttt{Ginger}$$$ decides to give you $$$q$$$ inquiries, given a integer $$$a$$$ for each query, answer the coefficient of $$$x ^ a$$$.

Input

The first line contains two integers $$$n$$$ $$$(1 \le n \le 11)$$$, $$$q$$$ $$$(1 \le q \le 10 ^ 4)$$$.

The second line contains $$$n$$$ integers $$$f_1, f_2, \dots, f_n$$$ $$$(0 \leq f_i \leq 10^6)$$$.

The next $$$q$$$ lines contains a integer $$$a$$$ $$$(0 \leq a \leq \sum_{i = 1} ^ {n} f_i)$$$

Output

output $$$q$$$ lines, Each line print the answer.

Example
Input
2 5
3 4
0
1
2
3
5
Output
1
-1
-1
0
2
Note

For test case:

$$$(1-x-x^3)(1-x^2-x^4) = 1 - x - x^2 - x^4 + 2x^5 + x^7$$$