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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a binary array$$$^{\dagger}$$$ of length $$$n$$$. You are allowed to perform one operation on it at most once. In an operation, you can choose any element and flip it: turn a $$$0$$$ into a $$$1$$$ or vice-versa.

What is the maximum number of inversions$$$^{\ddagger}$$$ the array can have after performing at most one operation?

$$$^\dagger$$$ A binary array is an array that contains only zeroes and ones.

$$$^\ddagger$$$ The number of inversions in an array is the number of pairs of indices $$$i,j$$$ such that $$$i<j$$$ and $$$a_i > a_j$$$.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the array.

The following line contains $$$n$$$ space-separated positive integers $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$ ($$$0 \leq a_i \leq 1$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

## Output Format
For each test case, output a single integer  — the maximum number of inversions the array can have after performing at most one operation.

## Examples
```input
5
4
1 0 1 0
6
0 1 0 0 1 0
2
0 0
8
1 0 1 1 0 0 0 1
3
1 1 1
```
```output
3
7
1
13
2
```

## Note
For the first test case, the inversions are initially formed by the pairs of indices ($$$1, 2$$$), ($$$1, 4$$$), ($$$3, 4$$$), being a total of $$$3$$$, which already is the maximum possible.

For the second test case, the inversions are initially formed by the pairs of indices ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$5, 6$$$), being a total of four. But, by flipping the first element, the array becomes $$${1, 1, 0, 0, 1, 0}$$$, which has the inversions formed by the pairs of indices ($$$1, 3$$$), ($$$1, 4$$$), ($$$1, 6$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$5, 6$$$) which total to $$$7$$$ inversions which is the maximum possible.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 512.0 MB

# Problem
Recently, Mishka started noticing that his keyboard malfunctions — maybe it's because he was playing rhythm games too much. Empirically, Mishka has found out that every other time he presses a key, it is registered as if the key was pressed twice. For example, if Mishka types text, the first time he presses a key, exactly one letter is printed; the second time he presses a key, two same letters are printed; the third time he presses a key, one letter is printed; the fourth time he presses a key, two same letters are printed, and so on. Note that the number of times a key was pressed is counted for the whole keyboard, not for each key separately. For example, if Mishka tries to type the word osu, it will be printed on the screen as ossu.

You are given a word consisting of $$$n$$$ lowercase Latin letters. You have to determine if it can be printed on Mishka's keyboard or not. You may assume that Mishka cannot delete letters from the word, and every time he presses a key, the new letter (or letters) is appended to the end of the word.

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

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the word.

The second line of the test case contains a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters — the word that should be checked.

## Output Format
For each test case, print YES if the word $$$s$$$ can be printed on Mishka's keyboard, and NO otherwise.

## Examples
```input
4
4
ossu
2
aa
6
addonn
3
qwe
```
```output
YES
NO
YES
NO
```

## Note
In the first test case, Mishka can type the word as follows: press o (one letter o appears at the end of the word), then presses s (two letters s appear at the end of the word), and, finally, press u (one letter appears at the end of the word, making the resulting word ossu).

In the second test case, Mishka can try typing the word as follows: press a (one letter a appears at the end of the word). But if he tries to press a one more time, two letters a will appear at the end of the word, so it is impossible to print the word using his keyboard.

In the fourth test case, Mishka has to start by pressing q. Then, if he presses w, two copies of w will appear at the end of the word, but the third letter should be e instead of w, so 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 python3.

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:
```python
<your code here>
```

Execution time limit: 15.0 seconds
Memory limit: 1024.0 MB

# Problem
Consider a deck of cards. Each card has one of $$$4$$$ suits, and there are exactly $$$n$$$ cards for each suit — so, the total number of cards in the deck is $$$4n$$$. The deck is shuffled randomly so that each of $$$(4n)!$$$ possible orders of cards in the deck has the same probability of being the result of shuffling. Let $$$c_i$$$ be the $$$i$$$-th card of the deck (from top to bottom).

Monocarp starts drawing the cards from the deck one by one. Before drawing a card, he tries to guess its suit. Monocarp remembers the suits of the $$$k$$$ last cards, and his guess is the suit that appeared the least often among the last $$$k$$$ cards he has drawn. So, while drawing the $$$i$$$-th card, Monocarp guesses that its suit is the suit that appears the minimum number of times among the cards $$$c_{i-k}, c_{i-k+1}, \dots, c_{i-1}$$$ (if $$$i \le k$$$, Monocarp considers all previously drawn cards, that is, the cards $$$c_1, c_2, \dots, c_{i-1}$$$). If there are multiple suits that appeared the minimum number of times among the previous cards Monocarp remembers, he chooses a random suit out of those for his guess (all suits that appeared the minimum number of times have the same probability of being chosen).

After making a guess, Monocarp draws a card and compares its suit to his guess. If they match, then his guess was correct; otherwise it was incorrect.

Your task is to calculate the expected number of correct guesses Monocarp makes after drawing all $$$4n$$$ cards from the deck.

## Input Format
The first (and only) line contains two integers $$$n$$$ ($$$1 \le n \le 500$$$) and $$$k$$$ ($$$1 \le k \le 4 \cdot n$$$).

## Output Format
Let the expected value you have to calculate be an irreducible fraction $$$\dfrac{x}{y}$$$. Print one integer — the value of $$$x \cdot y^{-1} \bmod 998244353$$$, where $$$y^{-1}$$$ is the inverse to $$$y$$$ (i. e. an integer such that $$$y \cdot y^{-1} \bmod 998244353 = 1$$$).

## Examples
```input
1 1
```
```output
748683266
```
-----
```input
3 2
```
```output
567184295
```
-----
```input
2 7
```
```output
373153250
```
-----
```input
2 8
```
```output
373153250
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 512.0 MB

# Problem
Monocarp wants to watch $$$n$$$ videos. Each video is only one minute long, but its size may be arbitrary. The $$$i$$$-th video has the size $$$a_i$$$ megabytes. All videos are published on the Internet. A video should be downloaded before it can be watched. Monocarp has poor Internet connection — it takes exactly $$$1$$$ minute to download $$$1$$$ megabyte of data, so it will require $$$a_i$$$ minutes to download the $$$i$$$-th video.

Monocarp's computer has a hard disk of $$$m$$$ megabytes. The disk is used to store the downloaded videos. Once Monocarp starts the download of a video of size $$$s$$$, the $$$s$$$ megabytes are immediately reserved on a hard disk. If there are less than $$$s$$$ megabytes left, the download cannot be started until the required space is freed. Each single video can be stored on the hard disk, since $$$a_i \le m$$$ for all $$$i$$$. Once the download is started, it cannot be interrupted. It is not allowed to run two or more downloads in parallel.

Once a video is fully downloaded to the hard disk, Monocarp can watch it. Watching each video takes exactly $$$1$$$ minute and does not occupy the Internet connection, so Monocarp can start downloading another video while watching the current one.

When Monocarp finishes watching a video, he doesn't need it on the hard disk anymore, so he can delete the video, instantly freeing the space it occupied on a hard disk. Deleting a video takes negligible time.

Monocarp wants to watch all $$$n$$$ videos as quickly as possible. The order of watching does not matter, since Monocarp needs to watch all of them anyway. Please calculate the minimum possible time required for that.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 10^9$$$) — the number of videos Monocarp wants to watch and the size of the hard disk, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le m$$$) — the sizes of the videos.

## Output Format
Print one integer — the minimum time required to watch all $$$n$$$ videos.

## Examples
```input
5 6
1 2 3 4 5
```
```output
16
```
-----
```input
5 5
1 2 3 4 5
```
```output
17
```
-----
```input
4 3
1 3 2 3
```
```output
12
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Monocarp is playing a MMORPG. There are two commonly used types of currency in this MMORPG — gold coins and silver coins. Monocarp wants to buy a new weapon for his character, and that weapon costs $$$n$$$ silver coins. Unfortunately, right now, Monocarp has no coins at all.

Monocarp can earn gold coins by completing quests in the game. Each quest yields exactly one gold coin. Monocarp can also exchange coins via the in-game trading system. Monocarp has spent days analyzing the in-game economy; he came to the following conclusion: it is possible to sell one gold coin for $$$a$$$ silver coins (i. e. Monocarp can lose one gold coin to gain $$$a$$$ silver coins), or buy one gold coin for $$$b$$$ silver coins (i. e. Monocarp can lose $$$b$$$ silver coins to gain one gold coin).

Now Monocarp wants to calculate the minimum number of quests that he has to complete in order to have at least $$$n$$$ silver coins after some abuse of the in-game economy. Note that Monocarp can perform exchanges of both types (selling and buying gold coins for silver coins) any number of times.

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

Each test case consists of one line containing three integers $$$n$$$, $$$a$$$ and $$$b$$$ ($$$1 \le n \le 10^7$$$; $$$1 \le a, b \le 50$$$).

## Output Format
For each test case, print one integer — the minimum possible number of quests Monocarp has to complete.

## Examples
```input
4
100 25 30
9999997 25 50
52 50 48
49 50 1
```
```output
4
400000
1
1
```

## Note
In the first test case of the example, Monocarp should complete $$$4$$$ quests, and then sell $$$4$$$ gold coins for $$$100$$$ silver coins.

In the second test case, Monocarp should complete $$$400000$$$ quests, and then sell $$$400000$$$ gold coins for $$$10$$$ million silver coins.

In the third test case, Monocarp should complete $$$1$$$ quest, sell the gold coin for $$$50$$$ silver coins, buy a gold coin for $$$48$$$ silver coins, and then sell it again for $$$50$$$ coins. So, he will have $$$52$$$ silver coins.

In the fourth test case, Monocarp should complete $$$1$$$ quest and then sell the gold coin he has obtained for $$$50$$$ silver coins.

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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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 python3.

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:
```python
<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.