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
Masha is going to participate in a talent show conducted by the university she studies at. She wants to impress the audience with lots of different magic tricks!

For one of her tricks, she uses $$$n$$$ sponge balls, one of which is a special one. First, she arranges the balls in a row in such a way that the special ball is put on position $$$k$$$ (positions are numbered from $$$1$$$ to $$$n$$$ from left to right). After that, she performs $$$m$$$ swaps: during the $$$i$$$-th swap, she chooses the ball on position $$$x_i$$$ and the ball on position $$$y_i$$$, and swaps them.

Since Masha is a magician, she fakes some of her actions to trick the audience — when she starts performing a swap, she may fake it, so it is not performed (but it looks like it is performed for the audience). There are no constraints on which swaps Masha should fake or should actually perform — for example, she may fake all of the swaps, or even not fake anything at all.

For the trick to work perfectly, the special ball should end up on a specific position — Masha has not decided yet, which position is perfect. Since faking swaps is difficult, for each position she wants to know the minimum number of swaps she has to fake so that the special ball ends up there.

Unfortunately, Masha is a magician, neither a mathematician nor a programmer. So she needs your help in calculating what she wants!

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — the number of balls, the number of swaps and the initial position of the special ball, respectively.

Then $$$m$$$ lines follow, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) denoting the $$$i$$$-th swap.

## Output Format
Print $$$n$$$ integers. The $$$i$$$-th integer should be the minimum number of swaps Masha has to fake so the special ball ends up on position $$$i$$$ (or $$$-1$$$, if Masha cannot put the special ball there).

## Examples
```input
4 5 1
3 4
2 1
4 1
3 1
3 1
```
```output
2 0 3 1
```
-----
```input
5 7 4
3 2
3 2
4 2
3 4
4 1
3 2
5 2
```
```output
2 2 0 3 1
```
-----
```input
7 15 5
5 3
4 2
6 1
2 4
1 6
3 7
5 6
4 2
6 4
2 6
6 3
6 3
7 6
2 6
7 2
```
```output
-1 1 1 1 2 1 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: 256.0 MB

# Problem
You have two IP cameras of the same model. Each camera can take photos starting from some moment of time with a fixed period. You can freely choose the starting moment but you can choose the period only as one of $$$k$$$ values $$$p_1, p_2, \dots, p_k$$$ which are chosen by the camera's manufacturer.

You have $$$n$$$ moments of interest $$$x_1, x_2, \dots, x_n$$$. You'd like to configure both cameras in such a way that at least one camera will take a photo in each of these moments. Configuring the camera means setting the moment when it takes the first photo and the gap between two consecutive photos (which should be one of the values $$$p_1, p_2, \dots, p_k$$$). It's not a problem for you that cameras can take photos at other moments of time — you only care about moments of interest.

## Input Format
The first line contains two integers $$$k$$$ and $$$n$$$ ($$$1 \le k \le 10^5$$$; $$$2 \le n \le 10^5$$$) — the number of periods to choose and the number of moments of interest.

The second line contains $$$k$$$ integers $$$p_1, p_2, \dots, p_k$$$ ($$$1 \le p_1 < p_2 < \dots < p_k \le 10^6$$$) — the periods to choose in the ascending order.

The third line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_1 < x_2 < \dots < x_n \le 10^6$$$) — the moments of interest in the ascending order.

## Output Format
Print YES (case insensitive) in the first line if there is a way to configure cameras.

In the second line, print two integers $$$s_1$$$ and $$$cp_1$$$ ($$$1 \le s_1 \le 10^6$$$; $$$1 \le cp_1 \le 10^6$$$; $$$cp_1 \in \{p_1, \dots, p_k\}$$$) — the starting moment and the period for the first camera. The period should be one of the given periods.

In the third line, print two integers $$$s_2$$$ and $$$cp_2$$$ ($$$1 \le s_2 \le 10^6$$$; $$$1 \le cp_2 \le 10^6$$$; $$$cp_2 \in \{p_1, \dots, p_k\}$$$) — the starting moment and the period for the second camera. The period should be one of the given periods.

If there is no way to configure cameras, print NO (case insensitive). If there are multiple ways, you may print any of them.

## Examples
```input
3 5
3 5 7
1 4 5 7 12
```
```output
YES
1 3
5 7
```
-----
```input
3 2
1 2 3
1 10
```
```output
YES
1 1
10 1
```
-----
```input
3 4
1 2 3
5 7 9 11
```
```output
YES
5 1
5 1
```
-----
```input
3 4
10 20 100
2 3 4 7
```
```output
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Alica and Bob are playing a game.

Initially they have a binary string $$$s$$$ consisting of only characters 0 and 1.

Alice and Bob make alternating moves: Alice makes the first move, Bob makes the second move, Alice makes the third one, and so on. During each move, the current player must choose two different adjacent characters of string $$$s$$$ and delete them. For example, if $$$s = 1011001$$$ then the following moves are possible:

1. delete $$$s_1$$$ and $$$s_2$$$: $$$\textbf{10}11001 \rightarrow 11001$$$;
2. delete $$$s_2$$$ and $$$s_3$$$: $$$1\textbf{01}1001 \rightarrow 11001$$$;
3. delete $$$s_4$$$ and $$$s_5$$$: $$$101\textbf{10}01 \rightarrow 10101$$$;
4. delete $$$s_6$$$ and $$$s_7$$$: $$$10110\textbf{01} \rightarrow 10110$$$.

If a player can't make any move, they lose. Both players play optimally. You have to determine if Alice can win.

## Input Format
First line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Only line of each test case contains one string $$$s$$$ ($$$1 \le |s| \le 100$$$), consisting of only characters 0 and 1.

## Output Format
For each test case print answer in the single line.

If Alice can win print DA (YES in Russian) in any register. Otherwise print NET (NO in Russian) in any register.

## Examples
```input
3
01
1111
0011
```
```output
DA
NET
NET
```

## Note
In the first test case after Alice's move string $$$s$$$ become empty and Bob can not make any move.

In the second test case Alice can not make any move initially.

In the third test case after Alice's move string $$$s$$$ turn into $$$01$$$. Then, after Bob's move string $$$s$$$ become empty and Alice can not make any move.

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
You are given an array $$$a$$$ consisting of $$$n$$$ integers. Indices of the array start from zero (i. e. the first element is $$$a_0$$$, the second one is $$$a_1$$$, and so on).

You can reverse at most one subarray (continuous subsegment) of this array. Recall that the subarray of $$$a$$$ with borders $$$l$$$ and $$$r$$$ is $$$a[l; r] = a_l, a_{l + 1}, \dots, a_{r}$$$.

Your task is to reverse such a subarray that the sum of elements on even positions of the resulting array is maximized (i. e. the sum of elements $$$a_0, a_2, \dots, a_{2k}$$$ for integer $$$k = \lfloor\frac{n-1}{2}\rfloor$$$ should be maximum possible).

You have to answer $$$t$$$ independent test cases.

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

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$a$$$. The second line of the test case contains $$$n$$$ integers $$$a_0, a_1, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

## Output Format
For each test case, print the answer on the separate line — the maximum possible sum of elements on even positions after reversing at most one subarray (continuous subsegment) of $$$a$$$.

## Examples
```input
4
8
1 7 3 4 7 6 2 9
5
1 2 1 2 1
10
7 8 4 5 7 6 8 9 7 3
4
3 1 2 1
```
```output
26
5
37
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
Let $$$f(x)$$$ be the sum of digits of a decimal number $$$x$$$.

Find the smallest non-negative integer $$$x$$$ such that $$$f(x) + f(x + 1) + \dots + f(x + k) = n$$$.

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

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 150$$$, $$$0 \le k \le 9$$$).

## Output Format
For each test case, print one integer without leading zeroes. If there is no such $$$x$$$ that $$$f(x) + f(x + 1) + \dots + f(x + k) = n$$$, print $$$-1$$$; otherwise, print the minimum $$$x$$$ meeting that constraint.

## Examples
```input
7
1 0
1 1
42 7
13 7
99 1
99 0
99 2
```
```output
1
0
4
-1
599998
99999999999
7997
```

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

# Problem
You are given a chessboard consisting of $$$n$$$ rows and $$$n$$$ columns. Rows are numbered from bottom to top from $$$1$$$ to $$$n$$$. Columns are numbered from left to right from $$$1$$$ to $$$n$$$. The cell at the intersection of the $$$x$$$-th column and the $$$y$$$-th row is denoted as $$$(x, y)$$$. Furthermore, the $$$k$$$-th column is a special column.

Initially, the board is empty. There are $$$m$$$ changes to the board. During the $$$i$$$-th change one pawn is added or removed from the board. The current board is good if we can move all pawns to the special column by the followings rules:

- Pawn in the cell $$$(x, y)$$$ can be moved to the cell $$$(x, y + 1)$$$, $$$(x - 1, y + 1)$$$ or $$$(x + 1, y + 1)$$$;
- You can make as many such moves as you like;
- Pawns can not be moved outside the chessboard;
- Each cell can not contain more than one pawn.

The current board may not always be good. To fix it, you can add new rows to the board. New rows are added at the top, i. e. they will have numbers $$$n+1, n+2, n+3, \dots$$$.

After each of $$$m$$$ changes, print one integer — the minimum number of rows which you have to add to make the board good.

## Input Format
The first line contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5; 1 \le k \le n$$$) — the size of the board, the index of the special column and the number of changes respectively.

Then $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$) — the index of the column and the index of the row respectively. If there is no pawn in the cell $$$(x, y)$$$, then you add a pawn to this cell, otherwise — you remove the pawn from this cell.

## Output Format
After each change print one integer — the minimum number of rows which you have to add to make the board good.

## Examples
```input
5 3 5
4 4
3 5
2 4
3 4
3 5
```
```output
0
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: 512.0 MB

# Problem
You are given two arrays $$$a$$$ and $$$b$$$, each consisting of $$$n$$$ positive integers, and an integer $$$x$$$. Please determine if one can rearrange the elements of $$$b$$$ so that $$$a_i + b_i \leq x$$$ holds for each $$$i$$$ ($$$1 \le i \le n$$$).

## Input Format
The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. $$$t$$$ blocks follow, each describing an individual test case.

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 50$$$; $$$1 \leq x \leq 1000$$$) — the length of arrays $$$a$$$ and $$$b$$$, and the parameter $$$x$$$, described in the problem statement.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_1 \le a_2 \le \dots \le a_n \leq x$$$) — the elements of array $$$a$$$ in non-descending order.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_1 \le b_2 \le \dots \le b_n \leq x$$$) — the elements of array $$$b$$$ in non-descending order.

Test cases are separated by a blank line.

## Output Format
For each test case print Yes if one can rearrange the corresponding array $$$b$$$ so that $$$a_i + b_i \leq x$$$ holds for each $$$i$$$ ($$$1 \le i \le n$$$) or No otherwise.

Each character can be printed in any case.

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

2 6
1 4
2 5

4 4
1 2 3 4
1 2 3 4

1 5
5
5
```
```output
Yes
Yes
No
No
```

## Note
In the first test case, one can rearrange $$$b$$$ so it'll look like $$$[1, 2, 1]$$$. In this case, $$$1 + 1 \leq 4$$$; $$$2 + 2 \leq 4$$$; $$$3 + 1 \leq 4$$$.

In the second test case, one can set $$$b$$$ to $$$[5, 2]$$$, then $$$1 + 5 \leq 6$$$; $$$4 + 2 \leq 6$$$.

In the third test case, no matter how one shuffles array $$$b$$$, $$$a_4 + b_4 = 4 + b_4 > 4$$$.

In the fourth test case, there is only one rearrangement of array $$$b$$$ and it doesn't satisfy the condition since $$$5 + 5 > 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
A robot is standing at the origin of the infinite two-dimensional plane. Each second the robot moves exactly $$$1$$$ meter in one of the four cardinal directions: north, south, west, and east. For the first step the robot can choose any of the four directions, but then at the end of every second it has to turn 90 degrees left or right with respect to the direction it just moved in. For example, if the robot has just moved north or south, the next step it takes has to be either west or east, and vice versa.

The robot makes exactly $$$n$$$ steps from its starting position according to the rules above. How many different points can the robot arrive to at the end? The final orientation of the robot can be ignored.

## Input Format
The only line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the number of steps the robot makes.

## Output Format
Print a single integer — the number of different possible locations after exactly $$$n$$$ steps.

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

## Note
In the first sample case, the robot will end up 1 meter north, south, west, or east depending on its initial direction.

In the second sample case, the robot will always end up $$$\sqrt{2}$$$ meters north-west, north-east, south-west, or south-east.

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
Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya loves tickets very much. As we know, each ticket has a number that is a positive integer. Its length equals n (n is always even). Petya calls a ticket lucky if the ticket's number is a lucky number and the sum of digits in the first half (the sum of the first n / 2 digits) equals the sum of digits in the second half (the sum of the last n / 2 digits). Check if the given ticket is lucky.

## Input Format
The first line contains an even integer n (2 ≤ n ≤ 50) — the length of the ticket number that needs to be checked. The second line contains an integer whose length equals exactly n — the ticket number. The number may contain leading zeros.

## Output Format
On the first line print "YES" if the given ticket number is lucky. Otherwise, print "NO" (without the quotes).

## Examples
```input
2
47
```
```output
NO
```
-----
```input
4
4738
```
```output
NO
```
-----
```input
4
4774
```
```output
YES
```

## Note
In the first sample the sum of digits in the first half does not equal the sum of digits in the second half (4 ≠ 7).

In the second sample the ticket number is not the lucky number.

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
Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya calls a mask of a positive integer n the number that is obtained after successive writing of all lucky digits of number n from the left to the right. For example, the mask of number 72174994 is number 7744, the mask of 7 is 7, the mask of 9999047 is 47. Obviously, mask of any number is always a lucky number.

Petya has two numbers — an arbitrary integer a and a lucky number b. Help him find the minimum number c (c > a) such that the mask of number c equals b.

## Input Format
The only line contains two integers a and b (1 ≤ a, b ≤ 105). It is guaranteed that number b is lucky.

## Output Format
In the only line print a single number — the number c that is sought by Petya.

## Examples
```input
1 7
```
```output
7
```
-----
```input
100 47
```
```output
147
```

Now solve the problem and return the code.