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
Overlooking the captivating blend of myriads of vernal hues, Arkady the painter lays out a long, long canvas.

Arkady has a sufficiently large amount of paint of three colours: cyan, magenta, and yellow. On the one-dimensional canvas split into n consecutive segments, each segment needs to be painted in one of the colours.

Arkady has already painted some (possibly none or all) segments and passes the paintbrush to you. You are to determine whether there are at least two ways of colouring all the unpainted segments so that no two adjacent segments are of the same colour. Two ways are considered different if and only if a segment is painted in different colours in them.

## Input Format
The first line contains a single positive integer n (1 ≤ n ≤ 100) — the length of the canvas.

The second line contains a string s of n characters, the i-th of which is either 'C' (denoting a segment painted in cyan), 'M' (denoting one painted in magenta), 'Y' (one painted in yellow), or '?' (an unpainted one).

## Output Format
If there are at least two different ways of painting, output "Yes"; otherwise output "No" (both without quotes).

You can print each character in any case (upper or lower).

## Examples
```input
5
CY??Y
```
```output
Yes
```
-----
```input
5
C?C?Y
```
```output
Yes
```
-----
```input
5
?CYC?
```
```output
Yes
```
-----
```input
5
C??MM
```
```output
No
```
-----
```input
3
MMY
```
```output
No
```

## Note
For the first example, there are exactly two different ways of colouring: CYCMY and CYMCY.

For the second example, there are also exactly two different ways of colouring: CMCMY and CYCMY.

For the third example, there are four ways of colouring: MCYCM, MCYCY, YCYCM, and YCYCY.

For the fourth example, no matter how the unpainted segments are coloured, the existing magenta segments will prevent the painting from satisfying the requirements. The similar is true for the fifth 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 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
A set of points on a plane is called good, if for any two points at least one of the three conditions is true:

- those two points lie on same horizontal line;
- those two points lie on same vertical line;
- the rectangle, with corners in these two points, contains inside or on its borders at least one point of the set, other than these two. We mean here a rectangle with sides parallel to coordinates' axes, the so-called bounding box of the two points.

You are given a set consisting of n points on a plane. Find any good superset of the given set whose size would not exceed 2·105 points.

## Input Format
The first line contains an integer n (1 ≤ n ≤ 104) — the number of points in the initial set. Next n lines describe the set's points. Each line contains two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — a corresponding point's coordinates. It is guaranteed that all the points are different.

## Output Format
Print on the first line the number of points m (n ≤ m ≤ 2·105) in a good superset, print on next m lines the points. The absolute value of the points' coordinates should not exceed 109. Note that you should not minimize m, it is enough to find any good superset of the given set, whose size does not exceed 2·105.

All points in the superset should have integer coordinates.

## Examples
```input
2
1 1
2 2
```
```output
3
1 1
2 2
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
Nikita likes tasks on order statistics, for example, he can easily find the $$$k$$$-th number in increasing order on a segment of an array. But now Nikita wonders how many segments of an array there are such that a given number $$$x$$$ is the $$$k$$$-th number in increasing order on this segment. In other words, you should find the number of segments of a given array such that there are exactly $$$k$$$ numbers of this segment which are less than $$$x$$$.

Nikita wants to get answer for this question for each $$$k$$$ from $$$0$$$ to $$$n$$$, where $$$n$$$ is the size of the array.

## Input Format
The first line contains two integers $$$n$$$ and $$$x$$$ $$$(1 \le n \le 2 \cdot 10^5, -10^9 \le x \le 10^9)$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$ — the given array.

## Output Format
Print $$$n+1$$$ integers, where the $$$i$$$-th number is the answer for Nikita's question for $$$k=i-1$$$.

## Examples
```input
5 3
1 2 3 4 5
```
```output
6 5 4 0 0 0
```
-----
```input
2 6
-5 9
```
```output
1 2 0
```
-----
```input
6 99
-1 -1 -1 -1 -1 -1
```
```output
0 6 5 4 3 2 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
You are given a ternary string (it is a string which consists only of characters '0', '1' and '2').

You can swap any two adjacent (consecutive) characters '0' and '1' (i.e. replace "01" with "10" or vice versa) or any two adjacent (consecutive) characters '1' and '2' (i.e. replace "12" with "21" or vice versa).

For example, for string "010210" we can perform the following moves:

- "010210" $$$\rightarrow$$$ "100210";
- "010210" $$$\rightarrow$$$ "001210";
- "010210" $$$\rightarrow$$$ "010120";
- "010210" $$$\rightarrow$$$ "010201".

Note than you cannot swap "02" $$$\rightarrow$$$ "20" and vice versa. You cannot perform any other operations with the given string excluding described above.

You task is to obtain the minimum possible (lexicographically) string by using these swaps arbitrary number of times (possibly, zero).

String $$$a$$$ is lexicographically less than string $$$b$$$ (if strings $$$a$$$ and $$$b$$$ have the same length) if there exists some position $$$i$$$ ($$$1 \le i \le |a|$$$, where $$$|s|$$$ is the length of the string $$$s$$$) such that for every $$$j < i$$$ holds $$$a_j = b_j$$$, and $$$a_i < b_i$$$.

## Input Format
The first line of the input contains the string $$$s$$$ consisting only of characters '0', '1' and '2', its length is between $$$1$$$ and $$$10^5$$$ (inclusive).

## Output Format
Print a single string — the minimum possible (lexicographically) string you can obtain by using the swaps described above arbitrary number of times (possibly, zero).

## Examples
```input
100210
```
```output
001120
```
-----
```input
11222121
```
```output
11112222
```
-----
```input
20
```
```output
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Alice got an array of length $$$n$$$ as a birthday present once again! This is the third year in a row!

And what is more disappointing, it is overwhelmengly boring, filled entirely with zeros. Bob decided to apply some changes to the array to cheer up Alice.

Bob has chosen $$$m$$$ changes of the following form. For some integer numbers $$$x$$$ and $$$d$$$, he chooses an arbitrary position $$$i$$$ ($$$1 \le i \le n$$$) and for every $$$j \in [1, n]$$$ adds $$$x + d \cdot dist(i, j)$$$ to the value of the $$$j$$$-th cell. $$$dist(i, j)$$$ is the distance between positions $$$i$$$ and $$$j$$$ (i.e. $$$dist(i, j) = |i - j|$$$, where $$$|x|$$$ is an absolute value of $$$x$$$).

For example, if Alice currently has an array $$$[2, 1, 2, 2]$$$ and Bob chooses position $$$3$$$ for $$$x = -1$$$ and $$$d = 2$$$ then the array will become $$$[2 - 1 + 2 \cdot 2,~1 - 1 + 2 \cdot 1,~2 - 1 + 2 \cdot 0,~2 - 1 + 2 \cdot 1]$$$ = $$$[5, 2, 1, 3]$$$. Note that Bob can't choose position $$$i$$$ outside of the array (that is, smaller than $$$1$$$ or greater than $$$n$$$).

Alice will be the happiest when the elements of the array are as big as possible. Bob claimed that the arithmetic mean value of the elements will work fine as a metric.

What is the maximum arithmetic mean value Bob can achieve?

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — the number of elements of the array and the number of changes.

Each of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$d_i$$$ ($$$-10^3 \le x_i, d_i \le 10^3$$$) — the parameters for the $$$i$$$-th change.

## Output Format
Print the maximal average arithmetic mean of the elements Bob can achieve.

Your answer is considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$.

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

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
Let's call an undirected graph $$$G = (V, E)$$$ relatively prime if and only if for each edge $$$(v, u) \in E$$$  $$$GCD(v, u) = 1$$$ (the greatest common divisor of $$$v$$$ and $$$u$$$ is $$$1$$$). If there is no edge between some pair of vertices $$$v$$$ and $$$u$$$ then the value of $$$GCD(v, u)$$$ doesn't matter. The vertices are numbered from $$$1$$$ to $$$|V|$$$.

Construct a relatively prime graph with $$$n$$$ vertices and $$$m$$$ edges such that it is connected and it contains neither self-loops nor multiple edges.

If there exists no valid graph with the given number of vertices and edges then output "Impossible".

If there are multiple answers then print any of them.

## Input Format
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — the number of vertices and the number of edges.

## Output Format
If there exists no valid graph with the given number of vertices and edges then output "Impossible".

Otherwise print the answer in the following format:

The first line should contain the word "Possible".

The $$$i$$$-th of the next $$$m$$$ lines should contain the $$$i$$$-th edge $$$(v_i, u_i)$$$ of the resulting graph ($$$1 \le v_i, u_i \le n, v_i \neq u_i$$$). For each pair $$$(v, u)$$$ there can be no more pairs $$$(v, u)$$$ or $$$(u, v)$$$. The vertices are numbered from $$$1$$$ to $$$n$$$.

If there are multiple answers then print any of them.

## Examples
```input
5 6
```
```output
Possible
2 5
3 2
5 1
3 4
4 1
5 4
```
-----
```input
6 12
```
```output
Impossible
```

## Note
Here is the representation of the graph from the first 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp has just launched his new startup idea. The niche is pretty free and the key vector of development sounds really promising, so he easily found himself some investors ready to sponsor the company. However, he is yet to name the startup!

Actually, Polycarp has already came up with the name but some improvement to it will never hurt. So now he wants to swap letters at some positions in it to obtain the better name. It isn't necessary for letters to be adjacent.

In addition, each of the investors has chosen some index in the name and selected a set of letters that can go there. Indices chosen by different investors are pairwise distinct. If some indices aren't chosen by any investor then any letter can go there.

Finally, Polycarp is sure that the smallest lexicographically name is the best. (Like why do you think Google decided to become Alphabet?)

More formally, you are given a string consisting of lowercase Latin letters from "a" to "f". You can swap letters at any positions arbitrary number of times (zero swaps is also possible).

What is the smallest lexicographically name you can obtain such that the letter at every position is among the allowed letters?

If Polycarp can't produce any valid name then print "Impossible".

## Input Format
The first line is the string $$$s$$$ ($$$1 \le |s| \le 10^5$$$) — the name Polycarp has came up with. The string consists only of lowercase Latin letters from "a" to "f".

The second line contains a single integer $$$m$$$ ($$$0 \le m \le |s|$$$) — the number of investors.

The $$$i$$$-th of the next $$$m$$$ lines contain an integer number $$$pos_i$$$ and a non-empty string of allowed characters for $$$pos_i$$$ ($$$1 \le pos_i \le |s|$$$). Each string contains pairwise distinct letters from "a" to "f". $$$pos_1, pos_2, \dots, pos_m$$$ are pairwise distinct. If any position of the string doesn't appear in the investors demands then any letter can go in this position.

## Output Format
If Polycarp can't produce any valid name then print "Impossible".

Otherwise print the smallest lexicographically name Polycarp can obtain by swapping letters in string $$$s$$$ such that the letter at every position is among the allowed ones.

## Examples
```input
bedefead
5
2 e
1 dc
5 b
7 ef
6 ef
```
```output
deadbeef
```
-----
```input
abacaba
0
```
```output
aaaabbc
```
-----
```input
fc
2
1 cfab
2 f
```
```output
cf
```

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
Natasha is planning an expedition to Mars for $$$n$$$ people. One of the important tasks is to provide food for each participant.

The warehouse has $$$m$$$ daily food packages. Each package has some food type $$$a_i$$$.

Each participant must eat exactly one food package each day. Due to extreme loads, each participant must eat the same food type throughout the expedition. Different participants may eat different (or the same) types of food.

Formally, for each participant $$$j$$$ Natasha should select his food type $$$b_j$$$ and each day $$$j$$$-th participant will eat one food package of type $$$b_j$$$. The values $$$b_j$$$ for different participants may be different.

What is the maximum possible number of days the expedition can last, following the requirements above?

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 100$$$) — the number of the expedition participants and the number of the daily food packages available.

The second line contains sequence of integers $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le 100$$$), where $$$a_i$$$ is the type of $$$i$$$-th food package.

## Output Format
Print the single integer — the number of days the expedition can last. If it is not possible to plan the expedition for even one day, print 0.

## Examples
```input
4 10
1 5 2 1 1 1 2 5 7 2
```
```output
2
```
-----
```input
100 1
1
```
```output
0
```
-----
```input
2 5
5 4 3 2 1
```
```output
1
```
-----
```input
3 9
42 42 42 42 42 42 42 42 42
```
```output
3
```

## Note
In the first example, Natasha can assign type $$$1$$$ food to the first participant, the same type $$$1$$$ to the second, type $$$5$$$ to the third and type $$$2$$$ to the fourth. In this case, the expedition can last for $$$2$$$ days, since each participant can get two food packages of his food type (there will be used $$$4$$$ packages of type $$$1$$$, two packages of type $$$2$$$ and two packages of type $$$5$$$).

In the second example, there are $$$100$$$ participants and only $$$1$$$ food package. In this case, the expedition can't last even $$$1$$$ day.

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
In Summer Informatics School, if a student doesn't behave well, teachers make a hole in his badge. And today one of the teachers caught a group of $$$n$$$ students doing yet another trick.

Let's assume that all these students are numbered from $$$1$$$ to $$$n$$$. The teacher came to student $$$a$$$ and put a hole in his badge. The student, however, claimed that the main culprit is some other student $$$p_a$$$.

After that, the teacher came to student $$$p_a$$$ and made a hole in his badge as well. The student in reply said that the main culprit was student $$$p_{p_a}$$$.

This process went on for a while, but, since the number of students was finite, eventually the teacher came to the student, who already had a hole in his badge.

After that, the teacher put a second hole in the student's badge and decided that he is done with this process, and went to the sauna.

You don't know the first student who was caught by the teacher. However, you know all the numbers $$$p_i$$$. Your task is to find out for every student $$$a$$$, who would be the student with two holes in the badge if the first caught student was $$$a$$$.

## Input Format
The first line of the input contains the only integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of the naughty students.

The second line contains $$$n$$$ integers $$$p_1$$$, ..., $$$p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ indicates the student who was reported to the teacher by student $$$i$$$.

## Output Format
For every student $$$a$$$ from $$$1$$$ to $$$n$$$ print which student would receive two holes in the badge, if $$$a$$$ was the first student caught by the teacher.

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

## Note
The picture corresponds to the first example test case.

When $$$a = 1$$$, the teacher comes to students $$$1$$$, $$$2$$$, $$$3$$$, $$$2$$$, in this order, and the student $$$2$$$ is the one who receives a second hole in his badge.

When $$$a = 2$$$, the teacher comes to students $$$2$$$, $$$3$$$, $$$2$$$, and the student $$$2$$$ gets a second hole in his badge. When $$$a = 3$$$, the teacher will visit students $$$3$$$, $$$2$$$, $$$3$$$ with student $$$3$$$ getting a second hole in his badge.

For the second example test case it's clear that no matter with whom the teacher starts, that student would be the one who gets the second hole in his badge.

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 a string $$$s$$$ of length $$$n$$$, which consists only of the first $$$k$$$ letters of the Latin alphabet. All letters in string $$$s$$$ are uppercase.

A subsequence of string $$$s$$$ is a string that can be derived from $$$s$$$ by deleting some of its symbols without changing the order of the remaining symbols. For example, "ADE" and "BD" are subsequences of "ABCDE", but "DEA" is not.

A subsequence of $$$s$$$ called good if the number of occurences of each of the first $$$k$$$ letters of the alphabet is the same.

Find the length of the longest good subsequence of $$$s$$$.

## Input Format
The first line of the input contains integers $$$n$$$ ($$$1\le n \le 10^5$$$) and $$$k$$$ ($$$1 \le k \le 26$$$).

The second line of the input contains the string $$$s$$$ of length $$$n$$$. String $$$s$$$ only contains uppercase letters from 'A' to the $$$k$$$-th letter of Latin alphabet.

## Output Format
Print the only integer — the length of the longest good subsequence of string $$$s$$$.

## Examples
```input
9 3
ACAABCCAB
```
```output
6
```
-----
```input
9 4
ABCABCABC
```
```output
0
```

## Note
In the first example, "ACBCAB" ("ACAABCCAB") is one of the subsequences that has the same frequency of 'A', 'B' and 'C'. Subsequence "CAB" also has the same frequency of these letters, but doesn't have the maximum possible length.

In the second example, none of the subsequences can have 'D', hence the answer is $$$0$$$.

Now solve the problem and return the code.