apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 512.0 MB

# Problem
There are $$$n$$$ people (numbered from $$$1$$$ to $$$n$$$) signed up for a doctor's appointment. The doctor has to choose in which order he will appoint these people. The $$$i$$$-th patient should be appointed among the first $$$p_i$$$ people. There are also $$$m$$$ restrictions of the following format: the $$$i$$$-th restriction is denoted by two integers $$$(a_i, b_i)$$$ and means that the patient with the index $$$a_i$$$ should be appointed earlier than the patient with the index $$$b_i$$$.

For example, if $$$n = 4$$$, $$$p = [2, 3, 2, 4]$$$, $$$m = 1$$$, $$$a = [3]$$$ and $$$b = [1]$$$, then the only order of appointment of patients that does not violate the restrictions is $$$[3, 1, 2, 4]$$$. For $$$n =3$$$, $$$p = [3, 3, 3]$$$, $$$m = 0$$$, $$$a = []$$$ and $$$b = []$$$, any order of appointment is valid.

For each patient, calculate the minimum position in the order that they can have among all possible orderings that don't violate the restrictions.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2000$$$; $$$0 \le m \le 2000$$$).

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$).

Then $$$m$$$ lines follow. The $$$i$$$-th of them contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$; $$$a_i \ne b_i$$$). All pairs of $$$(a_i, b_i)$$$ are distinct (i. e. if $$$i \ne j$$$, then either $$$a_i \ne a_j$$$, $$$b_i \ne b_j$$$, or both).

Additional constraint on the input: there is at least one valid order of patients.

## Output Format
Print $$$n$$$ integers, where $$$i$$$-th integer is equal to the minimum position of $$$i$$$-th patient in the order, among all valid orders. Positions in the order are numbered from $$$1$$$ to $$$n$$$.

## Examples
```input
4 1
2 3 2 4
3 1
```
```output
2 3 1 4
```
-----
```input
3 0
3 3 3
```
```output
1 1 1
```
-----
```input
5 3
4 3 3 2 5
3 1
1 5
4 2
```
```output
4 2 1 1 5
```

## Note
In the first example, $$$[3, 1, 2, 4]$$$ the only one valid order, so the minimum position of each patient is equal to their position in this order.

In the second example, any order is valid, so any patient can be appointed first.

In the third example, there are three valid orders: $$$[4, 2, 3, 1, 5]$$$, $$$[3, 4, 2, 1, 5]$$$ and $$$[4, 3, 2, 1, 5]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a square grid with $$$n$$$ rows and $$$n$$$ columns, where each cell has a non-negative integer written in it. There is a chip initially placed at the top left cell (the cell with coordinates $$$(1, 1)$$$). You need to move the chip to the bottom right cell (the cell with coordinates $$$(n, n)$$$).

In one step, you can move the chip to the neighboring cell, but:

1. you can move only right or down. In other words, if the current cell is $$$(x, y)$$$, you can move either to $$$(x, y + 1)$$$ or to $$$(x + 1, y)$$$. There are two special cases:   if the chip is in the last column (cell $$$(x, n)$$$) and you're moving right, you'll teleport to the first column (to the cell $$$(x, 1)$$$);  if the chip is in the last row (cell $$$(n, y)$$$) and you're moving down, you'll teleport to the first row (to the cell $$$(1, y)$$$).
2. you cannot visit the same cell twice. The starting cell is counted visited from the beginning (so you cannot enter it again), and you can't leave the finishing cell once you visit it.

Your total score is counted as the sum of numbers in all cells you have visited. What is the maximum possible score you can achieve?

## Input Format
The first line contains the single integer $$$n$$$ ($$$2 \le n \le 200$$$) — the number of rows and columns in the grid.

Next $$$n$$$ lines contains the description of each row of the grid. The $$$i$$$-th line contains $$$n$$$ integers $$$a_{i, 1}, a_{i, 2}, \dots, a_{i, n}$$$ ($$$0 \le a_{i, j} \le 10^9$$$) where $$$a_{i, j}$$$ is the number written in the cell $$$(i, j)$$$.

## Output Format
Print one integer — the maximum possible score you can achieve.

## Examples
```input
2
1 2
3 4
```
```output
8
```
-----
```input
3
10 10 10
10 0 10
10 10 10
```
```output
80
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an integer $$$n$$$.

Your task is to find two positive (greater than $$$0$$$) integers $$$a$$$ and $$$b$$$ such that $$$a+b=n$$$ and the least common multiple (LCM) of $$$a$$$ and $$$b$$$ is the minimum among all possible values of $$$a$$$ and $$$b$$$. If there are multiple answers, you can print any of them.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^9$$$).

## Output Format
For each test case, print two positive integers $$$a$$$ and $$$b$$$ — the answer to the problem. If there are multiple answers, you can print any of them.

## Examples
```input
4
2
9
5
10
```
```output
1 1
3 6
1 4
5 5
```

## Note
In the second example, there are $$$8$$$ possible pairs of $$$a$$$ and $$$b$$$:

- $$$a = 1$$$, $$$b = 8$$$, $$$LCM(1, 8) = 8$$$;
- $$$a = 2$$$, $$$b = 7$$$, $$$LCM(2, 7) = 14$$$;
- $$$a = 3$$$, $$$b = 6$$$, $$$LCM(3, 6) = 6$$$;
- $$$a = 4$$$, $$$b = 5$$$, $$$LCM(4, 5) = 20$$$;
- $$$a = 5$$$, $$$b = 4$$$, $$$LCM(5, 4) = 20$$$;
- $$$a = 6$$$, $$$b = 3$$$, $$$LCM(6, 3) = 6$$$;
- $$$a = 7$$$, $$$b = 2$$$, $$$LCM(7, 2) = 14$$$;
- $$$a = 8$$$, $$$b = 1$$$, $$$LCM(8, 1) = 8$$$.

In the third example, there are $$$5$$$ possible pairs of $$$a$$$ and $$$b$$$:

- $$$a = 1$$$, $$$b = 4$$$, $$$LCM(1, 4) = 4$$$;
- $$$a = 2$$$, $$$b = 3$$$, $$$LCM(2, 3) = 6$$$;
- $$$a = 3$$$, $$$b = 2$$$, $$$LCM(3, 2) = 6$$$;
- $$$a = 4$$$, $$$b = 1$$$, $$$LCM(4, 1) = 4$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a positive integer $$$x$$$.

You can apply the following operation to the number: remove one occurrence of any digit in such a way that the resulting number does not contain any leading zeroes and is still a positive integer. For example, $$$10142$$$ can be converted to $$$1142$$$, $$$1042$$$, $$$1012$$$ or $$$1014$$$ (note that $$$0142$$$ is not a valid outcome); $$$10$$$ can be converted to $$$1$$$ (but not to $$$0$$$ since it is not positive).

Your task is to find the minimum positive integer that you can obtain from $$$x$$$ if you can apply the aforementioned operation exactly $$$k$$$ times.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first line of each test case contains a single integer $$$x$$$ ($$$1 \le x < 10^{500000}$$$).

The second line contains a single integer $$$k$$$ ($$$0 \le k < |x|$$$), where $$$|x|$$$ is the length of the number $$$x$$$.

The sum of $$$|x|$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

## Output Format
For each test case, print one integer — the minimum positive number that you can obtain from $$$x$$$ if you can apply the operation exactly $$$k$$$ times.

## Examples
```input
5
10000
4
1337
0
987654321
6
66837494128
5
7808652
3
```
```output
1
1337
321
344128
7052
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
MKnez wants to construct an array $$$s_1,s_2, \ldots , s_n$$$ satisfying the following conditions:

- Each element is an integer number different from $$$0$$$;
- For each pair of adjacent elements their sum is equal to the sum of the whole array.

More formally, $$$s_i \neq 0$$$ must hold for each $$$1 \leq i \leq n$$$. Moreover, it must hold that $$$s_1 + s_2 + \cdots + s_n = s_i + s_{i+1}$$$ for each $$$1 \leq i < n$$$.

Help MKnez to construct an array with these properties or determine that it does not exist.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 100$$$). The description of the test cases follows.

The only line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 1000$$$) — the length of the array.

## Output Format
For each test case, print "YES" if an array of length $$$n$$$ satisfying the conditions exists. Otherwise, print "NO". If the answer is "YES", on the next line print a sequence $$$s_1,s_2, \ldots, s_n$$$ satisfying the conditions. Each element should be a non-zero integer in the range $$$[-5000,5000]$$$, i. e. $$$-5000 \leq s_i \leq 5000$$$ and $$$s_i \neq 0$$$ should hold for each $$$1 \leq i \leq n$$$.

It can be proved that if a solution exists then there also exists one which satisfies the additional constraints on the range.

If there are several correct answers, print any of them.

## Examples
```input
2
2
3
```
```output
YES
9 5
NO
```

## Note
In the first test case, $$$[9,5]$$$ is a valid answer since $$$9+5$$$ (the sum of the two adjacent elements $$$s_1+s_2$$$) is equal to $$$9+5$$$ (the sum of all elements). Other solutions include $$$[6,-9], [-1,-2], [-5000,5000], \ldots$$$

For the second test case, let us show why some arrays do not satisfy the constraints:

- $$$[1,1,1]$$$  — $$$s_1+s_2 = 1+1 = 2$$$ and $$$s_1+s_2+s_3=1+1+1 = 3$$$ differ;
- $$$[1,-1,1]$$$  — $$$s_1+s_2=1+(-1)=0$$$ and $$$s_1+s_2+s_3=1+(-1)+1 = 1$$$ differ;
- $$$[0,0,0]$$$  — The array $$$s$$$ cannot contain a $$$0$$$.

This is not a proof, but it can be shown that the answer is "NO".

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Mocha likes arrays, and Serval gave her an array consisting of positive integers as a gift.

Mocha thinks that for an array of positive integers $$$a$$$, it is good iff the greatest common divisor of all the elements in $$$a$$$ is no more than its length. And for an array of at least $$$2$$$ positive integers, it is beautiful iff all of its prefixes whose length is no less than $$$2$$$ are good.

For example:

- $$$[3,6]$$$ is not good, because $$$\gcd(3,6)=3$$$ is greater than its length $$$2$$$.
- $$$[1,2,4]$$$ is both good and beautiful, because all of its prefixes whose length is no less than $$$2$$$, which are $$$[1,2]$$$ and $$$[1,2,4]$$$, are both good.
- $$$[3,6,1]$$$ is good but not beautiful, because $$$[3,6]$$$ is not good.

Now Mocha gives you the gift array $$$a$$$ of $$$n$$$ positive integers, and she wants to know whether array $$$a$$$ could become beautiful by reordering the elements in $$$a$$$. It is allowed to keep the array $$$a$$$ unchanged.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\leq t\leq 500$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 100$$$) — the length of array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_1,a_2,\ldots,a_n\leq 10^6$$$) — the elements of array $$$a$$$.

## Output Format
For each test case, print Yes if it is possible to reorder the elements in $$$a$$$ to make it beautiful, and print No if not.

You can output Yes and No in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

## Examples
```input
6
2
3 6
3
1 2 4
3
3 6 1
3
15 35 21
4
35 10 35 14
5
1261 227821 143 4171 1941
```
```output
No
Yes
Yes
No
Yes
Yes
```

## Note
In the first test case, neither $$$[3,6]$$$ nor $$$[6,3]$$$ are beautiful, so it's impossible to obtain a beautiful array by reordering the elements in $$$a$$$.

In the second test case, $$$[1,2,4]$$$ is already beautiful. Keeping the array $$$a$$$ unchanged can obtain a beautiful array.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Serval has a string $$$s$$$ that only consists of 0 and 1 of length $$$n$$$. The $$$i$$$-th character of $$$s$$$ is denoted as $$$s_i$$$, where $$$1\leq i\leq n$$$.

Serval can perform the following operation called Inversion Magic on the string $$$s$$$:

- Choose an segment $$$[l, r]$$$ ($$$1\leq l\leq r\leq n$$$). For $$$l\leq i\leq r$$$, change $$$s_i$$$ into 1 if $$$s_i$$$ is 0, and change $$$s_i$$$ into 0 if $$$s_i$$$ is 1.

For example, let $$$s$$$ be 010100 and the segment $$$[2,5]$$$ is chosen. The string $$$s$$$ will be 001010 after performing the Inversion Magic.

Serval wants to make $$$s$$$ a palindrome after performing Inversion Magic exactly once. Help him to determine whether it is possible.

A string is a palindrome iff it reads the same backwards as forwards. For example, 010010 is a palindrome but 10111 is not.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\leq t\leq 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 10^5$$$) — the length of string $$$s$$$.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$. Only characters 0 and 1 can appear in $$$s$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

## Output Format
For each test case, print Yes if $$$s$$$ can be a palindrome after performing Inversion Magic exactly once, and print No if not.

You can output Yes and No in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

## Examples
```input
3
4
1001
5
10010
7
0111011
```
```output
Yes
Yes
No
```

## Note
In the first test case, Serval can perform Inversion Magic on the segment $$$[1,4]$$$. The string $$$s$$$ will be 0110 after the magic.

In the second test case, Serval can perform Inversion Magic on the segment $$$[1,3]$$$. The string $$$s$$$ will be 01110 after the magic.

In the third test case, Serval can't make $$$s$$$ a palindrome by performing Inversion Magic exactly once.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Serval loves Brain Power and his brain power problem.

Serval defines that a string $$$T$$$ is powerful iff $$$T$$$ can be obtained by concatenating some string $$$T'$$$ multiple times. Formally speaking, $$$T$$$ is powerful iff there exist a string $$$T'$$$ and an integer $$$k\geq 2$$$ such that $$$$$$T=\underbrace{T'+T'+\dots+T'}_{k\text{ times}}$$$$$$

For example, gogogo is powerful because it can be obtained by concatenating go three times, but power is not powerful.

Serval has a string $$$S$$$ consists of lowercase English letters. He is curious about the longest powerful subsequence of $$$S$$$, and he only needs you to find out the length of it. If all the non-empty subsequences of $$$S$$$ is not powerful, the answer is considered to be $$$0$$$.

A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters.

## Input Format
The first line contains a single string $$$S$$$ ($$$|S|\leq 80$$$) consisting of lowercase English letters.

## Output Format
Print a single integer — the length of the longest powerful subsequence of $$$S$$$. If all the non-empty subsequences of $$$S$$$ is not powerful, print $$$0$$$.

## Examples
```input
buaa
```
```output
2
```
-----
```input
codeforcesround
```
```output
6
```
-----
```input
oooooooooooaaaaeaaiaujooooooooooooo
```
```output
24
```
-----
```input
zero
```
```output
0
```

## Note
For the first sample, all of the non-empty subsequences of buaa are listed below:

- b
- u
- a (occurred twice, buaa and buaa)
- bu
- ba (occurred twice, buaa and buaa)
- ua (occurred twice, buaa and buaa)
- aa
- bua (occurred twice, buaa and buaa )
- baa
- uaa
- buaa

Since $$$\texttt{aa} = \texttt{a} + \texttt{a}$$$, aa is a powerful subsequence. It can be shown that aa is the only powerful subsequence among them. So the answer is $$$2$$$.

For the second sample, the longest powerful subsequence is codcod from codeforcesround. So the answer is $$$6$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
On March 14, the day of the number $$$\pi$$$ is celebrated all over the world. This is a very important mathematical constant equal to the ratio of the circumference of a circle to its diameter.

Polycarp was told at school that the number $$$\pi$$$ is irrational, therefore it has an infinite number of digits in decimal notation. He wanted to prepare for the Day of the number $$$\pi$$$ by memorizing this number as accurately as possible.

Polycarp wrote out all the digits that he managed to remember. For example, if Polycarp remembered $$$\pi$$$ as $$$3.1415$$$, he wrote out 31415.

Polycarp was in a hurry and could have made a mistake, so you decided to check how many first digits of the number $$$\pi$$$ Polycarp actually remembers correctly.

## Input Format
The first line of the input data contains the single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases in the test.

Each test case is described by a single string of digits $$$n$$$, which was written out by Polycarp.

The string $$$n$$$ contains up to $$$30$$$ digits.

## Output Format
Output $$$t$$$ integers, each of which is the answer to the corresponding test case, that is how many first digits of the number $$$\pi$$$ Polycarp remembers correctly.

## Examples
```input
9
000
3
4141592653
141592653589793238462643383279
31420
31415
314159265358
27182
314159265358979323846264338327
```
```output
0
1
0
0
3
5
12
0
30
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Taisia has $$$n$$$ six-sided dice. Each face of the die is marked with a number from $$$1$$$ to $$$6$$$, each number from $$$1$$$ to $$$6$$$ is used once.

Taisia rolls all $$$n$$$ dice at the same time and gets a sequence of values $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 6$$$), where $$$a_i$$$ is the value on the upper face of the $$$i$$$-th dice. The sum of this sequence is equal to $$$s$$$.

Suddenly, Taisia's pet cat steals exactly one dice with maximum value $$$a_i$$$ and calculates the sum of the values on the remaining $$$n-1$$$ dice, which is equal to $$$r$$$.

You only know the number of dice $$$n$$$ and the values of $$$s$$$, $$$r$$$. Restore a possible sequence $$$a$$$ that fulfills the constraints.

## Input Format
The first line contains the integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

Each testcase is given on a separate line and contains three integers $$$n$$$, $$$s$$$, $$$r$$$ ($$$2 \le n \le 50$$$, $$$1 \le r < s \le 300$$$).

It is guaranteed that a solution exists.

## Output Format
For each testcase, print: $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ in any order. It is guaranteed that such sequence exists.

If there are multiple solutions, print any.

## Examples
```input
7
2 2 1
2 4 2
4 9 5
5 17 11
3 15 10
4 4 3
5 20 15
```
```output
1 1
2 2 
1 2 2 4
6 4 2 3 2
5 5 5
1 1 1 1
1 4 5 5 5
```

Now solve the problem and return the code.