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
Simon and Antisimon play a game. Initially each player receives one fixed positive integer that doesn't change throughout the game. Simon receives number a and Antisimon receives number b. They also have a heap of n stones. The players take turns to make a move and Simon starts. During a move a player should take from the heap the number of stones equal to the greatest common divisor of the fixed number he has received and the number of stones left in the heap. A player loses when he cannot take the required number of stones (i. e. the heap has strictly less stones left than one needs to take).

Your task is to determine by the given a, b and n who wins the game.

## Input Format
The only string contains space-separated integers a, b and n (1 ≤ a, b, n ≤ 100) — the fixed numbers Simon and Antisimon have received correspondingly and the initial number of stones in the pile.

## Output Format
If Simon wins, print "0" (without the quotes), otherwise print "1" (without the quotes).

## Examples
```input
3 5 9
```
```output
0
```
-----
```input
1 1 100
```
```output
1
```

## Note
The greatest common divisor of two non-negative integers a and b is such maximum positive integer k, that a is divisible by k without remainder and similarly, b is divisible by k without remainder. Let gcd(a, b) represent the operation of calculating the greatest common divisor of numbers a and b. Specifically, gcd(x, 0) = gcd(0, x) = x.

In the first sample the game will go like that:

- Simon should take gcd(3, 9) = 3 stones from the heap. After his move the heap has 6 stones left.
- Antisimon should take gcd(5, 6) = 1 stone from the heap. After his move the heap has 5 stones left.
- Simon should take gcd(3, 5) = 1 stone from the heap. After his move the heap has 4 stones left.
- Antisimon should take gcd(5, 4) = 1 stone from the heap. After his move the heap has 3 stones left.
- Simon should take gcd(3, 3) = 3 stones from the heap. After his move the heap has 0 stones left.
- Antisimon should take gcd(5, 0) = 5 stones from the heap. As 0 < 5, it is impossible and Antisimon loses.

In the second sample each player during each move takes one stone from the heap. As n is even, Antisimon takes the last stone and Simon can't make a move after that.

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 $$$n$$$ students standing in a circle in some order. The index of the $$$i$$$-th student is $$$p_i$$$. It is guaranteed that all indices of students are distinct integers from $$$1$$$ to $$$n$$$ (i. e. they form a permutation).

Students want to start a round dance. A clockwise round dance can be started if the student $$$2$$$ comes right after the student $$$1$$$ in clockwise order (there are no students between them), the student $$$3$$$ comes right after the student $$$2$$$ in clockwise order, and so on, and the student $$$n$$$ comes right after the student $$$n - 1$$$ in clockwise order. A counterclockwise round dance is almost the same thing — the only difference is that the student $$$i$$$ should be right after the student $$$i - 1$$$ in counterclockwise order (this condition should be met for every $$$i$$$ from $$$2$$$ to $$$n$$$).

For example, if the indices of students listed in clockwise order are $$$[2, 3, 4, 5, 1]$$$, then they can start a clockwise round dance. If the students have indices $$$[3, 2, 1, 4]$$$ in clockwise order, then they can start a counterclockwise round dance.

Your task is to determine whether it is possible to start a round dance. Note that the students cannot change their positions before starting the dance; they cannot swap or leave the circle, and no other student can enter the circle.

You have to answer $$$q$$$ independent queries.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 200$$$) — the number of queries. Then $$$q$$$ queries follow.

The first line of the query contains one integer $$$n$$$ ($$$1 \le n \le 200$$$) — the number of students.

The second line of the query contains a permutation of indices $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is the index of the $$$i$$$-th student (in clockwise order). It is guaranteed that all $$$p_i$$$ are distinct integers from $$$1$$$ to $$$n$$$ (i. e. they form a permutation).

## Output Format
For each query, print the answer on it. If a round dance can be started with the given order of students, print "YES". Otherwise print "NO".

## Examples
```input
5
4
1 2 3 4
3
1 3 2
5
1 2 3 5 4
1
1
5
3 2 1 5 4
```
```output
YES
YES
NO
YES
YES
```

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 $$$4n$$$ sticks, the length of the $$$i$$$-th stick is $$$a_i$$$.

You have to create $$$n$$$ rectangles, each rectangle will consist of exactly $$$4$$$ sticks from the given set. The rectangle consists of four sides, opposite sides should have equal length and all angles in it should be right. Note that each stick can be used in only one rectangle. Each stick should be used as a side, you cannot break the stick or use it not to the full length.

You want to all rectangles to have equal area. The area of the rectangle with sides $$$a$$$ and $$$b$$$ is $$$a \cdot b$$$.

Your task is to say if it is possible to create exactly $$$n$$$ rectangles of equal area or not.

You have to answer $$$q$$$ independent queries.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 500$$$) — the number of queries. Then $$$q$$$ queries follow.

The first line of the query contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of rectangles.

The second line of the query contains $$$4n$$$ integers $$$a_1, a_2, \dots, a_{4n}$$$ ($$$1 \le a_i \le 10^4$$$), where $$$a_i$$$ is the length of the $$$i$$$-th stick.

## Output Format
For each query print the answer to it. If it is impossible to create exactly $$$n$$$ rectangles of equal area using given sticks, print "NO". Otherwise print "YES".

## Examples
```input
5
1
1 1 10 10
2
10 5 2 10 1 1 2 5
2
10 5 1 10 5 1 1 1
2
1 1 1 1 1 1 1 1
1
10000 10000 10000 10000
```
```output
YES
YES
NO
YES
YES
```

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 an array $$$a$$$ consisting of $$$n$$$ integers.

Your task is to say the number of such positive integers $$$x$$$ such that $$$x$$$ divides each number from the array. In other words, you have to find the number of common divisors of all elements in the array.

For example, if the array $$$a$$$ will be $$$[2, 4, 6, 2, 10]$$$, then $$$1$$$ and $$$2$$$ divide each number from the array (so the answer for this test is $$$2$$$).

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — the number of elements in $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

## Output Format
Print one integer — the number of such positive integers $$$x$$$ such that $$$x$$$ divides each number from the given array (in other words, the answer is the number of common divisors of all elements in the array).

## Examples
```input
5
1 2 3 4 5
```
```output
1
```
-----
```input
6
6 90 12 18 30 18
```
```output
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 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 only difference between easy and hard versions is the length of the string.

You are given a string $$$s$$$ and a string $$$t$$$, both consisting only of lowercase Latin letters. It is guaranteed that $$$t$$$ can be obtained from $$$s$$$ by removing some (possibly, zero) number of characters (not necessary contiguous) from $$$s$$$ without changing order of remaining characters (in other words, it is guaranteed that $$$t$$$ is a subsequence of $$$s$$$).

For example, the strings "test", "tst", "tt", "et" and "" are subsequences of the string "test". But the strings "tset", "se", "contest" are not subsequences of the string "test".

You want to remove some substring (contiguous subsequence) from $$$s$$$ of maximum possible length such that after removing this substring $$$t$$$ will remain a subsequence of $$$s$$$.

If you want to remove the substring $$$s[l;r]$$$ then the string $$$s$$$ will be transformed to $$$s_1 s_2 \dots s_{l-1} s_{r+1} s_{r+2} \dots s_{|s|-1} s_{|s|}$$$ (where $$$|s|$$$ is the length of $$$s$$$).

Your task is to find the maximum possible length of the substring you can remove so that $$$t$$$ is still a subsequence of $$$s$$$.

## Input Format
The first line of the input contains one string $$$s$$$ consisting of at least $$$1$$$ and at most $$$200$$$ lowercase Latin letters.

The second line of the input contains one string $$$t$$$ consisting of at least $$$1$$$ and at most $$$200$$$ lowercase Latin letters.

It is guaranteed that $$$t$$$ is a subsequence of $$$s$$$.

## Output Format
Print one integer — the maximum possible length of the substring you can remove so that $$$t$$$ is still a subsequence of $$$s$$$.

## Examples
```input
bbaba
bb
```
```output
3
```
-----
```input
baaba
ab
```
```output
2
```
-----
```input
abcde
abcde
```
```output
0
```
-----
```input
asdfasdf
fasd
```
```output
3
```

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
The only difference between easy and hard versions is the length of the string.

You are given a string $$$s$$$ and a string $$$t$$$, both consisting only of lowercase Latin letters. It is guaranteed that $$$t$$$ can be obtained from $$$s$$$ by removing some (possibly, zero) number of characters (not necessary contiguous) from $$$s$$$ without changing order of remaining characters (in other words, it is guaranteed that $$$t$$$ is a subsequence of $$$s$$$).

For example, the strings "test", "tst", "tt", "et" and "" are subsequences of the string "test". But the strings "tset", "se", "contest" are not subsequences of the string "test".

You want to remove some substring (contiguous subsequence) from $$$s$$$ of maximum possible length such that after removing this substring $$$t$$$ will remain a subsequence of $$$s$$$.

If you want to remove the substring $$$s[l;r]$$$ then the string $$$s$$$ will be transformed to $$$s_1 s_2 \dots s_{l-1} s_{r+1} s_{r+2} \dots s_{|s|-1} s_{|s|}$$$ (where $$$|s|$$$ is the length of $$$s$$$).

Your task is to find the maximum possible length of the substring you can remove so that $$$t$$$ is still a subsequence of $$$s$$$.

## Input Format
The first line of the input contains one string $$$s$$$ consisting of at least $$$1$$$ and at most $$$2 \cdot 10^5$$$ lowercase Latin letters.

The second line of the input contains one string $$$t$$$ consisting of at least $$$1$$$ and at most $$$2 \cdot 10^5$$$ lowercase Latin letters.

It is guaranteed that $$$t$$$ is a subsequence of $$$s$$$.

## Output Format
Print one integer — the maximum possible length of the substring you can remove so that $$$t$$$ is still a subsequence of $$$s$$$.

## Examples
```input
bbaba
bb
```
```output
3
```
-----
```input
baaba
ab
```
```output
2
```
-----
```input
abcde
abcde
```
```output
0
```
-----
```input
asdfasdf
fasd
```
```output
3
```

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
The only difference between easy and hard versions is that you should complete all the projects in easy version but this is not necessary in hard version.

Polycarp is a very famous freelancer. His current rating is $$$r$$$ units.

Some very rich customers asked him to complete some projects for their companies. To complete the $$$i$$$-th project, Polycarp needs to have at least $$$a_i$$$ units of rating; after he completes this project, his rating will change by $$$b_i$$$ (his rating will increase or decrease by $$$b_i$$$) ($$$b_i$$$ can be positive or negative). Polycarp's rating should not fall below zero because then people won't trust such a low rated freelancer.

Is it possible to complete all the projects? Formally, write a program to check if such an order of the projects exists, that Polycarp has enough rating before starting each project, and he has non-negative rating after completing each project.

In other words, you have to check that there exists such an order of projects in which Polycarp will complete them, so he has enough rating before starting each project, and has non-negative rating after completing each project.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$r$$$ ($$$1 \le n \le 100, 1 \le r \le 30000$$$) — the number of projects and the initial rating of Polycarp, respectively.

The next $$$n$$$ lines contain projects, one per line. The $$$i$$$-th project is represented as a pair of integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le 30000$$$, $$$-300 \le b_i \le 300$$$) — the rating required to complete the $$$i$$$-th project and the rating change after the project completion.

## Output Format
Print "YES" or "NO".

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

## Note
In the first example, the possible order is: $$$1, 2, 3$$$.

In the second example, the possible order is: $$$2, 3, 1$$$.

In the third example, the possible order is: $$$3, 1, 4, 2$$$.

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
The only difference between easy and hard versions is that you should complete all the projects in easy version but this is not necessary in hard version.

Polycarp is a very famous freelancer. His current rating is $$$r$$$ units.

Some very rich customers asked him to complete some projects for their companies. To complete the $$$i$$$-th project, Polycarp needs to have at least $$$a_i$$$ units of rating; after he completes this project, his rating will change by $$$b_i$$$ (his rating will increase or decrease by $$$b_i$$$) ($$$b_i$$$ can be positive or negative). Polycarp's rating should not fall below zero because then people won't trust such a low rated freelancer.

Polycarp can choose the order in which he completes projects. Furthermore, he can even skip some projects altogether.

To gain more experience (and money, of course) Polycarp wants to choose the subset of projects having maximum possible size and the order in which he will complete them, so he has enough rating before starting each project, and has non-negative rating after completing each project.

Your task is to calculate the maximum possible size of such subset of projects.

## Input Format
The first line of the input contains two integers $$$n$$$ and $$$r$$$ ($$$1 \le n \le 100, 1 \le r \le 30000$$$) — the number of projects and the initial rating of Polycarp, respectively.

The next $$$n$$$ lines contain projects, one per line. The $$$i$$$-th project is represented as a pair of integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le 30000$$$, $$$-300 \le b_i \le 300$$$) — the rating required to complete the $$$i$$$-th project and the rating change after the project completion.

## Output Format
Print one integer — the size of the maximum possible subset (possibly, empty) of projects Polycarp can choose.

## Examples
```input
3 4
4 6
10 -2
8 -1
```
```output
3
```
-----
```input
5 20
45 -6
34 -15
10 34
1 27
40 -45
```
```output
5
```
-----
```input
3 2
300 -300
1 299
1 123
```
```output
3
```

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
There are two types of burgers in your restaurant — hamburgers and chicken burgers! To assemble a hamburger you need two buns and a beef patty. To assemble a chicken burger you need two buns and a chicken cutlet.

You have $$$b$$$ buns, $$$p$$$ beef patties and $$$f$$$ chicken cutlets in your restaurant. You can sell one hamburger for $$$h$$$ dollars and one chicken burger for $$$c$$$ dollars. Calculate the maximum profit you can achieve.

You have to answer $$$t$$$ independent queries.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) – the number of queries.

The first line of each query contains three integers $$$b$$$, $$$p$$$ and $$$f$$$ ($$$1 \le b, ~p, ~f \le 100$$$) — the number of buns, beef patties and chicken cutlets in your restaurant.

The second line of each query contains two integers $$$h$$$ and $$$c$$$ ($$$1 \le h, ~c \le 100$$$) — the hamburger and chicken burger prices in your restaurant.

## Output Format
For each query print one integer — the maximum profit you can achieve.

## Examples
```input
3
15 2 3
5 10
7 5 2
10 12
1 100 100
100 100
```
```output
40
34
0
```

## Note
In first query you have to sell two hamburgers and three chicken burgers. Your income is $$$2 \cdot 5 + 3 \cdot 10 = 40$$$.

In second query you have to ell one hamburgers and two chicken burgers. Your income is $$$1 \cdot 10 + 2 \cdot 12 = 34$$$.

In third query you can not create any type of burgers because because you have only one bun. So your income is zero.

Now solve the problem and return the code.