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

# Problem
The New Year holidays are over, but Resha doesn't want to throw away the New Year tree. He invited his best friends Kerim and Gural to help him to redecorate the New Year tree.

The New Year tree is an undirected tree with n vertices and root in the vertex 1.

You should process the queries of the two types:

1. Change the colours of all vertices in the subtree of the vertex v to the colour c.
2. Find the number of different colours in the subtree of the vertex v.

## Input Format
The first line contains two integers n, m (1 ≤ n, m ≤ 4·105) — the number of vertices in the tree and the number of the queries.

The second line contains n integers ci (1 ≤ ci ≤ 60) — the colour of the i-th vertex.

Each of the next n - 1 lines contains two integers xj, yj (1 ≤ xj, yj ≤ n) — the vertices of the j-th edge. It is guaranteed that you are given correct undirected tree.

The last m lines contains the description of the queries. Each description starts with the integer tk (1 ≤ tk ≤ 2) — the type of the k-th query. For the queries of the first type then follows two integers vk, ck (1 ≤ vk ≤ n, 1 ≤ ck ≤ 60) — the number of the vertex whose subtree will be recoloured with the colour ck. For the queries of the second type then follows integer vk (1 ≤ vk ≤ n) — the number of the vertex for which subtree you should find the number of different colours.

## Output Format
For each query of the second type print the integer a — the number of different colours in the subtree of the vertex given in the query.

Each of the numbers should be printed on a separate line in order of query appearing in the input.

## Examples
```input
7 10
1 1 1 1 1 1 1
1 2
1 3
1 4
3 5
3 6
3 7
1 3 2
2 1
1 4 3
2 1
1 2 5
2 1
1 6 4
2 1
2 2
2 3
```
```output
2
3
4
5
1
2
```
-----
```input
23 30
1 2 2 6 5 3 2 1 1 1 2 4 5 3 4 4 3 3 3 3 3 4 6
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
4 11
6 12
6 13
7 14
7 15
7 16
8 17
8 18
10 19
10 20
10 21
11 22
11 23
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
2 1
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 4
```
```output
6
1
3
3
2
1
2
3
5
5
1
2
2
1
1
1
2
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
A tennis tournament with n participants is running. The participants are playing by an olympic system, so the winners move on and the losers drop out.

The tournament takes place in the following way (below, m is the number of the participants of the current round):

- let k be the maximal power of the number 2 such that k ≤ m,
- k participants compete in the current round and a half of them passes to the next round, the other m - k participants pass to the next round directly,
- when only one participant remains, the tournament finishes.

Each match requires b bottles of water for each participant and one bottle for the judge. Besides p towels are given to each participant for the whole tournament.

Find the number of bottles and towels needed for the tournament.

Note that it's a tennis tournament so in each match two participants compete (one of them will win and the other will lose).

## Input Format
The only line contains three integers n, b, p (1 ≤ n, b, p ≤ 500) — the number of participants and the parameters described in the problem statement.

## Output Format
Print two integers x and y — the number of bottles and towels need for the tournament.

## Examples
```input
5 2 3
```
```output
20 15
```
-----
```input
8 2 4
```
```output
35 32
```

## Note
In the first example will be three rounds:

1. in the first round will be two matches and for each match 5 bottles of water are needed (two for each of the participants and one for the judge),
2. in the second round will be only one match, so we need another 5 bottles of water,
3. in the third round will also be only one match, so we need another 5 bottles of water.

So in total we need 20 bottles of water.

In the second example no participant will move on to some round directly.

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
Limak is a little polar bear. He likes nice strings — strings of length n, consisting of lowercase English letters only.

The distance between two letters is defined as the difference between their positions in the alphabet. For example, $$\operatorname{dist}(c,e)=\operatorname{dist}(e,c)=2$$, and $$\operatorname{dist}(a,z)=\operatorname{dist}(z,a)=25$$.

Also, the distance between two nice strings is defined as the sum of distances of corresponding letters. For example, $$\operatorname{dist}(af,db)=\operatorname{dist}(a,d)+\operatorname{dist}(f,b)=3+4=7$$, and $$\operatorname{dist}(\text{bear}, \text{roar}) = 16 + 10 + 0 + 0 = 26$$.

Limak gives you a nice string s and an integer k. He challenges you to find any nice string s' that $$\text{dist}(s, s') = k$$. Find any s' satisfying the given conditions, or print "-1" if it's impossible to do so.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use gets/scanf/printf instead of getline/cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

## Input Format
The first line contains two integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 106).

The second line contains a string s of length n, consisting of lowercase English letters.

## Output Format
If there is no string satisfying the given conditions then print "-1" (without the quotes).

Otherwise, print any nice string s' that $$\text{dist}(s, s') = k$$.

## Examples
```input
4 26
bear
```
```output
roar
```
-----
```input
2 7
af
```
```output
db
```
-----
```input
3 1000
hey
```
```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: 64.0 MB

# Problem
Btoh yuo adn yuor roomatme lhoate wianshg disehs, btu stlil sdmoeboy msut peorrfm tihs cohre dialy. Oen dya yuo decdie to idourtcne smoe syestm. Yuor rmmotaoe sstgegus teh fooniwllg dael. Yuo argee on tow arayrs of ientgres M adn R, nmebur upmicnog dyas (induiclng teh cunrret oen) wtih sicsescuve irnegets (teh ceurrnt dya is zreo), adn yuo wsah teh diehss on dya D if adn olny if terhe etsixs an iednx i scuh taht D mod M[i] = R[i], otwsehrie yuor rmootmae deos it. Yuo lkie teh cncepot, btu yuor rmotaome's cuinnng simle meaks yuo ssecupt sthnoemig, so yuo itennd to vefriy teh fnerisas of teh aemnrgeet.

Yuo aer geivn ayarrs M adn R. Cuaclatle teh pceanregte of dyas on wchih yuo edn up dnoig teh wisahng. Amsuse taht yuo hvae iiiftlneny mnay dyas aehad of yuo.

## Input Format
The first line of input contains a single integer N (1 ≤ N ≤ 16).

The second and third lines of input contain N integers each, all between 0 and 16, inclusive, and represent arrays M and R, respectively. All M[i] are positive, for each i R[i] < M[i].

## Output Format
Output a single real number. The answer is considered to be correct if its absolute or relative error does not exceed 10 - 4.

## Examples
```input
1
2
0
```
```output
0.500000
```
-----
```input
2
2 3
1 0
```
```output
0.666667
```

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

# Problem
You can preview the image in better quality by the link: http://assets.codeforces.com/files/656/without-text.png

## Input Format
The only line of the input is a string (between 1 and 50 characters long, inclusive). Each character will be an alphanumeric character or a full stop ".".

## Output Format
Output the required answer.

## Examples
```input
Codeforces
```
```output
-87
```
-----
```input
APRIL.1st
```
```output
17
```

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

# Problem
You are given a complete undirected graph. For each pair of vertices you are given the length of the edge that connects them. Find the shortest paths between each pair of vertices in the graph and return the length of the longest of them.

## Input Format
The first line of the input contains a single integer N (3 ≤ N ≤ 10).

The following N lines each contain N space-separated integers. jth integer in ith line aij is the length of the edge that connects vertices i and j. aij = aji, aii = 0, 1 ≤ aij ≤ 100 for i ≠ j.

## Output Format
Output the maximum length of the shortest path between any pair of vertices in the graph.

## Examples
```input
3
0 1 1
1 0 4
1 4 0
```
```output
2
```
-----
```input
4
0 1 2 3
1 0 4 5
2 4 0 6
3 5 6 0
```
```output
5
```

## Note
You're running short of keywords, so you can't use some of them:

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

# Problem
A simple recommendation system would recommend a user things liked by a certain number of their friends. In this problem you will implement part of such a system.

You are given user's friends' opinions about a list of items. You are also given a threshold T — the minimal number of "likes" necessary for an item to be recommended to the user.

Output the number of items in the list liked by at least T of user's friends.

## Input Format
The first line of the input will contain three space-separated integers: the number of friends F (1 ≤ F ≤ 10), the number of items I (1 ≤ I ≤ 10) and the threshold T (1 ≤ T ≤ F).

The following F lines of input contain user's friends' opinions. j-th character of i-th line is 'Y' if i-th friend likes j-th item, and 'N' otherwise.

## Output Format
Output an integer — the number of items liked by at least T of user's friends.

## Examples
```input
3 3 2
YYY
NNN
YNY
```
```output
2
```
-----
```input
4 4 1
NNNY
NNYN
NYNN
YNNN
```
```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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
As some of you know, cubism is a trend in art, where the problem of constructing volumetrical shape on a plane with a combination of three-dimensional geometric shapes comes to the fore.

A famous sculptor Cicasso, whose self-portrait you can contemplate, hates cubism. He is more impressed by the idea to transmit two-dimensional objects through three-dimensional objects by using his magnificent sculptures. And his new project is connected with this. Cicasso wants to make a coat for the haters of anticubism. To do this, he wants to create a sculpture depicting a well-known geometric primitive — convex polygon.

Cicasso prepared for this a few blanks, which are rods with integer lengths, and now he wants to bring them together. The i-th rod is a segment of length li.

The sculptor plans to make a convex polygon with a nonzero area, using all rods he has as its sides. Each rod should be used as a side to its full length. It is forbidden to cut, break or bend rods. However, two sides may form a straight angle $$180^\circ$$.

Cicasso knows that it is impossible to make a convex polygon with a nonzero area out of the rods with the lengths which he had chosen. Cicasso does not want to leave the unused rods, so the sculptor decides to make another rod-blank with an integer length so that his problem is solvable. Of course, he wants to make it as short as possible, because the materials are expensive, and it is improper deed to spend money for nothing.

Help sculptor!

## Input Format
The first line contains an integer n (3 ≤ n ≤ 105) — a number of rod-blanks.

The second line contains n integers li (1 ≤ li ≤ 109) — lengths of rods, which Cicasso already has. It is guaranteed that it is impossible to make a polygon with n vertices and nonzero area using the rods Cicasso already has.

## Output Format
Print the only integer z — the minimum length of the rod, so that after adding it it can be possible to construct convex polygon with (n + 1) vertices and nonzero area from all of the rods.

## Examples
```input
3
1 2 1
```
```output
1
```
-----
```input
5
20 4 3 2 1
```
```output
11
```

## Note
In the first example triangle with sides {1 + 1 = 2, 2, 1} can be formed from a set of lengths {1, 1, 1, 2}.

In the second example you can make a triangle with lengths {20, 11, 4 + 3 + 2 + 1 = 10}.

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
After finishing eating her bun, Alyona came up with two integers n and m. She decided to write down two columns of integers — the first column containing integers from 1 to n and the second containing integers from 1 to m. Now the girl wants to count how many pairs of integers she can choose, one from the first column and the other from the second column, such that their sum is divisible by 5.

Formally, Alyona wants to count the number of pairs of integers (x, y) such that 1 ≤ x ≤ n, 1 ≤ y ≤ m and $$(x+y) \mod 5$$ equals 0.

As usual, Alyona has some troubles and asks you to help.

## Input Format
The only line of the input contains two integers n and m (1 ≤ n, m ≤ 1 000 000).

## Output Format
Print the only integer — the number of pairs of integers (x, y) such that 1 ≤ x ≤ n, 1 ≤ y ≤ m and (x + y) is divisible by 5.

## Examples
```input
6 12
```
```output
14
```
-----
```input
11 14
```
```output
31
```
-----
```input
1 5
```
```output
1
```
-----
```input
3 8
```
```output
5
```
-----
```input
5 7
```
```output
7
```
-----
```input
21 21
```
```output
88
```

## Note
Following pairs are suitable in the first sample case:

- for x = 1 fits y equal to 4 or 9;
- for x = 2 fits y equal to 3 or 8;
- for x = 3 fits y equal to 2, 7 or 12;
- for x = 4 fits y equal to 1, 6 or 11;
- for x = 5 fits y equal to 5 or 10;
- for x = 6 fits y equal to 4 or 9.

Only the pair (1, 4) is suitable in the third sample case.

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
Someone gave Alyona an array containing n positive integers a1, a2, ..., an. In one operation, Alyona can choose any element of the array and decrease it, i.e. replace with any positive integer that is smaller than the current one. Alyona can repeat this operation as many times as she wants. In particular, she may not apply any operation to the array at all.

Formally, after applying some operations Alyona will get an array of n positive integers b1, b2, ..., bn such that 1 ≤ bi ≤ ai for every 1 ≤ i ≤ n. Your task is to determine the maximum possible value of mex of this array.

Mex of an array in this problem is the minimum positive integer that doesn't appear in this array. For example, mex of the array containing 1, 3 and 4 is equal to 2, while mex of the array containing 2, 3 and 2 is equal to 1.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of elements in the Alyona's array.

The second line of the input contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array.

## Output Format
Print one positive integer — the maximum possible value of mex of the array after Alyona applies some (possibly none) operations.

## Examples
```input
5
1 3 3 3 6
```
```output
5
```
-----
```input
2
2 1
```
```output
3
```

## Note
In the first sample case if one will decrease the second element value to 2 and the fifth element value to 4 then the mex value of resulting array 1 2 3 3 4 will be equal to 5.

To reach the answer to the second sample case one must not decrease any of the array elements.

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
Alyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex 1, every vertex and every edge of which has a number written on.

The girl noticed that some of the tree's vertices are sad, so she decided to play with them. Let's call vertex v sad if there is a vertex u in subtree of vertex v such that dist(v, u) > au, where au is the number written on vertex u, dist(v, u) is the sum of the numbers written on the edges on the path from v to u.

Leaves of a tree are vertices connected to a single vertex by a single edge, but the root of a tree is a leaf if and only if the tree consists of a single vertex — root.

Thus Alyona decided to remove some of tree leaves until there will be no any sad vertex left in the tree. What is the minimum number of leaves Alyona needs to remove?

## Input Format
In the first line of the input integer n (1 ≤ n ≤ 105) is given — the number of vertices in the tree.

In the second line the sequence of n integers a1, a2, ..., an (1 ≤ ai ≤ 109) is given, where ai is the number written on vertex i.

The next n - 1 lines describe tree edges: ith of them consists of two integers pi and ci (1 ≤ pi ≤ n,  - 109 ≤ ci ≤ 109), meaning that there is an edge connecting vertices i + 1 and pi with number ci written on it.

## Output Format
Print the only integer — the minimum number of leaves Alyona needs to remove such that there will be no any sad vertex left in the tree.

## Examples
```input
9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8
```
```output
5
```

## Note
The following image represents possible process of removing leaves from the tree:

Now solve the problem and return the code.