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

# Problem
You are given two arrays $$$a$$$ and $$$b$$$ both of length $$$n$$$.

You will merge$$$^\dagger$$$ these arrays forming another array $$$c$$$ of length $$$2 \cdot n$$$. You have to find the maximum length of a subarray consisting of equal values across all arrays $$$c$$$ that could be obtained.

$$$^\dagger$$$ A merge of two arrays results in an array $$$c$$$ composed by successively taking the first element of either array (as long as that array is nonempty) and removing it. After this step, the element is appended to the back of $$$c$$$. We repeat this operation as long as we can (i.e. at least one array is nonempty).

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 2 \cdot n$$$) — the elements of array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \le b_i \le 2 \cdot n$$$) — the elements of array $$$b$$$.

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

## Output Format
For each test case, output the maximum length of a subarray consisting of equal values across all merges.

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

## Note
In the first test case, we can only make $$$c=[2,2]$$$, thus the answer is $$$2$$$.

In the second test case, since all values are distinct, the answer must be $$$1$$$.

In the third test case, the arrays $$$c$$$ we can make are $$$[1,2,1,2]$$$, $$$[1,2,2,1]$$$, $$$[2,1,1,2]$$$, $$$[2,1,2,1]$$$. We can see that the answer is $$$2$$$ when we choose $$$c=[1,2,2,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 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: 256.0 MB

# Problem
Call an array $$$a$$$ of length $$$n$$$ sorted if $$$a_1 \leq a_2 \leq \ldots \leq a_{n-1} \leq a_n$$$.

Ntarsis has an array $$$a$$$ of length $$$n$$$.

He is allowed to perform one type of operation on it (zero or more times):

- Choose an index $$$i$$$ ($$$1 \leq i \leq n-1$$$).
- Add $$$1$$$ to $$$a_1, a_2, \ldots, a_i$$$.
- Subtract $$$1$$$ from $$$a_{i+1}, a_{i+2}, \ldots, a_n$$$.

The values of $$$a$$$ can be negative after an operation.

Determine the minimum operations needed to make $$$a$$$ not sorted.

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

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

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the values of array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$500$$$.

## Output Format
Output the minimum number of operations needed to make the array not sorted.

## Examples
```input
4
2
1 1
4
1 8 10 13
3
1 3 2
3
1 9 14
```
```output
1
2
0
3
```

## Note
In the first case, we can perform $$$1$$$ operation to make the array not sorted:

- Pick $$$i = 1$$$. The array $$$a$$$ then becomes $$$[2, 0]$$$, which is not sorted.

In the second case, we can perform $$$2$$$ operations to make the array not sorted:

- Pick $$$i = 3$$$. The array $$$a$$$ then becomes $$$[2, 9, 11, 12]$$$.
- Pick $$$i = 3$$$. The array $$$a$$$ then becomes $$$[3, 10, 12, 11]$$$, which is not sorted.

It can be proven that $$$1$$$ and $$$2$$$ operations are the minimal numbers of operations in the first and second test cases, respectively.

In the third case, the array is already not sorted, so we perform $$$0$$$ operations.

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: 256.0 MB

# Problem
Ntarsis has received two integers $$$n$$$ and $$$k$$$ for his birthday. He wonders how many fibonacci-like sequences of length $$$k$$$ can be formed with $$$n$$$ as the $$$k$$$-th element of the sequence.

A sequence of non-decreasing non-negative integers is considered fibonacci-like if $$$f_i = f_{i-1} + f_{i-2}$$$ for all $$$i > 2$$$, where $$$f_i$$$ denotes the $$$i$$$-th element in the sequence. Note that $$$f_1$$$ and $$$f_2$$$ can be arbitrary.

For example, sequences such as $$$[4,5,9,14]$$$ and $$$[0,1,1]$$$ are considered fibonacci-like sequences, while $$$[0,0,0,1,1]$$$, $$$[1, 2, 1, 3]$$$, and $$$[-1,-1,-2]$$$ are not: the first two do not always satisfy $$$f_i = f_{i-1} + f_{i-2}$$$, the latter does not satisfy that the elements are non-negative.

Impress Ntarsis by helping him with this task.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$), the number of test cases. The description of each test case is as follows.

Each test case contains two integers, $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$3 \leq k \leq 10^9$$$).

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

## Output Format
For each test case output an integer, the number of fibonacci-like sequences of length $$$k$$$ such that the $$$k$$$-th element in the sequence is $$$n$$$. That is, output the number of sequences $$$f$$$ of length $$$k$$$ so $$$f$$$ is a fibonacci-like sequence and $$$f_k = n$$$. It can be shown this number is finite.

## Examples
```input
8
22 4
3 9
55 11
42069 6
69420 4
69 1434
1 3
1 4
```
```output
4
0
1
1052
11571
0
1
0
```

## Note
There are $$$4$$$ valid fibonacci-like sequences for $$$n = 22$$$, $$$k = 4$$$:

- $$$[6,8,14,22]$$$,
- $$$[4,9,13,22]$$$,
- $$$[2,10,12,22]$$$,
- $$$[0,11,11,22]$$$.

For $$$n = 3$$$, $$$k = 9$$$, it can be shown that there are no fibonacci-like sequences satisfying the given conditions.

For $$$n = 55$$$, $$$k = 11$$$, $$$[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]$$$ is the only fibonacci-like sequence.

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: 256.0 MB

# Problem
Recently, Tema and Vika celebrated Family Day. Their friend Arina gave them a carpet, which can be represented as an $$$n \cdot m$$$ table of lowercase Latin letters.

Vika hasn't seen the gift yet, but Tema knows what kind of carpets she likes. Vika will like the carpet if she can read her name on. She reads column by column from left to right and chooses one or zero letters from current column.

Formally, the girl will like the carpet if it is possible to select four distinct columns in order from left to right such that the first column contains "v", the second one contains "i", the third one contains "k", and the fourth one contains "a".

Help Tema understand in advance whether Vika will like Arina's gift.

## Input Format
Each test consists of multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 20$$$) — the sizes of the carpet.

The next $$$n$$$ lines contain $$$m$$$ lowercase Latin letters each, describing the given carpet.

## Output Format
For each set of input data, output "YES" if Vika will like the carpet, otherwise output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

## Examples
```input
5
1 4
vika
3 3
bad
car
pet
4 4
vvvv
iiii
kkkk
aaaa
4 4
vkak
iiai
avvk
viaa
4 7
vbickda
vbickda
vbickda
vbickda
```
```output
YES
NO
YES
NO
YES
```

## Note
In the first sample, Vika can read her name from left to right.

In the second sample, Vika cannot read the character "v", so she will not like the carpet.

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: 256.0 MB

# Problem
Tema and Vika are playing the following game.

First, Vika comes up with a sequence of positive integers $$$a$$$ of length $$$m$$$ and writes it down on a piece of paper. Then she takes a new piece of paper and writes down the sequence $$$b$$$ according to the following rule:

- First, she writes down $$$a_1$$$.
- Then, she writes down only those $$$a_i$$$ ($$$2 \le i \le m$$$) such that $$$a_{i - 1} \le a_i$$$. Let the length of this sequence be denoted as $$$n$$$.

For example, from the sequence $$$a=[4, 3, 2, 6, 3, 3]$$$, Vika will obtain the sequence $$$b=[4, 6, 3]$$$.

She then gives the piece of paper with the sequence $$$b$$$ to Tema. He, in turn, tries to guess the sequence $$$a$$$.

Tema considers winning in such a game highly unlikely, but still wants to find at least one sequence $$$a$$$ that could have been originally chosen by Vika. Help him and output any such sequence.

Note that the length of the sequence you output should not exceed the input sequence length by more than two times.

## Input Format
Each test consists of multiple test cases. The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. This is followed by a description of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the sequence $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$b_1, b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the elements of the sequence.

The sum of the values of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output two lines. In the first line, output a single integer $$$m$$$ — the length of the sequence ($$$n \le m \le 2 \cdot n$$$). In the second line, output $$$m$$$ integers $$$a_1, a_2, a_3, \dots, a_m$$$ ($$$1 \le a_i \le 10^9$$$) — the assumed sequence that Vika could have written on the first piece of paper.

If there are multiple suitable sequences, you can output any of them.

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

## Note
The first sample is explained in the problem statement.

In the second sample, Vika could have chosen the original sequence.

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: 256.0 MB

# Problem
Tema decided to improve his ice cream making skills. He has already learned how to make ice cream in a cone using exactly two balls.

Before his ice cream obsession, Tema was interested in mathematics. Therefore, he is curious about the minimum number of balls he needs to have in order to make exactly $$$n$$$ different types of ice cream.

There are plenty possible ice cream flavours: $$$1, 2, 3, \dots$$$. Tema can make two-balls ice cream with any flavours (probably the same).

Two ice creams are considered different if their sets of ball flavours are different. For example, $$$\{1, 2\} = \{2, 1\}$$$, but $$$\{1, 1\} \neq \{1, 2\}$$$.

For example, having the following ice cream balls: $$$\{1, 1, 2\}$$$, Tema can make only two types of ice cream: $$$\{1, 1\}$$$ and $$$\{1, 2\}$$$.

Note, that Tema do not need to make all the ice cream cones at the same time. This means that he making ice cream cones independently. Also in order to make a following cone $$$\{x, x\}$$$ for some $$$x$$$, Tema needs at least $$$2$$$ balls of type $$$x$$$.

Help Tema answer this question. It can be shown that answer always exist.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — the number of ice cream types that Tema wants to make.

## Output Format
For each test case, output a single integer — the minimum number of balls Tema needs to buy.

## Examples
```input
5
1
3
6
179
1000000000000000000
```
```output
2
3
4
27
2648956421
```

## Note
In the first sample, it is enough to have following balls types: $$$\{1, 1\}$$$. Note, that set $$$\{1\}$$$ if not enough since we need at least $$$2$$$ balls of a type $$$1$$$ in order to make such cone $$$\{1, 1\}$$$.

In the second sample, it is not possible to make it with $$$2$$$ balls, but it can be done with these balls: $$$\{1, 2, 3\}$$$.

In the third sample, $$$\{1, 2, 3, 4\}$$$ is optimal answer, so we can get following ice cream cones: $$$\{1, 2\}$$$, $$$\{1, 3\}$$$, $$$\{1, 4\}$$$, $$$\{2, 3\}$$$, $$$\{2, 4\}$$$, $$$\{3, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Chaneka, Pak Chanek's child, is an ambitious kid, so Pak Chanek gives her the following problem to test her ambition.

Given an array of integers $$$[A_1, A_2, A_3, \ldots, A_N]$$$. In one operation, Chaneka can choose one element, then increase or decrease the element's value by $$$1$$$. Chaneka can do that operation multiple times, even for different elements.

What is the minimum number of operations that must be done to make it such that $$$A_1 \times A_2 \times A_3 \times \ldots \times A_N = 0$$$?

## Input Format
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$).

The second line contains $$$N$$$ integers $$$A_1, A_2, A_3, \ldots, A_N$$$ ($$$-10^5 \leq A_i \leq 10^5$$$).

## Output Format
An integer representing the minimum number of operations that must be done to make it such that $$$A_1 \times A_2 \times A_3 \times \ldots \times A_N = 0$$$.

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

## Note
In the first example, initially, $$$A_1\times A_2\times A_3=2\times(-6)\times5=-60$$$. Chaneka can do the following sequence of operations:

1. Decrease the value of $$$A_1$$$ by $$$1$$$. Then, $$$A_1\times A_2\times A_3=1\times(-6)\times5=-30$$$
2. Decrease the value of $$$A_1$$$ by $$$1$$$. Then, $$$A_1\times A_2\times A_3=0\times(-6)\times5=0$$$

In the third example, Chaneka does not have to do any operations, because from the start, it already holds that $$$A_1\times A_2\times A_3\times A_4\times A_5=0\times(-1)\times0\times1\times0=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 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
Pak Chanek observes that the carriages of a train is always full on morning departure hours and afternoon departure hours. Therefore, the balance between carriages is needed so that it is not too crowded in only a few carriages.

A train contains $$$N$$$ carriages that are numbered from $$$1$$$ to $$$N$$$ from left to right. Carriage $$$i$$$ initially contains $$$A_i$$$ passengers. All carriages are connected by carriage doors, namely for each $$$i$$$ ($$$1\leq i\leq N-1$$$), carriage $$$i$$$ and carriage $$$i+1$$$ are connected by a two-way door.

Each passenger can move between carriages, but train regulation regulates that for each $$$i$$$, a passenger that starts from carriage $$$i$$$ cannot go through more than $$$D_i$$$ doors.

Define $$$Z$$$ as the most number of passengers in one same carriage after moving. Pak Chanek asks, what is the minimum possible value of $$$Z$$$?

## Input Format
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 2\cdot10^5$$$) — the number of carriages.

The second line contains $$$N$$$ integers $$$A_1, A_2, A_3, \ldots, A_N$$$ ($$$0 \leq A_i \leq 10^9$$$) — the initial number of passengers in each carriage.

The third line contains $$$N$$$ integers $$$D_1, D_2, D_3, \ldots, D_N$$$ ($$$0 \leq D_i \leq N-1$$$) — the maximum limit of the number of doors for each starting carriage.

## Output Format
An integer representing the minimum possible value of $$$Z$$$.

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

## Note
One strategy that is optimal is as follows:

- $$$5$$$ people in carriage $$$1$$$ move to carriage $$$4$$$ (going through $$$3$$$ doors).
- $$$3$$$ people in carriage $$$5$$$ move to carriage $$$3$$$ (going through $$$2$$$ doors).
- $$$2$$$ people in carriage $$$6$$$ move to carriage $$$5$$$ (going through $$$1$$$ door).
- $$$1$$$ person in carriage $$$6$$$ moves to carriage $$$7$$$ (going through $$$1$$$ door).

The number of passengers in each carriage becomes $$$[2,4,5,5,4,5,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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Define a set $$$A$$$ as a child of set $$$B$$$ if and only if for each element of value $$$x$$$ that is in $$$A$$$, there exists an element of value $$$x+1$$$ that is in $$$B$$$.

Given integers $$$N$$$ and $$$K$$$. In order to make Chaneka happy, you must find the number of different arrays containing $$$N$$$ sets $$$[S_1, S_2, S_3, \ldots, S_N]$$$ such that: - Each set can only contain zero or more different integers from $$$1$$$ to $$$K$$$. - There exists a way to rearrange the order of the array of sets into $$$[S'_1, S'_2, S'_3, \ldots, S'_N]$$$ such that $$$S'_i$$$ is a child of $$$S'_{i+1}$$$ for each $$$1\leq i\leq N-1$$$.

Print the answer modulo $$$998\,244\,353$$$.

Two sets are considered different if and only if there is at least one value that only occurs in one of the two sets.

Two arrays of sets are considered different if and only if there is at least one index $$$i$$$ such that the sets at index $$$i$$$ in the two arrays are different.

## Input Format
The only line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N,K \leq 2\cdot10^5$$$) — the number of sets in the array and the maximum limit for the values in the sets.

## Output Format
An integer representing the number of different arrays of sets that satisfy the problem condition, modulo $$$998\,244\,353$$$.

## Examples
```input
2 2
```
```output
11
```
-----
```input
1 3
```
```output
8
```
-----
```input
3 1
```
```output
4
```

## Note
In the first example, there are $$$11$$$ different arrays of sets possible, which are:

- $$$[\{\}, \{\}]$$$
- $$$[\{\}, \{1\}]$$$
- $$$[\{\}, \{1, 2\}]$$$
- $$$[\{\}, \{2\}]$$$
- $$$[\{1\}, \{\}]$$$
- $$$[\{1\}, \{1, 2\}]$$$
- $$$[\{1\}, \{2\}]$$$
- $$$[\{1, 2\}, \{\}]$$$
- $$$[\{1, 2\}, \{1\}]$$$
- $$$[\{2\}, \{\}]$$$
- $$$[\{2\}, \{1\}]$$$

Now solve the problem and return the code.