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 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
In a new version of the famous Pinball game, one of the most important parts of the game field is a sequence of n bumpers. The bumpers are numbered with integers from 1 to n from left to right. There are two types of bumpers. They are denoted by the characters '<' and '>'. When the ball hits the bumper at position i it goes one position to the right (to the position i + 1) if the type of this bumper is '>', or one position to the left (to i - 1) if the type of the bumper at position i is '<'. If there is no such position, in other words if i - 1 < 1 or i + 1 > n, the ball falls from the game field.

Depending on the ball's starting position, the ball may eventually fall from the game field or it may stay there forever. You are given a string representing the bumpers' types. Calculate the number of positions such that the ball will eventually fall from the game field if it starts at that position.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the sequence of bumpers. The second line contains the string, which consists of the characters '<' and '>'. The character at the i-th position of this string corresponds to the type of the i-th bumper.

## Output Format
Print one integer — the number of positions in the sequence such that the ball will eventually fall from the game field if it starts at that position.

## Examples
```input
4
<<><
```
```output
2
```
-----
```input
5
>>>>>
```
```output
5
```
-----
```input
4
>><<
```
```output
0
```

## Note
In the first sample, the ball will fall from the field if starts at position 1 or position 2.

In the second sample, any starting position will result in the ball falling from the field.

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 define a grid to be a set of tiles with 2 rows and 13 columns. Each tile has an English letter written in it. The letters don't have to be unique: there might be two or more tiles with the same letter written on them. Here is an example of a grid:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

We say that two tiles are adjacent if they share a side or a corner. In the example grid above, the tile with the letter 'A' is adjacent only to the tiles with letters 'B', 'N', and 'O'. A tile is not adjacent to itself.

A sequence of tiles is called a path if each tile in the sequence is adjacent to the tile which follows it (except for the last tile in the sequence, which of course has no successor). In this example, "ABC" is a path, and so is "KXWIHIJK". "MAB" is not a path because 'M' is not adjacent to 'A'. A single tile can be used more than once by a path (though the tile cannot occupy two consecutive places in the path because no tile is adjacent to itself).

You’re given a string s which consists of 27 upper-case English letters. Each English letter occurs at least once in s. Find a grid that contains a path whose tiles, viewed in the order that the path visits them, form the string s. If there’s no solution, print "Impossible" (without the quotes).

## Input Format
The only line of the input contains the string s, consisting of 27 upper-case English letters. Each English letter occurs at least once in s.

## Output Format
Output two lines, each consisting of 13 upper-case English characters, representing the rows of the grid. If there are multiple solutions, print any of them. If there is no solution print "Impossible".

## Examples
```input
ABCDEFGHIJKLMNOPQRSGTUVWXYZ
```
```output
YXWVUTGHIJKLM
ZABCDEFSRQPON
```
-----
```input
BUVTYZFQSNRIWOXXGJLKACPEMDH
```
```output
Impossible
```

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 and Bonnie are sisters, but they don't like each other very much. So when some old family photos were found in the attic, they started to argue about who should receive which photos. In the end, they decided that they would take turns picking photos. Alice goes first.

There are n stacks of photos. Each stack contains exactly two photos. In each turn, a player may take only a photo from the top of one of the stacks.

Each photo is described by two non-negative integers a and b, indicating that it is worth a units of happiness to Alice and b units of happiness to Bonnie. Values of a and b might differ for different photos.

It's allowed to pass instead of taking a photo. The game ends when all photos are taken or both players pass consecutively.

The players don't act to maximize their own happiness. Instead, each player acts to maximize the amount by which her happiness exceeds her sister's. Assuming both players play optimal, find the difference between Alice's and Bonnie's happiness. That is, if there's a perfectly-played game such that Alice has x happiness and Bonnie has y happiness at the end, you should print x - y.

## Input Format
The first line of input contains a single integer n (1 ≤ n ≤ 100 000) — the number of two-photo stacks. Then follow n lines, each describing one of the stacks. A stack is described by four space-separated non-negative integers a1, b1, a2 and b2, each not exceeding 109. a1 and b1 describe the top photo in the stack, while a2 and b2 describe the bottom photo in the stack.

## Output Format
Output a single integer: the difference between Alice's and Bonnie's happiness if both play optimally.

## Examples
```input
2
12 3 4 7
1 15 9 1
```
```output
1
```
-----
```input
2
5 4 8 8
4 12 14 0
```
```output
4
```
-----
```input
1
0 10 0 10
```
```output
-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 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
Chloe, the same as Vladik, is a competitive programmer. She didn't have any problems to get to the olympiad like Vladik, but she was confused by the task proposed on the olympiad.

Let's consider the following algorithm of generating a sequence of integers. Initially we have a sequence consisting of a single element equal to 1. Then we perform (n - 1) steps. On each step we take the sequence we've got on the previous step, append it to the end of itself and insert in the middle the minimum positive integer we haven't used before. For example, we get the sequence [1, 2, 1] after the first step, the sequence [1, 2, 1, 3, 1, 2, 1] after the second step.

The task is to find the value of the element with index k (the elements are numbered from 1) in the obtained sequence, i. e. after (n - 1) steps.

Please help Chloe to solve the problem!

## Input Format
The only line contains two integers n and k (1 ≤ n ≤ 50, 1 ≤ k ≤ 2n - 1).

## Output Format
Print single integer — the integer at the k-th position in the obtained sequence.

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

## Note
In the first sample the obtained sequence is [1, 2, 1, 3, 1, 2, 1]. The number on the second position is 2.

In the second sample the obtained sequence is [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]. The number on the eighth position is 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 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
Vladik was bored on his way home and decided to play the following game. He took n cards and put them in a row in front of himself. Every card has a positive integer number not exceeding 8 written on it. He decided to find the longest subsequence of cards which satisfies the following conditions:

- the number of occurrences of each number from 1 to 8 in the subsequence doesn't differ by more then 1 from the number of occurrences of any other number. Formally, if there are ck cards with number k on them in the subsequence, than for all pairs of integers $$i \in [1,8], j \in [1,8]$$ the condition |ci - cj| ≤ 1 must hold.
- if there is at least one card with number x on it in the subsequence, then all cards with number x in this subsequence must form a continuous segment in it (but not necessarily a continuous segment in the original sequence). For example, the subsequence [1, 1, 2, 2] satisfies this condition while the subsequence [1, 2, 2, 1] doesn't. Note that [1, 1, 2, 2] doesn't satisfy the first condition.

Please help Vladik to find the length of the longest subsequence that satisfies both conditions.

## Input Format
The first line contains single integer n (1 ≤ n ≤ 1000) — the number of cards in Vladik's sequence.

The second line contains the sequence of n positive integers not exceeding 8 — the description of Vladik's sequence.

## Output Format
Print single integer — the length of the longest subsequence of Vladik's sequence that satisfies both conditions.

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

## Note
In the first sample all the numbers written on the cards are equal, so you can't take more than one card, otherwise you'll violate the first condition.

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
Mahmoud has n line segments, the i-th of them has length ai. Ehab challenged him to use exactly 3 line segments to form a non-degenerate triangle. Mahmoud doesn't accept challenges unless he is sure he can win, so he asked you to tell him if he should accept the challenge. Given the lengths of the line segments, check if he can choose exactly 3 of them to form a non-degenerate triangle.

Mahmoud should use exactly 3 line segments, he can't concatenate two line segments or change any length. A non-degenerate triangle is a triangle with positive area.

## Input Format
The first line contains single integer n (3 ≤ n ≤ 105) — the number of line segments Mahmoud has.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the lengths of line segments Mahmoud has.

## Output Format
In the only line print "YES" if he can choose exactly three line segments and form a non-degenerate triangle with them, and "NO" otherwise.

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

## Note
For the first example, he can use line segments with lengths 2, 4 and 5 to form a non-degenerate triangle.

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
A monster is chasing after Rick and Morty on another planet. They're so frightened that sometimes they scream. More accurately, Rick screams at times b, b + a, b + 2a, b + 3a, ... and Morty screams at times d, d + c, d + 2c, d + 3c, ....

The Monster will catch them if at any point they scream at the same time, so it wants to know when it will catch them (the first time they scream at the same time) or that they will never scream at the same time.

## Input Format
The first line of input contains two integers a and b (1 ≤ a, b ≤ 100).

The second line contains two integers c and d (1 ≤ c, d ≤ 100).

## Output Format
Print the first time Rick and Morty will scream at the same time, or  - 1 if they will never scream at the same time.

## Examples
```input
20 2
9 19
```
```output
82
```
-----
```input
2 1
16 12
```
```output
-1
```

## Note
In the first sample testcase, Rick's 5th scream and Morty's 8th time are at time 82.

In the second sample testcase, all Rick's screams will be at odd times and Morty's will be at even times, so they will never scream at the same time.

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
Since the giant heads have appeared in the sky all humanity is in danger, so all Ricks and Mortys from all parallel universes are gathering in groups to find a solution to get rid of them.

There are n parallel universes participating in this event (n Ricks and n Mortys). I. e. each of n universes has one Rick and one Morty. They're gathering in m groups. Each person can be in many groups and a group can contain an arbitrary number of members.

Ricks and Mortys have registered online in these groups. So, a person can have joined a group more than once (developer of this website hadn't considered this possibility).

Summer from universe #1 knows that in each parallel universe (including hers) exactly one of Rick and Morty from that universe is a traitor and is loyal, but no one knows which one. She knows that we are doomed if there's a group such that every member in that group is a traitor (they will plan and destroy the world).

Summer knows that if there's a possibility that world ends (there's a group where all members are traitors) she should immediately cancel this event. So she wants to know if she should cancel the event. You have to tell her yes if and only if there's at least one scenario (among all 2n possible scenarios, 2 possible scenarios for who a traitor in each universe) such that in that scenario the world will end.

## Input Format
The first line of input contains two integers n and m (1 ≤ n, m ≤ 104) — number of universes and number of groups respectively.

The next m lines contain the information about the groups. i-th of them first contains an integer k (number of times someone joined i-th group, k > 0) followed by k integers vi, 1, vi, 2, ..., vi, k. If vi, j is negative, it means that Rick from universe number  - vi, j has joined this group and otherwise it means that Morty from universe number vi, j has joined it.

Sum of k for all groups does not exceed 104.

## Output Format
In a single line print the answer to Summer's question. Print "YES" if she should cancel the event and "NO" otherwise.

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

## Note
In the first sample testcase, 1st group only contains the Rick from universe number 3, so in case he's a traitor, then all members of this group are traitors and so Summer should cancel the event.

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
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 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
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.