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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The game of Berland poker is played with a deck of $$$n$$$ cards, $$$m$$$ of which are jokers. $$$k$$$ players play this game ($$$n$$$ is divisible by $$$k$$$).

At the beginning of the game, each player takes $$$\frac{n}{k}$$$ cards from the deck (so each card is taken by exactly one player). The player who has the maximum number of jokers is the winner, and he gets the number of points equal to $$$x - y$$$, where $$$x$$$ is the number of jokers in the winner's hand, and $$$y$$$ is the maximum number of jokers among all other players. If there are two or more players with maximum number of jokers, all of them are winners and they get $$$0$$$ points.

Here are some examples:

- $$$n = 8$$$, $$$m = 3$$$, $$$k = 2$$$. If one player gets $$$3$$$ jokers and $$$1$$$ plain card, and another player gets $$$0$$$ jokers and $$$4$$$ plain cards, then the first player is the winner and gets $$$3 - 0 = 3$$$ points;
- $$$n = 4$$$, $$$m = 2$$$, $$$k = 4$$$. Two players get plain cards, and the other two players get jokers, so both of them are winners and get $$$0$$$ points;
- $$$n = 9$$$, $$$m = 6$$$, $$$k = 3$$$. If the first player gets $$$3$$$ jokers, the second player gets $$$1$$$ joker and $$$2$$$ plain cards, and the third player gets $$$2$$$ jokers and $$$1$$$ plain card, then the first player is the winner, and he gets $$$3 - 2 = 1$$$ point;
- $$$n = 42$$$, $$$m = 0$$$, $$$k = 7$$$. Since there are no jokers, everyone gets $$$0$$$ jokers, everyone is a winner, and everyone gets $$$0$$$ points.

Given $$$n$$$, $$$m$$$ and $$$k$$$, calculate the maximum number of points a player can get for winning the game.

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

Then the test cases follow. Each test case contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 50$$$, $$$0 \le m \le n$$$, $$$2 \le k \le n$$$, $$$k$$$ is a divisors of $$$n$$$).

## Output Format
For each test case, print one integer — the maximum number of points a player can get for winning the game.

## Examples
```input
4
8 3 2
4 2 4
9 6 3
42 0 7
```
```output
3
0
1
0
```

## Note
Test cases of the example are described in the statement.

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
There are two infinite sources of water:

- hot water of temperature $$$h$$$;
- cold water of temperature $$$c$$$ ($$$c < h$$$).

You perform the following procedure of alternating moves:

1. take one cup of the hot water and pour it into an infinitely deep barrel;
2. take one cup of the cold water and pour it into an infinitely deep barrel;
3. take one cup of the hot water $$$\dots$$$
4. and so on $$$\dots$$$

Note that you always start with the cup of hot water.

The barrel is initially empty. You have to pour at least one cup into the barrel. The water temperature in the barrel is an average of the temperatures of the poured cups.

You want to achieve a temperature as close as possible to $$$t$$$. So if the temperature in the barrel is $$$t_b$$$, then the absolute difference of $$$t_b$$$ and $$$t$$$ ($$$|t_b - t|$$$) should be as small as possible.

How many cups should you pour into the barrel, so that the temperature in it is as close as possible to $$$t$$$? If there are multiple answers with the minimum absolute difference, then print the smallest of them.

## Input Format
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 3 \cdot 10^4$$$) — the number of testcases.

Each of the next $$$T$$$ lines contains three integers $$$h$$$, $$$c$$$ and $$$t$$$ ($$$1 \le c < h \le 10^6$$$; $$$c \le t \le h$$$) — the temperature of the hot water, the temperature of the cold water and the desired temperature in the barrel.

## Output Format
For each testcase print a single positive integer — the minimum number of cups required to be poured into the barrel to achieve the closest temperature to $$$t$$$.

## Examples
```input
3
30 10 20
41 15 30
18 13 18
```
```output
2
7
1
```

## Note
In the first testcase the temperature after $$$2$$$ poured cups: $$$1$$$ hot and $$$1$$$ cold is exactly $$$20$$$. So that is the closest we can achieve.

In the second testcase the temperature after $$$7$$$ poured cups: $$$4$$$ hot and $$$3$$$ cold is about $$$29.857$$$. Pouring more water won't get us closer to $$$t$$$ than that.

In the third testcase the temperature after $$$1$$$ poured cup: $$$1$$$ hot is $$$18$$$. That's exactly equal to $$$t$$$.

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.5 seconds
Memory limit: 512.0 MB

# Problem
Alice and Bob are playing yet another card game. This time the rules are the following. There are $$$n$$$ cards lying in a row in front of them. The $$$i$$$-th card has value $$$a_i$$$.

First, Alice chooses a non-empty consecutive segment of cards $$$[l; r]$$$ ($$$l \le r$$$). After that Bob removes a single card $$$j$$$ from that segment $$$(l \le j \le r)$$$. The score of the game is the total value of the remaining cards on the segment $$$(a_l + a_{l + 1} + \dots + a_{j - 1} + a_{j + 1} + \dots + a_{r - 1} + a_r)$$$. In particular, if Alice chooses a segment with just one element, then the score after Bob removes the only card is $$$0$$$.

Alice wants to make the score as big as possible. Bob takes such a card that the score is as small as possible.

What segment should Alice choose so that the score is maximum possible? Output the maximum score.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-30 \le a_i \le 30$$$) — the values on the cards.

## Output Format
Print a single integer — the final score of the game.

## Examples
```input
5
5 -2 10 -1 4
```
```output
6
```
-----
```input
8
5 2 5 3 -30 -30 6 9
```
```output
10
```
-----
```input
3
-10 6 -15
```
```output
0
```

## Note
In the first example Alice chooses a segment $$$[1;5]$$$ — the entire row of cards. Bob removes card $$$3$$$ with the value $$$10$$$ from the segment. Thus, the final score is $$$5 + (-2) + (-1) + 4 = 6$$$.

In the second example Alice chooses a segment $$$[1;4]$$$, so that Bob removes either card $$$1$$$ or $$$3$$$ with the value $$$5$$$, making the answer $$$5 + 2 + 3 = 10$$$.

In the third example Alice can choose any of the segments of length $$$1$$$: $$$[1;1]$$$, $$$[2;2]$$$ or $$$[3;3]$$$. Bob removes the only card, so the score is $$$0$$$. If Alice chooses some other segment then the answer will be less than $$$0$$$.

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
We define $$$x \bmod y$$$ as the remainder of division of $$$x$$$ by $$$y$$$ ($$$\%$$$ operator in C++ or Java, mod operator in Pascal).

Let's call an array of positive integers $$$[a_1, a_2, \dots, a_k]$$$ stable if for every permutation $$$p$$$ of integers from $$$1$$$ to $$$k$$$, and for every non-negative integer $$$x$$$, the following condition is met:

$$$ (((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k = (((x \bmod a_{p_1}) \bmod a_{p_2}) \dots \bmod a_{p_{k - 1}}) \bmod a_{p_k} $$$

That is, for each non-negative integer $$$x$$$, the value of $$$(((x \bmod a_1) \bmod a_2) \dots \bmod a_{k - 1}) \bmod a_k$$$ does not change if we reorder the elements of the array $$$a$$$.

For two given integers $$$n$$$ and $$$k$$$, calculate the number of stable arrays $$$[a_1, a_2, \dots, a_k]$$$ such that $$$1 \le a_1 < a_2 < \dots < a_k \le n$$$.

## Input Format
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 5 \cdot 10^5$$$).

## Output Format
Print one integer — the number of stable arrays $$$[a_1, a_2, \dots, a_k]$$$ such that $$$1 \le a_1 < a_2 < \dots < a_k \le n$$$. Since the answer may be large, print it modulo $$$998244353$$$.

## Examples
```input
7 3
```
```output
16
```
-----
```input
3 7
```
```output
0
```
-----
```input
1337 42
```
```output
95147305
```
-----
```input
1 1
```
```output
1
```
-----
```input
500000 1
```
```output
500000
```

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
Ehab loves number theory, but for some reason he hates the number $$$x$$$. Given an array $$$a$$$, find the length of its longest subarray such that the sum of its elements isn't divisible by $$$x$$$, or determine that such subarray doesn't exist.

An array $$$a$$$ is a subarray of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

## Input Format
The first line contains an integer $$$t$$$ $$$(1 \le t \le 5)$$$ — the number of test cases you need to solve. The description of the test cases follows.

The first line of each test case contains 2 integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le x \le 10^4$$$) — the number of elements in the array $$$a$$$ and the number that Ehab hates.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$0 \le a_i \le 10^4$$$) — the elements of the array $$$a$$$.

## Output Format
For each testcase, print the length of the longest subarray whose sum isn't divisible by $$$x$$$. If there's no such subarray, print $$$-1$$$.

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

## Note
In the first test case, the subarray $$$[2,3]$$$ has sum of elements $$$5$$$, which isn't divisible by $$$3$$$.

In the second test case, the sum of elements of the whole array is $$$6$$$, which isn't divisible by $$$4$$$.

In the third test case, all subarrays have an even sum, so the answer is $$$-1$$$.

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
Given a permutation $$$p$$$ of length $$$n$$$, find its subsequence $$$s_1$$$, $$$s_2$$$, $$$\ldots$$$, $$$s_k$$$ of length at least $$$2$$$ such that:

- $$$|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$$$ is as big as possible over all subsequences of $$$p$$$ with length at least $$$2$$$.
- Among all such subsequences, choose the one whose length, $$$k$$$, is as small as possible.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

A sequence $$$a$$$ is a subsequence of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deleting some (possibly, zero or all) elements.

A permutation of length $$$n$$$ is an array of length $$$n$$$ in which every element from $$$1$$$ to $$$n$$$ occurs exactly once.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 2 \cdot 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$$$ ($$$2 \le n \le 10^5$$$) — the length of the permutation $$$p$$$.

The second line of each test case contains $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_{n}$$$ ($$$1 \le p_i \le n$$$, $$$p_i$$$ are distinct) — the elements of the permutation $$$p$$$.

The sum of $$$n$$$ across the test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, the first line should contain the length of the found subsequence, $$$k$$$. The second line should contain $$$s_1$$$, $$$s_2$$$, $$$\ldots$$$, $$$s_k$$$ — its elements.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

## Examples
```input
2
3
3 2 1
4
1 3 4 2
```
```output
2
3 1 
3
1 4 2
```

## Note
In the first test case, there are $$$4$$$ subsequences of length at least $$$2$$$:

- $$$[3,2]$$$ which gives us $$$|3-2|=1$$$.
- $$$[3,1]$$$ which gives us $$$|3-1|=2$$$.
- $$$[2,1]$$$ which gives us $$$|2-1|=1$$$.
- $$$[3,2,1]$$$ which gives us $$$|3-2|+|2-1|=2$$$.

So the answer is either $$$[3,1]$$$ or $$$[3,2,1]$$$. Since we want the subsequence to be as short as possible, the answer is $$$[3,1]$$$.

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
Given an array $$$a$$$ of length $$$n$$$, find another array, $$$b$$$, of length $$$n$$$ such that:

- for each $$$i$$$ $$$(1 \le i \le n)$$$ $$$MEX(\{b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_i\})=a_i$$$.

The $$$MEX$$$ of a set of integers is the smallest non-negative integer that doesn't belong to this set.

If such array doesn't exist, determine this.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$0 \le a_i \le i$$$) — the elements of the array $$$a$$$. It's guaranteed that $$$a_i \le a_{i+1}$$$ for $$$1\le i < n$$$.

## Output Format
If there's no such array, print a single line containing $$$-1$$$.

Otherwise, print a single line containing $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_n$$$ ($$$0 \le b_i \le 10^6$$$)

If there are multiple answers, print any.

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

## Note
In the second test case, other answers like $$$[1,1,1,0]$$$, for example, are valid.

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
Given a connected undirected graph with $$$n$$$ vertices and an integer $$$k$$$, you have to either:

- either find an independent set that has exactly $$$\lceil\frac{k}{2}\rceil$$$ vertices.
- or find a simple cycle of length at most $$$k$$$.

An independent set is a set of vertices such that no two of them are connected by an edge. A simple cycle is a cycle that doesn't contain any vertex twice.

I have a proof that for any input you can always solve at least one of these problems, but it's left as an exercise for the reader.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$3 \le k \le n \le 10^5$$$, $$$n-1 \le m \le 2 \cdot 10^5$$$) — the number of vertices and edges in the graph, and the parameter $$$k$$$ from the statement.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$) that mean there's an edge between vertices $$$u$$$ and $$$v$$$. It's guaranteed that the graph is connected and doesn't contain any self-loops or multiple edges.

## Output Format
If you choose to solve the first problem, then on the first line print $$$1$$$, followed by a line containing $$$\lceil\frac{k}{2}\rceil$$$ distinct integers not exceeding $$$n$$$, the vertices in the desired independent set.

If you, however, choose to solve the second problem, then on the first line print $$$2$$$, followed by a line containing one integer, $$$c$$$, representing the length of the found cycle, followed by a line containing $$$c$$$ distinct integers not exceeding $$$n$$$, the vertices in the desired cycle, in the order they appear in the cycle.

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

## Note
In the first sample:

Notice that printing the independent set $$$\{2,4\}$$$ is also OK, but printing the cycle $$$1-2-3-4$$$ isn't, because its length must be at most $$$3$$$.

In the second sample:

Notice that printing the independent set $$$\{1,3\}$$$ or printing the cycle $$$2-1-4$$$ is also OK.

In the third sample:

In the fourth sample:

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
Leo has developed a new programming language C+=. In C+=, integer variables can only be changed with a "+=" operation that adds the right-hand side value to the left-hand side variable. For example, performing "a += b" when a = $$$2$$$, b = $$$3$$$ changes the value of a to $$$5$$$ (the value of b does not change).

In a prototype program Leo has two integer variables a and b, initialized with some positive values. He can perform any number of operations "a += b" or "b += a". Leo wants to test handling large integers, so he wants to make the value of either a or b strictly greater than a given value $$$n$$$. What is the smallest number of operations he has to perform?

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

Each of the following $$$T$$$ lines describes a single test case, and contains three integers $$$a, b, n$$$ ($$$1 \leq a, b \leq n \leq 10^9$$$) — initial values of a and b, and the value one of the variables has to exceed, respectively.

## Output Format
For each test case print a single integer — the smallest number of operations needed. Separate answers with line breaks.

## Examples
```input
2
1 2 3
5 4 100
```
```output
2
7
```

## Note
In the first case we cannot make a variable exceed $$$3$$$ in one operation. One way of achieving this in two operations is to perform "b += a" twice.

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
Karl likes Codeforces and subsequences. He wants to find a string of lowercase English letters that contains at least $$$k$$$ subsequences codeforces. Out of all possible strings, Karl wants to find a shortest one.

Formally, a codeforces subsequence of a string $$$s$$$ is a subset of ten characters of $$$s$$$ that read codeforces from left to right. For example, codeforces contains codeforces a single time, while codeforcesisawesome contains codeforces four times: codeforcesisawesome, codeforcesisawesome, codeforcesisawesome, codeforcesisawesome.

Help Karl find any shortest string that contains at least $$$k$$$ codeforces subsequences.

## Input Format
The only line contains a single integer $$$k$$$ ($$$1 \leq k \leq 10^{16})$$$.

## Output Format
Print a shortest string of lowercase English letters that contains at least $$$k$$$ codeforces subsequences. If there are several such strings, print any of them.

## Examples
```input
1
```
```output
codeforces
```
-----
```input
3
```
```output
codeforcesss
```

Now solve the problem and return the code.