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
There are n students in Polycarp's class (including himself). A few days ago all students wrote an essay "My best friend". Each student's essay was dedicated to one of the students of class, to his/her best friend. Note that student b's best friend is not necessarily student a, if a's best friend is b.

And now the teacher leads the whole class to the museum of the history of sports programming. Exciting stories of legendary heroes await the students: tourist, Petr, tomek, SnapDragon — that's who they will hear about!

The teacher decided to divide students into pairs so that each pair consisted of a student and his best friend. She may not be able to split all the students into pairs, it's not a problem — she wants to pick out the maximum number of such pairs. If there is more than one variant of doing so, she wants to pick out the pairs so that there were as much boy-girl pairs as possible. Of course, each student must not be included in more than one pair.

## Input Format
The first line contains an integer n (2 ≤ n ≤ 105), n is the number of students per class. Next, n lines contain information about the students, one per line. Each line contains two integers fi, si (1 ≤ fi ≤ n, fi ≠ i, 1 ≤ si ≤ 2), where fi is the number of i-th student's best friend and si denotes the i-th pupil's sex (si = 1 for a boy and si = 2 for a girl).

## Output Format
Print on the first line two numbers t, e, where t is the maximum number of formed pairs, and e is the maximum number of boy-girl type pairs among them. Then print t lines, each line must contain a pair ai, bi (1 ≤ ai, bi ≤ n), they are numbers of pupils in the i-th pair. Print the pairs in any order. Print the numbers in pairs in any order. If there are several solutions, output any of them.

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

## Note
The picture corresponds to the first sample. On the picture rhomb stand for boys, squares stand for girls, arrows lead from a pupil to his/her best friend. Bold non-dashed arrows stand for pairs in the answer.

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 few years ago, Hitagi encountered a giant crab, who stole the whole of her body weight. Ever since, she tried to avoid contact with others, for fear that this secret might be noticed.

To get rid of the oddity and recover her weight, a special integer sequence is needed. Hitagi's sequence has been broken for a long time, but now Kaiki provides an opportunity.

Hitagi's sequence a has a length of n. Lost elements in it are denoted by zeros. Kaiki provides another sequence b, whose length k equals the number of lost elements in a (i.e. the number of zeros). Hitagi is to replace each zero in a with an element from b so that each element in b should be used exactly once. Hitagi knows, however, that, apart from 0, no integer occurs in a and b more than once in total.

If the resulting sequence is not an increasing sequence, then it has the power to recover Hitagi from the oddity. You are to determine whether this is possible, or Kaiki's sequence is just another fake. In other words, you should detect whether it is possible to replace each zero in a with an integer from b so that each integer from b is used exactly once, and the resulting sequence is not increasing.

## Input Format
The first line of input contains two space-separated positive integers n (2 ≤ n ≤ 100) and k (1 ≤ k ≤ n) — the lengths of sequence a and b respectively.

The second line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 200) — Hitagi's broken sequence with exactly k zero elements.

The third line contains k space-separated integers b1, b2, ..., bk (1 ≤ bi ≤ 200) — the elements to fill into Hitagi's sequence.

Input guarantees that apart from 0, no integer occurs in a and b more than once in total.

## Output Format
Output "Yes" if it's possible to replace zeros in a with elements in b and make the resulting sequence not increasing, and "No" otherwise.

## Examples
```input
4 2
11 0 0 14
5 4
```
```output
Yes
```
-----
```input
6 1
2 3 0 8 9 10
5
```
```output
No
```
-----
```input
4 1
8 94 0 4
89
```
```output
Yes
```
-----
```input
7 7
0 0 0 0 0 0 0
1 2 3 4 5 6 7
```
```output
Yes
```

## Note
In the first sample:

- Sequence a is 11, 0, 0, 14.
- Two of the elements are lost, and the candidates in b are 5 and 4.
- There are two possible resulting sequences: 11, 5, 4, 14 and 11, 4, 5, 14, both of which fulfill the requirements. Thus the answer is "Yes".

In the second sample, the only possible resulting sequence is 2, 3, 5, 8, 9, 10, which is an increasing sequence and therefore invalid.

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 crowdedness of the discotheque would never stop our friends from having fun, but a bit more spaciousness won't hurt, will it?

The discotheque can be seen as an infinite xy-plane, in which there are a total of n dancers. Once someone starts moving around, they will move only inside their own movement range, which is a circular area Ci described by a center (xi, yi) and a radius ri. No two ranges' borders have more than one common point, that is for every pair (i, j) (1 ≤ i < j ≤ n) either ranges Ci and Cj are disjoint, or one of them is a subset of the other. Note that it's possible that two ranges' borders share a single common point, but no two dancers have exactly the same ranges.

Tsukihi, being one of them, defines the spaciousness to be the area covered by an odd number of movement ranges of dancers who are moving. An example is shown below, with shaded regions representing the spaciousness if everyone moves at the same time.

But no one keeps moving for the whole night after all, so the whole night's time is divided into two halves — before midnight and after midnight. Every dancer moves around in one half, while sitting down with friends in the other. The spaciousness of two halves are calculated separately and their sum should, of course, be as large as possible. The following figure shows an optimal solution to the example above.

By different plans of who dances in the first half and who does in the other, different sums of spaciousness over two halves are achieved. You are to find the largest achievable value of this sum.

## Input Format
The first line of input contains a positive integer n (1 ≤ n ≤ 1 000) — the number of dancers.

The following n lines each describes a dancer: the i-th line among them contains three space-separated integers xi, yi and ri ( - 106 ≤ xi, yi ≤ 106, 1 ≤ ri ≤ 106), describing a circular movement range centered at (xi, yi) with radius ri.

## Output Format
Output one decimal number — the largest achievable sum of spaciousness over two halves of the night.

The output is considered correct if it has a relative or absolute error of at most 10 - 9. Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $$\frac{|a-b|}{\max(1, |b|)} \leq 10^{-9}$$.

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

## Note
The first sample corresponds to the illustrations in the legend.

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
Those unwilling to return home from a long journey, will be affected by the oddity of the snail and lose their way. Mayoi, the oddity's carrier, wouldn't like this to happen, but there's nothing to do with this before a cure is figured out. For now, she would only like to know the enormous number of possibilities to be faced with if someone gets lost.

There are n towns in the region, numbered from 1 to n. The town numbered 1 is called the capital. The traffic network is formed by bidirectional roads connecting pairs of towns. No two roads connect the same pair of towns, and no road connects a town with itself. The time needed to travel through each of the roads is the same. Lost travelers will not be able to find out how the towns are connected, but the residents can help them by providing the following facts:

- Starting from each town other than the capital, the shortest path (i.e. the path passing through the minimum number of roads) to the capital exists, and is unique;
- Let li be the number of roads on the shortest path from town i to the capital, then li ≥ li - 1 holds for all 2 ≤ i ≤ n;
- For town i, the number of roads connected to it is denoted by di, which equals either 2 or 3.

You are to count the number of different ways in which the towns are connected, and give the answer modulo 109 + 7. Two ways of connecting towns are considered different if a pair (u, v) (1 ≤ u, v ≤ n) exists such there is a road between towns u and v in one of them but not in the other.

## Input Format
The first line of input contains a positive integer n (3 ≤ n ≤ 50) — the number of towns.

The second line contains n space-separated integers d1, d2, ..., dn (2 ≤ di ≤ 3) — the number of roads connected to towns 1, 2, ..., n, respectively. It is guaranteed that the sum of di over all i is even.

## Output Format
Output one integer — the total number of different possible ways in which the towns are connected, modulo 109 + 7.

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

## Note
In the first example, the following structure is the only one to satisfy the constraints, the distances from towns 2, 3, 4 to the capital are all 1.

In the second example, the following two structures satisfy the constraints.

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
There are n students who have taken part in an olympiad. Now it's time to award the students.

Some of them will receive diplomas, some wiil get certificates, and others won't receive anything. Students with diplomas and certificates are called winners. But there are some rules of counting the number of diplomas and certificates. The number of certificates must be exactly k times greater than the number of diplomas. The number of winners must not be greater than half of the number of all students (i.e. not be greater than half of n). It's possible that there are no winners.

You have to identify the maximum possible number of winners, according to these rules. Also for this case you have to calculate the number of students with diplomas, the number of students with certificates and the number of students who are not winners.

## Input Format
The first (and the only) line of input contains two integers n and k (1 ≤ n, k ≤ 1012), where n is the number of students and k is the ratio between the number of certificates and the number of diplomas.

## Output Format
Output three numbers: the number of students with diplomas, the number of students with certificates and the number of students who are not winners in case when the number of winners is maximum possible.

It's possible that there are no winners.

## Examples
```input
18 2
```
```output
3 6 9
```
-----
```input
9 10
```
```output
0 0 9
```
-----
```input
1000000000000 5
```
```output
83333333333 416666666665 500000000002
```
-----
```input
1000000000000 499999999999
```
```output
1 499999999999 500000000000
```

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
n children are standing in a circle and playing a game. Children's numbers in clockwise order form a permutation a1, a2, ..., an of length n. It is an integer sequence such that each integer from 1 to n appears exactly once in it.

The game consists of m steps. On each step the current leader with index i counts out ai people in clockwise order, starting from the next person. The last one to be pointed at by the leader becomes the new leader.

You are given numbers l1, l2, ..., lm — indices of leaders in the beginning of each step. Child with number l1 is the first leader in the game.

Write a program which will restore a possible permutation a1, a2, ..., an. If there are multiple solutions then print any of them. If there is no solution then print -1.

## Input Format
The first line contains two integer numbers n, m (1 ≤ n, m ≤ 100).

The second line contains m integer numbers l1, l2, ..., lm (1 ≤ li ≤ n) — indices of leaders in the beginning of each step.

## Output Format
Print such permutation of n numbers a1, a2, ..., an that leaders in the game will be exactly l1, l2, ..., lm if all the rules are followed. If there are multiple solutions print any of them.

If there is no permutation which satisfies all described conditions print -1.

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

## Note
Let's follow leadership in the first example:

- Child 2 starts.
- Leadership goes from 2 to 2 + a2 = 3.
- Leadership goes from 3 to 3 + a3 = 5. As it's greater than 4, it's going in a circle to 1.
- Leadership goes from 1 to 1 + a1 = 4.
- Leadership goes from 4 to 4 + a4 = 8. Thus in circle it still remains at 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Alice and Bob got very bored during a long car trip so they decided to play a game. From the window they can see cars of different colors running past them. Cars are going one after another.

The game rules are like this. Firstly Alice chooses some color A, then Bob chooses some color B (A ≠ B). After each car they update the number of cars of their chosen color that have run past them. Let's define this numbers after i-th car cntA(i) and cntB(i).

- If cntA(i) > cntB(i) for every i then the winner is Alice.
- If cntB(i) ≥ cntA(i) for every i then the winner is Bob.
- Otherwise it's a draw.

Bob knows all the colors of cars that they will encounter and order of their appearance. Alice have already chosen her color A and Bob now wants to choose such color B that he will win the game (draw is not a win). Help him find this color.

If there are multiple solutions, print any of them. If there is no such color then print -1.

## Input Format
The first line contains two integer numbers n and A (1 ≤ n ≤ 105, 1 ≤ A ≤ 106) – number of cars and the color chosen by Alice.

The second line contains n integer numbers c1, c2, ..., cn (1 ≤ ci ≤ 106) — colors of the cars that Alice and Bob will encounter in the order of their appearance.

## Output Format
Output such color B (1 ≤ B ≤ 106) that if Bob chooses it then he will win the game. If there are multiple solutions, print any of them. If there is no such color then print -1.

It is guaranteed that if there exists any solution then there exists solution with (1 ≤ B ≤ 106).

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

## Note
Let's consider availability of colors in the first example:

- cnt2(i) ≥ cnt1(i) for every i, and color 2 can be the answer.
- cnt4(2) < cnt1(2), so color 4 isn't the winning one for Bob.
- All the other colors also have cntj(2) < cnt1(2), thus they are not available.

In the third example every color is acceptable except for 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vova again tries to play some computer card game.

The rules of deck creation in this game are simple. Vova is given an existing deck of n cards and a magic number k. The order of the cards in the deck is fixed. Each card has a number written on it; number ai is written on the i-th card in the deck.

After receiving the deck and the magic number, Vova removes x (possibly x = 0) cards from the top of the deck, y (possibly y = 0) cards from the bottom of the deck, and the rest of the deck is his new deck (Vova has to leave at least one card in the deck after removing cards). So Vova's new deck actually contains cards x + 1, x + 2, ... n - y - 1, n - y from the original deck.

Vova's new deck is considered valid iff the product of all numbers written on the cards in his new deck is divisible by k. So Vova received a deck (possibly not a valid one) and a number k, and now he wonders, how many ways are there to choose x and y so the deck he will get after removing x cards from the top and y cards from the bottom is valid?

## Input Format
The first line contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the numbers written on the cards.

## Output Format
Print the number of ways to choose x and y so the resulting deck is valid.

## Examples
```input
3 4
6 2 8
```
```output
4
```
-----
```input
3 6
9 1 14
```
```output
1
```

## Note
In the first example the possible values of x and y are:

1. x = 0, y = 0;
2. x = 1, y = 0;
3. x = 2, y = 0;
4. x = 0, y = 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: 5.0 seconds
Memory limit: 1024.0 MB

# Problem
Author note: I think some of you might remember the problem "Two Melodies" from Eductational Codeforces Round 22. Now it's time to make it a bit more difficult!

Alice is a composer, and recently she had recorded two tracks that became very popular. Now she has got a lot of fans who are waiting for new tracks.

This time Alice wants to form four melodies for her tracks.

Alice has a sheet with n notes written on it. She wants to take four such non-empty non-intersecting subsequences that all of them form a melody and sum of their lengths is maximal.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Subsequence forms a melody when each two adjacent notes either differ by 1 or are congruent modulo 7.

You should write a program which will calculate maximum sum of lengths of such four non-empty non-intersecting subsequences that all of them form a melody.

## Input Format
The first line contains one integer number n (4 ≤ n ≤ 3000).

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 105) — notes written on a sheet.

## Output Format
Print maximum sum of lengths of such four non-empty non-intersecting subsequences that all of them form a melody.

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

## Note
In the first example it is possible to compose 4 melodies by choosing any 4 notes (and each melody will consist of only one note).

In the second example it is possible to compose one melody with 2 notes — {1, 2}. Remaining notes are used in other three melodies (one note per each melody).

Now solve the problem and return the code.