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
A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity.

Your favorite store sells lemonade in bottles of n different volumes at different costs. A single bottle of type i has volume 2i - 1 liters and costs ci roubles. The number of bottles of each type in the store can be considered infinite.

You want to buy at least L liters of lemonade. How many roubles do you have to spend?

## Input Format
The first line contains two integers n and L (1 ≤ n ≤ 30; 1 ≤ L ≤ 109) — the number of types of bottles in the store and the required amount of lemonade in liters, respectively.

The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 109) — the costs of bottles of different types.

## Output Format
Output a single integer — the smallest number of roubles you have to pay in order to buy at least L liters of lemonade.

## Examples
```input
4 12
20 30 70 90
```
```output
150
```
-----
```input
4 3
10000 1000 100 10
```
```output
10
```
-----
```input
4 3
10 100 1000 10000
```
```output
30
```
-----
```input
5 787787787
123456789 234567890 345678901 456789012 987654321
```
```output
44981600785557577
```

## Note
In the first example you should buy one 8-liter bottle for 90 roubles and two 2-liter bottles for 30 roubles each. In total you'll get 12 liters of lemonade for just 150 roubles.

In the second example, even though you need only 3 liters, it's cheaper to buy a single 8-liter bottle for 10 roubles.

In the third example it's best to buy three 1-liter bottles for 10 roubles each, getting three liters for 30 roubles.

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 n positive integers a1, a2, ..., an.

For every ai you need to find a positive integer ki such that the decimal notation of 2ki contains the decimal notation of ai as a substring among its last min(100, length(2ki)) digits. Here length(m) is the length of the decimal notation of m.

Note that you don't have to minimize ki. The decimal notations in this problem do not contain leading zeros.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 2 000) — the number of integers ai.

Each of the next n lines contains a positive integer ai (1 ≤ ai < 1011).

## Output Format
Print n lines. The i-th of them should contain a positive integer ki such that the last min(100, length(2ki)) digits of 2ki contain the decimal notation of ai as a substring. Integers ki must satisfy 1 ≤ ki ≤ 1050.

It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.

## Examples
```input
2
8
2
```
```output
3
1
```
-----
```input
2
3
4857
```
```output
5
20
```

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

# Problem
You generate real numbers s1, s2, ..., sn as follows:

- s0 = 0;
- si = si - 1 + ti, where ti is a real number chosen independently uniformly at random between 0 and 1, inclusive.

You are given real numbers x1, x2, ..., xn. You are interested in the probability that si ≤ xi is true for all i simultaneously.

It can be shown that this can be represented as $$\frac{p}{q}$$, where P and Q are coprime integers, and $$Q \not\equiv 0 \pmod{998244353}$$. Print the value of P·Q - 1 modulo 998244353.

## Input Format
The first line contains integer n (1 ≤ n ≤ 30).

The next n lines contain real numbers x1, x2, ..., xn, given with at most six digits after the decimal point (0 < xi ≤ n).

## Output Format
Print a single integer, the answer to the problem.

## Examples
```input
4
1.00
2
3.000000
4.0
```
```output
1
```
-----
```input
1
0.50216
```
```output
342677322
```
-----
```input
2
0.5
1.0
```
```output
623902721
```
-----
```input
6
0.77
1.234567
2.1
1.890
2.9999
3.77
```
```output
859831967
```

## Note
In the first example, the sought probability is 1 since the sum of i real numbers which don't exceed 1 doesn't exceed i.

In the second example, the probability is x1 itself.

In the third example, the sought probability is 3 / 8.

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
Imp likes his plush toy a lot.

Recently, he found a machine that can clone plush toys. Imp knows that if he applies the machine to an original toy, he additionally gets one more original toy and one copy, and if he applies the machine to a copied toy, he gets two additional copies.

Initially, Imp has only one original toy. He wants to know if it is possible to use machine to get exactly x copied toys and y original toys? He can't throw toys away, and he can't apply the machine to a copy if he doesn't currently have any copies.

## Input Format
The only line contains two integers x and y (0 ≤ x, y ≤ 109) — the number of copies and the number of original toys Imp wants to get (including the initial one).

## Output Format
Print "Yes", if the desired configuration is possible, and "No" otherwise.

You can print each letter in arbitrary case (upper or lower).

## Examples
```input
6 3
```
```output
Yes
```
-----
```input
4 2
```
```output
No
```
-----
```input
1000 1001
```
```output
Yes
```

## Note
In the first example, Imp has to apply the machine twice to original toys and then twice to copies.

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
Imp is in a magic forest, where xorangles grow (wut?)

A xorangle of order n is such a non-degenerate triangle, that lengths of its sides are integers not exceeding n, and the xor-sum of the lengths is equal to zero. Imp has to count the number of distinct xorangles of order n to get out of the forest.

Formally, for a given integer n you have to find the number of such triples (a, b, c), that:

- 1 ≤ a ≤ b ≤ c ≤ n;
- $$a \oplus b \oplus c = 0$$, where $$x \oplus y$$ denotes the bitwise xor of integers x and y.
- (a, b, c) form a non-degenerate (with strictly positive area) triangle.

## Input Format
The only line contains a single integer n (1 ≤ n ≤ 2500).

## Output Format
Print the number of xorangles of order n.

## Examples
```input
6
```
```output
1
```
-----
```input
10
```
```output
2
```

## Note
The only xorangle in the first sample is (3, 5, 6).

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
Imp is watching a documentary about cave painting.

Some numbers, carved in chaotic order, immediately attracted his attention. Imp rapidly proposed a guess that they are the remainders of division of a number n by all integers i from 1 to k. Unfortunately, there are too many integers to analyze for Imp.

Imp wants you to check whether all these remainders are distinct. Formally, he wants to check, if all $$n \bmod i$$, 1 ≤ i ≤ k, are distinct, i. e. there is no such pair (i, j) that:

- 1 ≤ i < j ≤ k,
- $$n \bmod i = n \bmod j$$, where $$x \bmod y$$ is the remainder of division x by y.

## Input Format
The only line contains two integers n, k (1 ≤ n, k ≤ 1018).

## Output Format
Print "Yes", if all the remainders are distinct, and "No" otherwise.

You can print each letter in arbitrary case (lower or upper).

## Examples
```input
4 4
```
```output
No
```
-----
```input
5 3
```
```output
Yes
```

## Note
In the first sample remainders modulo 1 and 4 coincide.

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
Apart from plush toys, Imp is a huge fan of little yellow birds!

To summon birds, Imp needs strong magic. There are n trees in a row on an alley in a park, there is a nest on each of the trees. In the i-th nest there are ci birds; to summon one bird from this nest Imp needs to stay under this tree and it costs him costi points of mana. However, for each bird summoned, Imp increases his mana capacity by B points. Imp summons birds one by one, he can summon any number from 0 to ci birds from the i-th nest.

Initially Imp stands under the first tree and has W points of mana, and his mana capacity equals W as well. He can only go forward, and each time he moves from a tree to the next one, he restores X points of mana (but it can't exceed his current mana capacity). Moving only forward, what is the maximum number of birds Imp can summon?

## Input Format
The first line contains four integers n, W, B, X (1 ≤ n ≤ 103, 0 ≤ W, B, X ≤ 109) — the number of trees, the initial points of mana, the number of points the mana capacity increases after a bird is summoned, and the number of points restored when Imp moves from a tree to the next one.

The second line contains n integers c1, c2, ..., cn (0 ≤ ci ≤ 104) — where ci is the number of birds living in the i-th nest. It is guaranteed that $$\sum_{i=1}^{n} c_i \leq 10^4$$.

The third line contains n integers cost1, cost2, ..., costn (0 ≤ costi ≤ 109), where costi is the mana cost to summon a bird from the i-th nest.

## Output Format
Print a single integer — the maximum number of birds Imp can summon.

## Examples
```input
2 12 0 4
3 4
4 2
```
```output
6
```
-----
```input
4 1000 10 35
1 2 4 5
1000 500 250 200
```
```output
5
```
-----
```input
2 10 7 11
2 10
6 1
```
```output
11
```

## Note
In the first sample base amount of Imp's mana is equal to 12 (with maximum capacity also equal to 12). After he summons two birds from the first nest, he loses 8 mana points, although his maximum capacity will not increase (since B = 0). After this step his mana will be 4 of 12; during the move you will replenish 4 mana points, and hence own 8 mana out of 12 possible. Now it's optimal to take 4 birds from the second nest and spend 8 mana. The final answer will be — 6.

In the second sample the base amount of mana is equal to 1000. The right choice will be to simply pick all birds from the last nest. Note that Imp's mana doesn't restore while moving because it's initially full.

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
Imp is really pleased that you helped him. But it you solve the last problem, his gladness would raise even more.

- a is strictly less than b;
- a divides b without a remainder.

You are to find such a set $$1$$, which is a subset of {1, 2, ..., n} (the set that contains all positive integers not greater than n), that $$f(\mathbf{I}) = k$$.

## Input Format
The only line contains two integers n and k $$( 2 \leq n \leq 3 \cdot 10^{5}, 1 \leq k \leq \min ( 10^{9}, \frac { n \cdot ( n - 1 ) } { 2 } ) )$$.

## Output Format
If there is no answer, print "No".

Otherwise, in the first line print "Yes", in the second — an integer m that denotes the size of the set $$1$$ you have found, in the second line print m integers — the elements of the set $$1$$, in any order.

If there are multiple answers, print any of them.

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

## Note
In the second sample, the valid pairs in the output set are (1, 2), (1, 4), (1, 5), (1, 6), (2, 4), (2, 6). Thus, $$f(\{1,2,4,5,6\})=6$$.

In the third example, the valid pairs in the output set are (2, 4), (4, 8), (2, 8). Thus, $$f(\{2,4,5,8\})=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
The stardate is 1977 and the science and art of detecting Death Stars is in its infancy. Princess Heidi has received information about the stars in the nearby solar system from the Rebel spies and now, to help her identify the exact location of the Death Star, she needs to know whether this information is correct.

Two rebel spies have provided her with the maps of the solar system. Each map is an N × N grid, where each cell is either occupied by a star or empty. To see whether the information is correct, Heidi needs to know whether the two maps are of the same solar system, or if possibly one of the spies is actually an Empire double agent, feeding her false information.

Unfortunately, spies may have accidentally rotated a map by 90, 180, or 270 degrees, or flipped it along the vertical or the horizontal axis, before delivering it to Heidi. If Heidi can rotate or flip the maps so that two of them become identical, then those maps are of the same solar system. Otherwise, there are traitors in the Rebel ranks! Help Heidi find out.

## Input Format
The first line of the input contains one number N (1 ≤ N ≤ 10) – the dimension of each map. Next N lines each contain N characters, depicting the first map: 'X' indicates a star, while 'O' indicates an empty quadrant of space. Next N lines each contain N characters, depicting the second map in the same format.

## Output Format
The only line of output should contain the word Yes if the maps are identical, or No if it is impossible to match them by performing rotations and translations.

## Examples
```input
4
XOOO
XXOO
OOOO
XXXX
XOOO
XOOO
XOXO
XOXX
```
```output
Yes
```
-----
```input
2
XX
OO
XO
OX
```
```output
No
```

## Note
In the first test, you can match the first map to the second map by first flipping the first map along the vertical axis, and then by rotating it 90 degrees clockwise.

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
The Rebel fleet is afraid that the Empire might want to strike back again. Princess Heidi needs to know if it is possible to assign R Rebel spaceships to guard B bases so that every base has exactly one guardian and each spaceship has exactly one assigned base (in other words, the assignment is a perfect matching). Since she knows how reckless her pilots are, she wants to be sure that any two (straight) paths – from a base to its assigned spaceship – do not intersect in the galaxy plane (that is, in 2D), and so there is no risk of collision.

## Input Format
The first line contains two space-separated integers R, B(1 ≤ R, B ≤ 10). For 1 ≤ i ≤ R, the i + 1-th line contains two space-separated integers xi and yi (|xi|, |yi| ≤ 10000) denoting the coordinates of the i-th Rebel spaceship. The following B lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and that no three points are on the same line.

## Output Format
If it is possible to connect Rebel spaceships and bases so as satisfy the constraint, output Yes, otherwise output No (without quote).

## Examples
```input
3 3
0 0
2 0
3 1
-2 1
0 3
2 2
```
```output
Yes
```
-----
```input
2 1
1 0
2 2
3 1
```
```output
No
```

## Note
For the first example, one possible way is to connect the Rebels and bases in order.

For the second example, there is no perfect matching between Rebels and bases.

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

# Problem
Princess Heidi decided to give orders to all her K Rebel ship commanders in person. Unfortunately, she is currently travelling through hyperspace, and will leave it only at N specific moments t1, t2, ..., tN. The meetings with commanders must therefore start and stop at those times. Namely, each commander will board her ship at some time ti and disembark at some later time tj. Of course, Heidi needs to meet with all commanders, and no two meetings can be held during the same time. Two commanders cannot even meet at the beginnings/endings of the hyperspace jumps, because too many ships in one position could give out their coordinates to the enemy.

Your task is to find minimum time that Princess Heidi has to spend on meetings, with her schedule satisfying the conditions above.

## Input Format
The first line contains two integers K, N (2 ≤ 2K ≤ N ≤ 500000, K ≤ 5000). The second line contains N distinct integers t1, t2, ..., tN (1 ≤ ti ≤ 109) representing the times when Heidi leaves hyperspace.

## Output Format
Output only one integer: the minimum time spent on meetings.

## Examples
```input
2 5
1 4 6 7 12
```
```output
4
```
-----
```input
3 6
6 3 4 2 5 1
```
```output
3
```
-----
```input
4 12
15 7 4 19 3 30 14 1 5 23 17 25
```
```output
6
```

## Note
In the first example, there are five valid schedules: [1, 4], [6, 7] with total time 4, [1, 4], [6, 12] with total time 9, [1, 4], [7, 12] with total time 8, [1, 6], [7, 12] with total time 10, and [4, 6], [7, 12] with total time 7. So the answer is 4.

In the second example, there is only 1 valid schedule: [1, 2], [3, 4], [5, 6].

For the third example, one possible schedule with total time 6 is: [1, 3], [4, 5], [14, 15], [23, 25].

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 is unrest in the Galactic Senate. Several thousand solar systems have declared their intentions to leave the Republic. Master Heidi needs to select the Jedi Knights who will go on peacekeeping missions throughout the galaxy. It is well-known that the success of any peacekeeping mission depends on the colors of the lightsabers of the Jedi who will go on that mission.

Heidi has n Jedi Knights standing in front of her, each one with a lightsaber of one of m possible colors. She knows that for the mission to be the most effective, she needs to select some contiguous interval of knights such that there are exactly k1 knights with lightsabers of the first color, k2 knights with lightsabers of the second color, ..., km knights with lightsabers of the m-th color. Help her find out if this is possible.

## Input Format
The first line of the input contains n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ n). The second line contains n integers in the range {1, 2, ..., m} representing colors of the lightsabers of the subsequent Jedi Knights. The third line contains m integers k1, k2, ..., km (with $$1 \leq \sum_{i=1}^{m} k_i \leq n$$) – the desired counts of lightsabers of each color from 1 to m.

## Output Format
Output YES if an interval with prescribed color counts exists, or output NO if there is none.

## Examples
```input
5 2
1 1 2 2 1
1 2
```
```output
YES
```

Now solve the problem and return the code.