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
Valera is a lazy student. He has m clean bowls and k clean plates.

Valera has made an eating plan for the next n days. As Valera is lazy, he will eat exactly one dish per day. At that, in order to eat a dish, he needs exactly one clean plate or bowl. We know that Valera can cook only two types of dishes. He can eat dishes of the first type from bowls and dishes of the second type from either bowls or plates.

When Valera finishes eating, he leaves a dirty plate/bowl behind. His life philosophy doesn't let him eat from dirty kitchenware. So sometimes he needs to wash his plate/bowl before eating. Find the minimum number of times Valera will need to wash a plate/bowl, if he acts optimally.

## Input Format
The first line of the input contains three integers n, m, k (1 ≤ n, m, k ≤ 1000) — the number of the planned days, the number of clean bowls and the number of clean plates.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 2). If ai equals one, then on day i Valera will eat a first type dish. If ai equals two, then on day i Valera will eat a second type dish.

## Output Format
Print a single integer — the minimum number of times Valera will need to wash a plate/bowl.

## Examples
```input
3 1 1
1 2 1
```
```output
1
```
-----
```input
4 3 1
1 1 1 1
```
```output
1
```
-----
```input
3 1 2
2 2 2
```
```output
0
```
-----
```input
8 2 2
1 2 1 2 1 2 1 2
```
```output
4
```

## Note
In the first sample Valera will wash a bowl only on the third day, so the answer is one.

In the second sample, Valera will have the first type of the dish during all four days, and since there are only three bowls, he will wash a bowl exactly once.

In the third sample, Valera will have the second type of dish for all three days, and as they can be eaten from either a plate or a bowl, he will never need to wash a plate/bowl.

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
Valera loves to participate in competitions. Especially in programming contests. Today he has participated in the contest with his team, consisting of n students (including Valera). This contest was an individual competition, so each student in the team solved problems individually.

After the contest was over, Valera was interested in results. He found out that:

- each student in the team scored at least l points and at most r points;
- in total, all members of the team scored exactly sall points;
- the total score of the k members of the team who scored the most points is equal to exactly sk; more formally, if a1, a2, ..., an is the sequence of points earned by the team of students in the non-increasing order (a1 ≥ a2 ≥ ... ≥ an), then sk = a1 + a2 + ... + ak.

However, Valera did not find out exactly how many points each of n students scored. Valera asked you to recover any distribution of scores between the students of the team, such that all the conditions above are met.

## Input Format
The first line of the input contains exactly six integers n, k, l, r, sall, sk (1 ≤ n, k, l, r ≤ 1000; l ≤ r; k ≤ n; 1 ≤ sk ≤ sall ≤ 106).

It's guaranteed that the input is such that the answer exists.

## Output Format
Print exactly n integers a1, a2, ..., an — the number of points each student scored. If there are multiple solutions, you can print any of them. You can print the distribution of points in any order.

## Examples
```input
5 3 1 3 13 9
```
```output
2 3 2 3 3
```
-----
```input
5 3 1 3 15 9
```
```output
3 3 3 3 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 city Valera lives in is going to hold elections to the city Parliament.

The city has n districts and n - 1 bidirectional roads. We know that from any district there is a path along the roads to any other district. Let's enumerate all districts in some way by integers from 1 to n, inclusive. Furthermore, for each road the residents decided if it is the problem road or not. A problem road is a road that needs to be repaired.

There are n candidates running the elections. Let's enumerate all candidates in some way by integers from 1 to n, inclusive. If the candidate number i will be elected in the city Parliament, he will perform exactly one promise — to repair all problem roads on the way from the i-th district to the district 1, where the city Parliament is located.

Help Valera and determine the subset of candidates such that if all candidates from the subset will be elected to the city Parliament, all problem roads in the city will be repaired. If there are several such subsets, you should choose the subset consisting of the minimum number of candidates.

## Input Format
The first line contains a single integer n (2 ≤ n ≤ 105) — the number of districts in the city.

Then n - 1 lines follow. Each line contains the description of a city road as three positive integers xi, yi, ti (1 ≤ xi, yi ≤ n, 1 ≤ ti ≤ 2) — the districts connected by the i-th bidirectional road and the road type. If ti equals to one, then the i-th road isn't the problem road; if ti equals to two, then the i-th road is the problem road.

It's guaranteed that the graph structure of the city is a tree.

## Output Format
In the first line print a single non-negative number k — the minimum size of the required subset of candidates. Then on the second line print k space-separated integers a1, a2, ... ak — the numbers of the candidates that form the required subset. If there are multiple solutions, you are allowed to print any of them.

## Examples
```input
5
1 2 2
2 3 2
3 4 2
4 5 2
```
```output
1
5
```
-----
```input
5
1 2 1
2 3 2
2 4 1
4 5 1
```
```output
1
3
```
-----
```input
5
1 2 2
1 3 2
1 4 2
1 5 2
```
```output
4
5 4 3 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
One fine morning, n fools lined up in a row. After that, they numbered each other with numbers from 1 to n, inclusive. Each fool got a unique number. The fools decided not to change their numbers before the end of the fun.

Every fool has exactly k bullets and a pistol. In addition, the fool number i has probability of pi (in percent) that he kills the fool he shoots at.

The fools decided to have several rounds of the fun. Each round of the fun looks like this: each currently living fool shoots at another living fool with the smallest number (a fool is not stupid enough to shoot at himself). All shots of the round are perfomed at one time (simultaneously). If there is exactly one living fool, he does not shoot.

Let's define a situation as the set of numbers of all the living fools at the some time. We say that a situation is possible if for some integer number j (0 ≤ j ≤ k) there is a nonzero probability that after j rounds of the fun this situation will occur.

Valera knows numbers p1, p2, ..., pn and k. Help Valera determine the number of distinct possible situations.

## Input Format
The first line contains two integers n, k (1 ≤ n, k ≤ 3000) — the initial number of fools and the number of bullets for each fool.

The second line contains n integers p1, p2, ..., pn (0 ≤ pi ≤ 100) — the given probabilities (in percent).

## Output Format
Print a single number — the answer to the problem.

## Examples
```input
3 3
50 50 50
```
```output
7
```
-----
```input
1 1
100
```
```output
1
```
-----
```input
2 1
100 100
```
```output
2
```
-----
```input
3 3
0 0 0
```
```output
1
```

## Note
In the first sample, any situation is possible, except for situation {1, 2}.

In the second sample there is exactly one fool, so he does not make shots.

In the third sample the possible situations are {1, 2} (after zero rounds) and the "empty" situation {} (after one round).

In the fourth sample, the only possible situation is {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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Valera loves segments. He has recently come up with one interesting problem.

The Ox axis of coordinates has n segments, the i-th segment starts in position li and ends in position ri (we will mark it as [li, ri]). Your task is to process m queries, each consists of number cnti and a set of cnti coordinates of points located on the Ox axis. The answer to the query is the number of segments, such that each of them contains at least one point from the query. Segment [l, r] contains point q, if l ≤ q ≤ r.

Valera found the solution of this problem too difficult. So he asked you to help him. Help Valera.

## Input Format
The first line contains two integers n, m (1 ≤ n, m ≤ 3·105) — the number of segments on the axis of coordinates and the number of queries.

Next n lines contain the descriptions of the segments. The i-th line contains two positive integers li, ri (1 ≤ li ≤ ri ≤ 106) — the borders of the i-th segment.

Next m lines contain the description of the queries, one per line. Each line starts from integer cnti (1 ≤ cnti ≤ 3·105) — the number of points in the i-th query. Then the line contains cnti distinct positive integers p1, p2, ..., pcnti (1 ≤ p1 < p2 < ... < pcnti ≤ 106) — the coordinates of points in the i-th query.

It is guaranteed that the total number of points in all queries doesn't exceed 3·105.

## Output Format
Print m non-negative integers, where the i-th number is the response to the i-th query.

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

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
The cinema theater hall in Sereja's city is n seats lined up in front of one large screen. There are slots for personal possessions to the left and to the right of each seat. Any two adjacent seats have exactly one shared slot. The figure below shows the arrangement of seats and slots for n = 4.

Today it's the premiere of a movie called "Dry Hard". The tickets for all the seats have been sold. There is a very strict controller at the entrance to the theater, so all n people will come into the hall one by one. As soon as a person enters a cinema hall, he immediately (momentarily) takes his seat and occupies all empty slots to the left and to the right from him. If there are no empty slots, the man gets really upset and leaves.

People are not very constant, so it's hard to predict the order in which the viewers will enter the hall. For some seats, Sereja knows the number of the viewer (his number in the entering queue of the viewers) that will come and take this seat. For others, it can be any order.

Being a programmer and a mathematician, Sereja wonders: how many ways are there for the people to enter the hall, such that nobody gets upset? As the number can be quite large, print it modulo 1000000007 (109 + 7).

## Input Format
The first line contains integer n (1 ≤ n ≤ 105). The second line contains n integers, the i-th integer shows either the index of the person (index in the entering queue) with the ticket for the i-th seat or a 0, if his index is not known. It is guaranteed that all positive numbers in the second line are distinct.

You can assume that the index of the person who enters the cinema hall is a unique integer from 1 to n. The person who has index 1 comes first to the hall, the person who has index 2 comes second and so on.

## Output Format
In a single line print the remainder after dividing the answer by number 1000000007 (109 + 7).

## Examples
```input
11
0 0 0 0 0 0 0 0 0 0 0
```
```output
1024
```
-----
```input
6
0 3 1 0 0 0
```
```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
Let's assume that we have a sequence of doubles a1, a2, ..., a|a| and a double variable x. You are allowed to perform the following two-staged operation:

1. choose an index of the sequence element i (1 ≤ i ≤ |a|);
2. consecutively perform assignments: $$\begin{align*}
tmp &= \frac{a_i + x}{2}, \\
a_i &= tmp, \\
x &= tmp.
\end{align*}$$.

Let's use function g(a, x) to represent the largest value that can be obtained from variable x, using the described operation any number of times and sequence a.

Sereja has sequence b1, b2, ..., b|b|. Help Sereja calculate sum: $$\sum_{i=1}^{|b|}\sum_{j=i}^{|b|}g([b_i,b_{i+1},\ldots,b_j],0)$$. Record [bi, bi + 1, ..., bj] represents a sequence containing the elements in brackets in the given order. To avoid problems with precision, please, print the required sum divided by |b|2.

## Input Format
The first line contains integer |b| (1 ≤ |b| ≤ 3·105) — the length of sequence b. The second line contains |b| integers b1, b2, ..., b|b| (1 ≤ bi ≤ 105).

## Output Format
In a single line print a real number — the required sum divided by |b|2. Your answer will be considered correct if its absolute or relative error won't exceed 10 - 6.

## Examples
```input
5
1 2 3 4 1
```
```output
1.238750000000000
```

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
Iahub likes chess very much. He even invented a new chess piece named Coder. A Coder can move (and attack) one square horizontally or vertically. More precisely, if the Coder is located at position (x, y), he can move to (or attack) positions (x + 1, y), (x–1, y), (x, y + 1) and (x, y–1).

Iahub wants to know how many Coders can be placed on an n × n chessboard, so that no Coder attacks any other Coder.

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

## Output Format
On the first line print an integer, the maximum number of Coders that can be placed on the chessboard.

On each of the next n lines print n characters, describing the configuration of the Coders. For an empty cell print an '.', and for a Coder print a 'C'.

If there are multiple correct answers, you can print any.

## Examples
```input
2
```
```output
2
C.
.C
```

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
Iahub wants to enhance his multitasking abilities. In order to do this, he wants to sort n arrays simultaneously, each array consisting of m integers.

Iahub can choose a pair of distinct indices i and j (1 ≤ i, j ≤ m, i ≠ j). Then in each array the values at positions i and j are swapped only if the value at position i is strictly greater than the value at position j.

Iahub wants to find an array of pairs of distinct indices that, chosen in order, sort all of the n arrays in ascending or descending order (the particular order is given in input). The size of the array can be at most $$\frac{m(m-1)}{2}$$ (at most $$\frac{m(m-1)}{2}$$ pairs). Help Iahub, find any suitable array.

## Input Format
The first line contains three integers n (1 ≤  n ≤ 1000), m (1 ≤ m ≤  100) and k. Integer k is 0 if the arrays must be sorted in ascending order, and 1 if the arrays must be sorted in descending order. Each line i of the next n lines contains m integers separated by a space, representing the i-th array. For each element x of the array i, 1 ≤ x ≤ 106 holds.

## Output Format
On the first line of the output print an integer p, the size of the array (p can be at most $$\frac{m(m-1)}{2}$$). Each of the next p lines must contain two distinct integers i and j (1 ≤ i, j ≤ m, i ≠ j), representing the chosen indices.

If there are multiple correct answers, you can print any.

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

## Note
Consider the first sample. After the first operation, the arrays become [1, 3, 2, 5, 4] and [1, 2, 3, 4, 5]. After the second operation, the arrays become [1, 2, 3, 5, 4] and [1, 2, 3, 4, 5]. After the third operation they become [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5].

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 64.0 MB

# Problem
C*++ language is quite similar to C++. The similarity manifests itself in the fact that the programs written in C*++ sometimes behave unpredictably and lead to absolutely unexpected effects. For example, let's imagine an arithmetic expression in C*++ that looks like this (expression is the main term):

- expression ::= summand | expression + summand | expression - summand
- summand ::= increment | coefficient*increment
- increment ::= a++ | ++a
- coefficient ::= 0|1|2|...|1000

For example, "5*a++-3*++a+a++" is a valid expression in C*++.

Thus, we have a sum consisting of several summands divided by signs "+" or "-". Every summand is an expression "a++" or "++a" multiplied by some integer coefficient. If the coefficient is omitted, it is suggested being equal to 1.

The calculation of such sum in C*++ goes the following way. First all the summands are calculated one after another, then they are summed by the usual arithmetic rules. If the summand contains "a++", then during the calculation first the value of the "a" variable is multiplied by the coefficient, then value of "a" is increased by 1. If the summand contains "++a", then the actions on it are performed in the reverse order: first "a" is increased by 1, then — multiplied by the coefficient.

The summands may be calculated in any order, that's why sometimes the result of the calculation is completely unpredictable! Your task is to find its largest possible value.

## Input Format
The first input line contains an integer a ( - 1000 ≤ a ≤ 1000) — the initial value of the variable "a". The next line contains an expression in C*++ language of the described type. The number of the summands in the expression does not exceed 1000. It is guaranteed that the line describing the expression contains no spaces and tabulation.

## Output Format
Output a single number — the maximal possible value of the expression.

## Examples
```input
1
5*a++-3*++a+a++
```
```output
11
```
-----
```input
3
a+++++a
```
```output
8
```

## Note
Consider the second example. Initially a = 3. Suppose that at first the first summand is calculated, and then the second one is. The first summand gets equal to 3, and the value of a is increased by 1. At the calculation of the second summand a is increased once more (gets equal to 5). The value of the second summand is 5, and together they give 8. If we calculate the second summand first and the first summand later, then the both summands equals to 4, and the result is 8, too.

Now solve the problem and return the code.