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
Even polar bears feel cold when lying on the ice. Therefore, a polar bear Alice is going to make a carpet. The carpet can be viewed as a grid with height h and width w. Then the grid is divided into h × w squares. Alice is going to assign one of k different colors to each square. The colors are numbered from 1 to k. She may choose not to use all of the colors.

However, there are some restrictions. For every two adjacent squares (squares that shares an edge) x and y, there is a color constraint in one of the forms:

- color(x) = color(y), or
- color(x) ≠ color(y).

Example of the color constraints:

Ideally, Alice wants to satisfy all color constraints. But again, life in the Arctic is hard. It is not always possible to satisfy all color constraints. Fortunately, she will still be happy if at least $$\frac{3}{4}$$ of the color constraints are satisfied.

If she has 4 colors she can color the carpet in the following way:

And she is happy because $${ \frac { 1 3 } { 1 7 } }$$ of the color constraints are satisfied, and $$\frac{13}{17} \geq \frac{3}{4}$$. Your task is to help her color the carpet.

## Input Format
The first line contains three integers h, w, k (2 ≤ h, w ≤ 1000, 1 ≤ k ≤ w·h).

The next 2h - 1 lines describe the color constraints from top to bottom, left to right. They contain w - 1, w, w - 1, w, ..., w - 1 characters respectively. Each color constraint is represented by a character "E" or "N", where "E" means " = " and "N" means " ≠ ".

The color constraints listed in the order they are depicted on the picture.

## Output Format
If there is a coloring that satisfies at least $$\frac{3}{4}$$ of the color constraints, print "YES" (without quotes) in the first line. In each of the next h lines, print w integers describing the coloring.

Otherwise, print "NO" (without quotes).

## Examples
```input
3 4 4
ENE
NNEE
NEE
ENEN
ENN
```
```output
YES
1 1 2 2
3 4 1 1
3 3 2 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
Eugeny has array a = a1, a2, ..., an, consisting of n integers. Each integer ai equals to -1, or to 1. Also, he has m queries:

- Query number i is given as a pair of integers li, ri (1 ≤ li ≤ ri ≤ n).
- The response to the query will be integer 1, if the elements of array a can be rearranged so as the sum ali + ali + 1 + ... + ari = 0, otherwise the response to the query will be integer 0.

Help Eugeny, answer all his queries.

## Input Format
The first line contains integers n and m (1 ≤ n, m ≤ 2·105). The second line contains n integers a1, a2, ..., an (ai = -1, 1). Next m lines contain Eugene's queries. The i-th line contains integers li, ri (1 ≤ li ≤ ri ≤ n).

## Output Format
Print m integers — the responses to Eugene's queries in the order they occur in the input.

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

# Problem
Eugeny loves listening to music. He has n songs in his play list. We know that song number i has the duration of ti minutes. Eugeny listens to each song, perhaps more than once. He listens to song number i ci times. Eugeny's play list is organized as follows: first song number 1 plays c1 times, then song number 2 plays c2 times, ..., in the end the song number n plays cn times.

Eugeny took a piece of paper and wrote out m moments of time when he liked a song. Now for each such moment he wants to know the number of the song that played at that moment. The moment x means that Eugeny wants to know which song was playing during the x-th minute of his listening to the play list.

Help Eugeny and calculate the required numbers of songs.

## Input Format
The first line contains two integers n, m (1 ≤ n, m ≤ 105). The next n lines contain pairs of integers. The i-th line contains integers ci, ti (1 ≤ ci, ti ≤ 109) — the description of the play list. It is guaranteed that the play list's total duration doesn't exceed 109 $$(\sum_{i=1}^{n} c_i \cdot t_i \leq 10^9)$$.

The next line contains m positive integers v1, v2, ..., vm, that describe the moments Eugeny has written out. It is guaranteed that there isn't such moment of time vi, when the music doesn't play any longer. It is guaranteed that vi < vi + 1 (i < m).

The moment of time vi means that Eugeny wants to know which song was playing during the vi-th munite from the start of listening to the playlist.

## Output Format
Print m integers — the i-th number must equal the number of the song that was playing during the vi-th minute after Eugeny started listening to the play list.

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

# Problem
Many schoolchildren look for a job for the summer, and one day, when Gerald was still a schoolboy, he also decided to work in the summer. But as Gerald was quite an unusual schoolboy, he found quite unusual work. A certain Company agreed to pay him a certain sum of money if he draws them three identical circles on a plane. The circles must not interfere with each other (but they may touch each other). He can choose the centers of the circles only from the n options granted by the Company. He is free to choose the radius of the circles himself (all three radiuses must be equal), but please note that the larger the radius is, the more he gets paid.

Help Gerald earn as much as possible.

## Input Format
The first line contains a single integer n — the number of centers (3 ≤ n ≤ 3000). The following n lines each contain two integers xi, yi ( - 104 ≤ xi, yi ≤ 104) — the coordinates of potential circle centers, provided by the Company.

All given points are distinct.

## Output Format
Print a single real number — maximum possible radius of circles. The answer will be accepted if its relative or absolute error doesn't exceed 10 - 6.

## Examples
```input
3
0 1
1 0
1 1
```
```output
0.50000000000000000000
```
-----
```input
7
2 -3
-2 -3
3 0
-3 -1
1 -2
2 -2
-1 0
```
```output
1.58113883008418980000
```

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
n soldiers stand in a circle. For each soldier his height ai is known. A reconnaissance unit can be made of such two neighbouring soldiers, whose heights difference is minimal, i.e. |ai - aj| is minimal. So each of them will be less noticeable with the other. Output any pair of soldiers that can form a reconnaissance unit.

## Input Format
The first line contains integer n (2 ≤ n ≤ 100) — amount of soldiers. Then follow the heights of the soldiers in their order in the circle — n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 1000). The soldier heights are given in clockwise or counterclockwise direction.

## Output Format
Output two integers — indexes of neighbouring soldiers, who should form a reconnaissance unit. If there are many optimum solutions, output any of them. Remember, that the soldiers stand in a circle.

## Examples
```input
5
10 12 13 15 10
```
```output
5 1
```
-----
```input
4
10 20 30 40
```
```output
1 2
```

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Once Bob got to a sale of old TV sets. There were n TV sets at that sale. TV set with index i costs ai bellars. Some TV sets have a negative price — their owners are ready to pay Bob if he buys their useless apparatus. Bob can «buy» any TV sets he wants. Though he's very strong, Bob can carry at most m TV sets, and he has no desire to go to the sale for the second time. Please, help Bob find out the maximum sum of money that he can earn.

## Input Format
The first line contains two space-separated integers n and m (1 ≤ m ≤ n ≤ 100) — amount of TV sets at the sale, and amount of TV sets that Bob can carry. The following line contains n space-separated integers ai ( - 1000 ≤ ai ≤ 1000) — prices of the TV sets.

## Output Format
Output the only number — the maximum sum of money that Bob can earn, given that he can carry at most m TV sets.

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

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
«Bersoft» company is working on a new version of its most popular text editor — Bord 2010. Bord, like many other text editors, should be able to print out multipage documents. A user keys a sequence of the document page numbers that he wants to print out (separates them with a comma, without spaces).

Your task is to write a part of the program, responsible for «standardization» of this sequence. Your program gets the sequence, keyed by the user, as input. The program should output this sequence in format l1-r1,l2-r2,...,lk-rk, where ri + 1 < li + 1 for all i from 1 to k - 1, and li ≤ ri. The new sequence should contain all the page numbers, keyed by the user, and nothing else. If some page number appears in the input sequence several times, its appearances, starting from the second one, should be ignored. If for some element i from the new sequence li = ri, this element should be output as li, and not as «li - li».

For example, sequence 1,2,3,1,1,2,6,6,2 should be output as 1-3,6.

## Input Format
The only line contains the sequence, keyed by the user. The sequence contains at least one and at most 100 positive integer numbers. It's guaranteed, that this sequence consists of positive integer numbers, not exceeding 1000, separated with a comma, doesn't contain any other characters, apart from digits and commas, can't end with a comma, and the numbers don't contain leading zeroes. Also it doesn't start with a comma or contain more than one comma in a row.

## Output Format
Output the sequence in the required format.

## Examples
```input
1,2,3,1,1,2,6,6,2
```
```output
1-3,6
```
-----
```input
3,2,1
```
```output
1-3
```
-----
```input
30,20,10
```
```output
10,20,30
```

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There are n cities in Berland. Each city has its index — an integer number from 1 to n. The capital has index r1. All the roads in Berland are two-way. The road system is such that there is exactly one path from the capital to each city, i.e. the road map looks like a tree. In Berland's chronicles the road map is kept in the following way: for each city i, different from the capital, there is kept number pi — index of the last city on the way from the capital to i.

Once the king of Berland Berl XXXIV decided to move the capital from city r1 to city r2. Naturally, after this the old representation of the road map in Berland's chronicles became incorrect. Please, help the king find out a new representation of the road map in the way described above.

## Input Format
The first line contains three space-separated integers n, r1, r2 (2 ≤ n ≤ 5·104, 1 ≤ r1 ≠ r2 ≤ n) — amount of cities in Berland, index of the old capital and index of the new one, correspondingly.

The following line contains n - 1 space-separated integers — the old representation of the road map. For each city, apart from r1, there is given integer pi — index of the last city on the way from the capital to city i. All the cities are described in order of increasing indexes.

## Output Format
Output n - 1 numbers — new representation of the road map in the same format.

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

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
On a number line there are n balls. At time moment 0 for each ball the following data is known: its coordinate xi, speed vi (possibly, negative) and weight mi. The radius of the balls can be ignored.

The balls collide elastically, i.e. if two balls weighing m1 and m2 and with speeds v1 and v2 collide, their new speeds will be:

$$v_{1}^{\prime }=\frac{(m_{1}-m_{2})v_{1}+2m_{2}v_{2}}{m_{1}+m_{2}},v_{2}^{\prime }=\frac{(m_{2}-m_{1})v_{2}+2m_{1}v_{1}}{m_{1}+m_{2}}$$

Your task is to find out, where each ball will be t seconds after.

## Input Format
The first line contains two integers n and t (1 ≤ n ≤ 10, 0 ≤ t ≤ 100) — amount of balls and duration of the process. Then follow n lines, each containing three integers: xi, vi, mi (1 ≤ |vi|, mi ≤ 100, |xi| ≤ 100) — coordinate, speed and weight of the ball with index i at time moment 0.

It is guaranteed that no two balls have the same coordinate initially. Also each collision will be a collision of not more than two balls (that is, three or more balls never collide at the same point in all times from segment [0;t]).

## Output Format
Output n numbers — coordinates of the balls t seconds after. Output the numbers accurate to at least 4 digits after the decimal point.

## Examples
```input
2 9
3 4 5
0 7 8
```
```output
68.538461538
44.538461538
```
-----
```input
3 10
1 2 3
4 -5 6
7 -8 9
```
```output
-93.666666667
-74.666666667
-15.666666667
```

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The new "Die Hard" movie has just been released! There are n people at the cinema box office standing in a huge line. Each of them has a single 100, 50 or 25 ruble bill. A "Die Hard" ticket costs 25 rubles. Can the booking clerk sell a ticket to each person and give the change if he initially has no money and sells the tickets strictly in the order people follow in the line?

## Input Format
The first line contains integer n (1 ≤ n ≤ 105) — the number of people in the line. The next line contains n integers, each of them equals 25, 50 or 100 — the values of the bills the people have. The numbers are given in the order from the beginning of the line (at the box office) to the end of the line.

## Output Format
Print "YES" (without the quotes) if the booking clerk can sell a ticket to each person and give the change. Otherwise print "NO".

## Examples
```input
4
25 25 50 50
```
```output
YES
```
-----
```input
2
25 100
```
```output
NO
```
-----
```input
4
50 50 25 25
```
```output
NO
```

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
Igor has fallen in love with Tanya. Now Igor wants to show his feelings and write a number on the fence opposite to Tanya's house. Igor thinks that the larger the number is, the more chance to win Tanya's heart he has.

Unfortunately, Igor could only get v liters of paint. He did the math and concluded that digit d requires ad liters of paint. Besides, Igor heard that Tanya doesn't like zeroes. That's why Igor won't use them in his number.

Help Igor find the maximum number he can write on the fence.

## Input Format
The first line contains a positive integer v (0 ≤ v ≤ 106). The second line contains nine positive integers a1, a2, ..., a9 (1 ≤ ai ≤ 105).

## Output Format
Print the maximum number Igor can write on the fence. If he has too little paint for any digit (so, he cannot write anything), print -1.

## Examples
```input
5
5 4 3 2 1 2 3 4 5
```
```output
55555
```
-----
```input
2
9 11 1 12 5 8 9 10 6
```
```output
33
```
-----
```input
0
1 1 1 1 1 1 1 1 1
```
```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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Cosider a sequence, consisting of n integers: a1, a2, ..., an. Jeff can perform the following operation on sequence a:

- take three integers v, t, k (1 ≤ v, t ≤ n; 0 ≤ k; v + tk ≤ n), such that av = av + t, av + t = av + 2t, ..., av + t(k - 1) = av + tk;
- remove elements av, av + t, ..., av + t·k from the sequence a, the remaining elements should be reindexed a1, a2, ..., an - k - 1.
- permute in some order the remaining elements of sequence a.

A beauty of a sequence a is the minimum number of operations that is needed to delete all elements from sequence a.

Jeff's written down a sequence of m integers b1, b2, ..., bm. Now he wants to ask q questions. Each question can be described with two integers li, ri. The answer to the question is the beauty of sequence bli, bli + 1, ..., bri. You are given the sequence b and all questions. Help Jeff, answer all his questions.

## Input Format
The first line contains integer m (1 ≤ m ≤ 105). The next line contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 105).

The third line contains integer q (1 ≤ q ≤ 105) — the number of questions. The next q lines contain pairs of integers, i-th of them contains a pair of integers li, ri (1 ≤ li ≤ ri ≤ m) — the description of i-th question.

## Output Format
In q lines print the answers to Jeff's queries. Print the answers according to the order of questions in input.

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

Now solve the problem and return the code.