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
Danil decided to earn some money, so he had found a part-time job. The interview have went well, so now he is a light switcher.

Danil works in a rooted tree (undirected connected acyclic graph) with n vertices, vertex 1 is the root of the tree. There is a room in each vertex, light can be switched on or off in each room. Danil's duties include switching light in all rooms of the subtree of the vertex. It means that if light is switched on in some room of the subtree, he should switch it off. Otherwise, he should switch it on.

Unfortunately (or fortunately), Danil is very lazy. He knows that his boss is not going to personally check the work. Instead, he will send Danil tasks using Workforces personal messages.

There are two types of tasks:

1. pow v describes a task to switch lights in the subtree of vertex v.
2. get v describes a task to count the number of rooms in the subtree of v, in which the light is turned on. Danil should send the answer to his boss using Workforces messages.

A subtree of vertex v is a set of vertices for which the shortest path from them to the root passes through v. In particular, the vertex v is in the subtree of v.

Danil is not going to perform his duties. He asks you to write a program, which answers the boss instead of him.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 200 000) — the number of vertices in the tree.

The second line contains n - 1 space-separated integers p2, p3, ..., pn (1 ≤ pi < i), where pi is the ancestor of vertex i.

The third line contains n space-separated integers t1, t2, ..., tn (0 ≤ ti ≤ 1), where ti is 1, if the light is turned on in vertex i and 0 otherwise.

The fourth line contains a single integer q (1 ≤ q ≤ 200 000) — the number of tasks.

The next q lines are get v or pow v (1 ≤ v ≤ n) — the tasks described above.

## Output Format
For each task get v print the number of rooms in the subtree of v, in which the light is turned on.

## Examples
```input
4
1 1 1
1 0 0 1
9
get 1
get 2
get 3
get 4
pow 1
get 1
get 2
get 3
get 4
```
```output
2
0
0
1
2
1
1
0
```

## Note
The tree before the task pow 1. The tree after the task pow 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
The following problem is well-known: given integers n and m, calculate

$$2^n \bmod m$$,

where 2n = 2·2·...·2 (n factors), and $$x \bmod y$$ denotes the remainder of division of x by y.

You are asked to solve the "reverse" problem. Given integers n and m, calculate

$$m \mod 2^n$$.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 108).

The second line contains a single integer m (1 ≤ m ≤ 108).

## Output Format
Output a single integer — the value of $$m \mod 2^n$$.

## Examples
```input
4
42
```
```output
10
```
-----
```input
1
58
```
```output
0
```
-----
```input
98765432
23456789
```
```output
23456789
```

## Note
In the first example, the remainder of division of 42 by 24 = 16 is equal to 10.

In the second example, 58 is divisible by 21 = 2 without remainder, and the answer is 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Consider a rooted tree. A rooted tree has one special vertex called the root. All edges are directed from the root. Vertex u is called a child of vertex v and vertex v is called a parent of vertex u if there exists a directed edge from v to u. A vertex is called a leaf if it doesn't have children and has a parent.

Let's call a rooted tree a spruce if its every non-leaf vertex has at least 3 leaf children. You are given a rooted tree, check whether it's a spruce.

The definition of a rooted tree can be found here.

## Input Format
The first line contains one integer n — the number of vertices in the tree (3 ≤ n ≤ 1 000). Each of the next n - 1 lines contains one integer pi (1 ≤ i ≤ n - 1) — the index of the parent of the i + 1-th vertex (1 ≤ pi ≤ i).

Vertex 1 is the root. It's guaranteed that the root has at least 2 children.

## Output Format
Print "Yes" if the tree is a spruce and "No" otherwise.

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

## Note
The first example:

The second example:

It is not a spruce, because the non-leaf vertex 1 has only 2 leaf children.

The third example:

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
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 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 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 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: 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 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
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 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
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 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
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 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
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 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
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 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
We've got no test cases. A big olympiad is coming up. But the problemsetters' number one priority should be adding another problem to the round.

The diameter of a multiset of points on the line is the largest distance between two points from this set. For example, the diameter of the multiset {1, 3, 2, 1} is 2.

Diameter of multiset consisting of one point is 0.

You are given n points on the line. What is the minimum number of points you have to remove, so that the diameter of the multiset of the remaining points will not exceed d?

## Input Format
The first line contains two integers n and d (1 ≤ n ≤ 100, 0 ≤ d ≤ 100) — the amount of points and the maximum allowed diameter respectively.

The second line contains n space separated integers (1 ≤ xi ≤ 100) — the coordinates of the points.

## Output Format
Output a single integer — the minimum number of points you have to remove.

## Examples
```input
3 1
2 1 4
```
```output
1
```
-----
```input
3 0
7 7 7
```
```output
0
```
-----
```input
6 3
1 3 4 6 9 10
```
```output
3
```

## Note
In the first test case the optimal strategy is to remove the point with coordinate 4. The remaining points will have coordinates 1 and 2, so the diameter will be equal to 2 - 1 = 1.

In the second test case the diameter is equal to 0, so its is unnecessary to remove any points.

In the third test case the optimal strategy is to remove points with coordinates 1, 9 and 10. The remaining points will have coordinates 3, 4 and 6, so the diameter will be equal to 6 - 3 = 3.

Now solve the problem and return the code.