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

# Problem
There are $$$n$$$ piles of stones, where the $$$i$$$-th pile has $$$a_i$$$ stones. Two people play a game, where they take alternating turns removing stones.

In a move, a player may remove a positive number of stones from the first non-empty pile (the pile with the minimal index, that has at least one stone). The first player who cannot make a move (because all piles are empty) loses the game. If both players play optimally, determine the winner of the game.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1\le t\le 1000$$$)  — the number of test cases. Next $$$2t$$$ lines contain descriptions of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 10^5$$$)  — the number of piles.

The second line of each test case contains $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$)  — $$$a_i$$$ is equal to the number of stones in the $$$i$$$-th pile.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$10^5$$$.

## Output Format
For each test case, if the player who makes the first move will win, output "First". Otherwise, output "Second".

## Examples
```input
7
3
2 5 4
8
1 1 1 1 1 1 1 1
6
1 2 3 4 5 6
6
1 1 2 1 2 2
1
1000000000
5
1 2 2 1 1
3
1 1 1
```
```output
First
Second
Second
First
First
Second
First
```

## Note
In the first test case, the first player will win the game. His winning strategy is:

1. The first player should take the stones from the first pile. He will take $$$1$$$ stone. The numbers of stones in piles will be $$$[1, 5, 4]$$$.
2. The second player should take the stones from the first pile. He will take $$$1$$$ stone because he can't take any other number of stones. The numbers of stones in piles will be $$$[0, 5, 4]$$$.
3. The first player should take the stones from the second pile because the first pile is empty. He will take $$$4$$$ stones. The numbers of stones in piles will be $$$[0, 1, 4]$$$.
4. The second player should take the stones from the second pile because the first pile is empty. He will take $$$1$$$ stone because he can't take any other number of stones. The numbers of stones in piles will be $$$[0, 0, 4]$$$.
5. The first player should take the stones from the third pile because the first and second piles are empty. He will take $$$4$$$ stones. The numbers of stones in piles will be $$$[0, 0, 0]$$$.
6. The second player will lose the game because all piles will be empty.

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
You are playing a very popular game called Cubecraft. Initially, you have one stick and want to craft $$$k$$$ torches. One torch can be crafted using one stick and one coal.

Hopefully, you've met a very handsome wandering trader who has two trade offers:

- exchange $$$1$$$ stick for $$$x$$$ sticks (you lose $$$1$$$ stick and gain $$$x$$$ sticks).
- exchange $$$y$$$ sticks for $$$1$$$ coal (you lose $$$y$$$ sticks and gain $$$1$$$ coal).

During one trade, you can use only one of these two trade offers. You can use each trade offer any number of times you want to, in any order.

Your task is to find the minimum number of trades you need to craft at least $$$k$$$ torches. The answer always exists under the given constraints.

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 only line of the test case contains three integers $$$x$$$, $$$y$$$ and $$$k$$$ ($$$2 \le x \le 10^9$$$; $$$1 \le y, k \le 10^9$$$) — the number of sticks you can buy with one stick, the number of sticks required to buy one coal and the number of torches you need, respectively.

## Output Format
For each test case, print the answer: the minimum number of trades you need to craft at least $$$k$$$ torches. The answer always exists under the given constraints.

## Examples
```input
5
2 1 5
42 13 24
12 11 12
1000000000 1000000000 1000000000
2 1000000000 1000000000
```
```output
14
33
25
2000000003
1000000001999999999
```

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
You and your friend are playing the game Mortal Kombat XI. You are trying to pass a challenge tower. There are $$$n$$$ bosses in this tower, numbered from $$$1$$$ to $$$n$$$. The type of the $$$i$$$-th boss is $$$a_i$$$. If the $$$i$$$-th boss is easy then its type is $$$a_i = 0$$$, otherwise this boss is hard and its type is $$$a_i = 1$$$.

During one session, either you or your friend can kill one or two bosses (neither you nor your friend can skip the session, so the minimum number of bosses killed during one session is at least one). After your friend session, your session begins, then again your friend session begins, your session begins, and so on. The first session is your friend's session.

Your friend needs to get good because he can't actually kill hard bosses. To kill them, he uses skip points. One skip point can be used to kill one hard boss.

Your task is to find the minimum number of skip points your friend needs to use so you and your friend kill all $$$n$$$ bosses in the given order.

For example: suppose $$$n = 8$$$, $$$a = [1, 0, 1, 1, 0, 1, 1, 1]$$$. Then the best course of action is the following:

- your friend kills two first bosses, using one skip point for the first boss;
- you kill the third and the fourth bosses;
- your friend kills the fifth boss;
- you kill the sixth and the seventh bosses;
- your friend kills the last boss, using one skip point, so the tower is completed using two skip points.

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 number of bosses. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$), where $$$a_i$$$ is the type of the $$$i$$$-th boss.

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: the minimum number of skip points your friend needs to use so you and your friend kill all $$$n$$$ bosses in the given order.

## Examples
```input
6
8
1 0 1 1 0 1 1 1
5
1 1 1 1 0
7
1 1 1 1 0 0 1
6
1 1 1 1 1 1
1
1
1
0
```
```output
2
2
2
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 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
You are given four integers $$$n$$$, $$$m$$$, $$$l$$$ and $$$r$$$.

Let's name a tuple $$$(x_1, y_1, x_2, y_2)$$$ as good if:

1. $$$1 \le x_1 < x_2 \le n$$$;
2. $$$1 \le y_2 < y_1 \le m$$$;
3. $$$x_1 \cdot y_1 = x_2 \cdot y_2$$$;
4. $$$l \le x_1 \cdot y_1 \le r$$$.

Find any good tuple for each $$$x_1$$$ from $$$1$$$ to $$$n$$$ inclusive.

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

The second line contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le nm$$$).

## Output Format
For each $$$x_1$$$ from $$$1$$$ to $$$n$$$ inclusive:

- if there are no such four integers, print $$$-1$$$;
- otherwise, print four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ and $$$y_2$$$. If there are multiple answers, print any of them.

## Examples
```input
8 20
91 100
```
```output
-1
-1
-1
-1
-1
6 16 8 12
-1
-1
```
-----
```input
4 5
1 10
```
```output
1 2 2 1
2 3 3 2
-1
-1
```
-----
```input
5 12
16 60
```
```output
-1
2 9 3 6
3 8 4 6
4 5 5 4
-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: 5.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ integers. We denote the subarray $$$a[l..r]$$$ as the array $$$[a_l, a_{l + 1}, \dots, a_r]$$$ ($$$1 \le l \le r \le n$$$).

A subarray is considered good if every integer that occurs in this subarray occurs there exactly thrice. For example, the array $$$[1, 2, 2, 2, 1, 1, 2, 2, 2]$$$ has three good subarrays:

- $$$a[1..6] = [1, 2, 2, 2, 1, 1]$$$;
- $$$a[2..4] = [2, 2, 2]$$$;
- $$$a[7..9] = [2, 2, 2]$$$.

Calculate the number of good subarrays of the given array $$$a$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le n$$$).

## Output Format
Print one integer — the number of good subarrays of the array $$$a$$$.

## Examples
```input
9
1 2 2 2 1 1 2 2 2
```
```output
3
```
-----
```input
10
1 2 3 4 1 2 3 1 2 3
```
```output
0
```
-----
```input
12
1 2 3 4 3 4 2 1 3 4 2 1
```
```output
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You have a blackboard and initially only an odd number $$$x$$$ is written on it. Your goal is to write the number $$$1$$$ on the blackboard.

You may write new numbers on the blackboard with the following two operations.

- You may take two numbers (not necessarily distinct) already on the blackboard and write their sum on the blackboard. The two numbers you have chosen remain on the blackboard.
- You may take two numbers (not necessarily distinct) already on the blackboard and write their bitwise XOR on the blackboard. The two numbers you have chosen remain on the blackboard.

## Input Format
The single line of the input contains the odd integer $$$x$$$ ($$$3 \le x \le 999,999$$$).

## Output Format
Print on the first line the number $$$q$$$ of operations you perform. Then $$$q$$$ lines should follow, each describing one operation.

- The "sum" operation is described by the line "$$$a$$$ + $$$b$$$", where $$$a, b$$$ must be integers already present on the blackboard.
- The "xor" operation is described by the line "$$$a$$$ ^ $$$b$$$", where $$$a, b$$$ must be integers already present on the blackboard.

You can perform at most $$$100,000$$$ operations (that is, $$$q\le 100,000$$$) and all numbers written on the blackboard must be in the range $$$[0, 5\cdot10^{18}]$$$. It can be proven that under such restrictions the required sequence of operations exists. You can output any suitable sequence of operations.

## Examples
```input
3
```
```output
5
3 + 3
3 ^ 6
3 + 5
3 + 6
8 ^ 9
```
-----
```input
123
```
```output
10
123 + 123
123 ^ 246
141 + 123
246 + 123
264 ^ 369
121 + 246
367 ^ 369
30 + 30
60 + 60
120 ^ 121
```

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