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: 0.5 seconds
Memory limit: 256.0 MB

# Problem
The Fire Lord attacked the Frost Kingdom. He has already got to the Ice Fortress, where the Snow Queen dwells. He arranged his army on a segment n in length not far from the city walls. And only the frost magician Solomon can save the Frost Kingdom.

The n-long segment is located at a distance equal exactly to 1 from the castle walls. It can be imaginarily divided into unit segments. On some of the unit segments fire demons are located — no more than one demon per position. Each demon is characterised by his strength - by some positive integer. We can regard the fire demons being idle.

Initially Solomon is positioned on the fortress wall. He can perform the following actions several times in a row:

- "L" — Solomon shifts one unit to the left. This movement cannot be performed on the castle wall.
- "R" — Solomon shifts one unit to the left. This movement cannot be performed if there's no ice block to the right.
- "A" — If there's nothing to the right of Solomon, then Solomon creates an ice block that immediately freezes to the block that Solomon is currently standing on. If there already is an ice block, then Solomon destroys it. At that the ice blocks to the right of the destroyed one can remain but they are left unsupported. Those ice blocks fall down.

Solomon spends exactly a second on each of these actions.

As the result of Solomon's actions, ice blocks' segments fall down. When an ice block falls on a fire demon, the block evaporates and the demon's strength is reduced by 1. When the demons' strength is equal to 0, the fire demon vanishes. The picture below shows how it happens. The ice block that falls on the position with no demon, breaks into lots of tiny pieces and vanishes without hurting anybody.

Help Solomon destroy all the Fire Lord's army in minimum time.

## Input Format
The first line contains an integer n (1 ≤ n ≤ 1000). The next line contains n numbers, the i-th of them represents the strength of the fire demon standing of the i-th position, an integer from 1 to 100. If there's no demon on the i-th position, then the i-th number equals to 0. It is guaranteed that the input data have at least one fire demon.

## Output Format
Print a string of minimum length, containing characters "L", "R" and "A" — the succession of actions leading to the required result.

If there are several possible answers, print any of them.

## Examples
```input
3
1 0 1
```
```output
ARARARALLLA
```
-----
```input
3
0 2 0
```
```output
ARARALAARALA
```

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
Alex, Bob and Carl will soon participate in a team chess tournament. Since they are all in the same team, they have decided to practise really hard before the tournament. But it's a bit difficult for them because chess is a game for two players, not three.

So they play with each other according to following rules:

- Alex and Bob play the first game, and Carl is spectating;
- When the game ends, the one who lost the game becomes the spectator in the next game, and the one who was spectating plays against the winner.

Alex, Bob and Carl play in such a way that there are no draws.

Today they have played n games, and for each of these games they remember who was the winner. They decided to make up a log of games describing who won each game. But now they doubt if the information in the log is correct, and they want to know if the situation described in the log they made up was possible (that is, no game is won by someone who is spectating if Alex, Bob and Carl play according to the rules). Help them to check it!

## Input Format
The first line contains one integer n (1 ≤ n ≤ 100) — the number of games Alex, Bob and Carl played.

Then n lines follow, describing the game log. i-th line contains one integer ai (1 ≤ ai ≤ 3) which is equal to 1 if Alex won i-th game, to 2 if Bob won i-th game and 3 if Carl won i-th game.

## Output Format
Print YES if the situation described in the log was possible. Otherwise print NO.

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

## Note
In the first example the possible situation is:

1. Alex wins, Carl starts playing instead of Bob;
2. Alex wins, Bob replaces Carl;
3. Bob wins.

The situation in the second example is impossible because Bob loses the first game, so he cannot win the second one.

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
Recently Luba learned about a special kind of numbers that she calls beautiful numbers. The number is called beautiful iff its binary representation consists of k + 1 consecutive ones, and then k consecutive zeroes.

Some examples of beautiful numbers:

- 12 (110);
- 1102 (610);
- 11110002 (12010);
- 1111100002 (49610).

More formally, the number is beautiful iff there exists some positive integer k such that the number is equal to (2k - 1) * (2k - 1).

Luba has got an integer number n, and she wants to find its greatest beautiful divisor. Help her to find it!

## Input Format
The only line of input contains one number n (1 ≤ n ≤ 105) — the number Luba has got.

## Output Format
Output one number — the greatest beautiful divisor of Luba's number. It is obvious that the answer always exists.

## Examples
```input
3
```
```output
1
```
-----
```input
992
```
```output
496
```

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
Vova promised himself that he would never play computer games... But recently Firestorm — a well-known game developing company — published their newest game, World of Farcraft, and it became really popular. Of course, Vova started playing it.

Now he tries to solve a quest. The task is to come to a settlement named Overcity and spread a rumor in it.

Vova knows that there are n characters in Overcity. Some characters are friends to each other, and they share information they got. Also Vova knows that he can bribe each character so he or she starts spreading the rumor; i-th character wants ci gold in exchange for spreading the rumor. When a character hears the rumor, he tells it to all his friends, and they start spreading the rumor to their friends (for free), and so on.

The quest is finished when all n characters know the rumor. What is the minimum amount of gold Vova needs to spend in order to finish the quest?

Take a look at the notes if you think you haven't understood the problem completely.

## Input Format
The first line contains two integer numbers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — the number of characters in Overcity and the number of pairs of friends.

The second line contains n integer numbers ci (0 ≤ ci ≤ 109) — the amount of gold i-th character asks to start spreading the rumor.

Then m lines follow, each containing a pair of numbers (xi, yi) which represent that characters xi and yi are friends (1 ≤ xi, yi ≤ n, xi ≠ yi). It is guaranteed that each pair is listed at most once.

## Output Format
Print one number — the minimum amount of gold Vova has to spend in order to finish the quest.

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

## Note
In the first example the best decision is to bribe the first character (he will spread the rumor to fourth character, and the fourth one will spread it to fifth). Also Vova has to bribe the second and the third characters, so they know the rumor.

In the second example Vova has to bribe everyone.

In the third example the optimal decision is to bribe the first, the third, the fifth, the seventh and the ninth characters.

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
Recenlty Luba got a credit card and started to use it. Let's consider n consecutive days Luba uses the card.

She starts with 0 money on her account.

In the evening of i-th day a transaction ai occurs. If ai > 0, then ai bourles are deposited to Luba's account. If ai < 0, then ai bourles are withdrawn. And if ai = 0, then the amount of money on Luba's account is checked.

In the morning of any of n days Luba can go to the bank and deposit any positive integer amount of burles to her account. But there is a limitation: the amount of money on the account can never exceed d.

It can happen that the amount of money goes greater than d by some transaction in the evening. In this case answer will be «-1».

Luba must not exceed this limit, and also she wants that every day her account is checked (the days when ai = 0) the amount of money on her account is non-negative. It takes a lot of time to go to the bank, so Luba wants to know the minimum number of days she needs to deposit some money to her account (if it is possible to meet all the requirements). Help her!

## Input Format
The first line contains two integers n, d (1 ≤ n ≤ 105, 1 ≤ d ≤ 109) —the number of days and the money limitation.

The second line contains n integer numbers a1, a2, ... an ( - 104 ≤ ai ≤ 104), where ai represents the transaction in i-th day.

## Output Format
Print -1 if Luba cannot deposit the money to her account in such a way that the requirements are met. Otherwise print the minimum number of days Luba has to deposit money.

## Examples
```input
5 10
-1 5 0 -5 3
```
```output
0
```
-----
```input
3 4
-10 0 20
```
```output
-1
```
-----
```input
5 10
-5 0 10 -11 0
```
```output
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 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 rooted tree with n vertices. The vertices are numbered from 1 to n, the root is the vertex number 1.

Each vertex has a color, let's denote the color of vertex v by cv. Initially cv = 0.

You have to color the tree into the given colors using the smallest possible number of steps. On each step you can choose a vertex v and a color x, and then color all vectices in the subtree of v (including v itself) in color x. In other words, for every vertex u, such that the path from root to u passes through v, set cu = x.

It is guaranteed that you have to color each vertex in a color different from 0.

You can learn what a rooted tree is using the link: https://en.wikipedia.org/wiki/Tree_(graph_theory).

## Input Format
The first line contains a single integer n (2 ≤ n ≤ 104) — the number of vertices in the tree.

The second line contains n - 1 integers p2, p3, ..., pn (1 ≤ pi < i), where pi means that there is an edge between vertices i and pi.

The third line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ n), where ci is the color you should color the i-th vertex into.

It is guaranteed that the given graph is a tree.

## Output Format
Print a single integer — the minimum number of steps you have to perform to color the tree into given colors.

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

## Note
The tree from the first sample is shown on the picture (numbers are vetices' indices):

On first step we color all vertices in the subtree of vertex 1 into color 2 (numbers are colors):

On seond step we color all vertices in the subtree of vertex 5 into color 1:

On third step we color all vertices in the subtree of vertex 2 into color 1:

The tree from the second sample is shown on the picture (numbers are vetices' indices):

On first step we color all vertices in the subtree of vertex 1 into color 3 (numbers are colors):

On second step we color all vertices in the subtree of vertex 3 into color 1:

On third step we color all vertices in the subtree of vertex 6 into color 2:

On fourth step we color all vertices in the subtree of vertex 4 into color 1:

On fith step we color all vertices in the subtree of vertex 7 into color 3:

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Hurricane came to Berland and to suburbs Stringsvill. You are going to it to check if it's all right with you favorite string. Hurrinace broke it a bit by reversing some of its non-intersecting substrings. You have a photo of this string before hurricane and you want to restore it to original state using reversing minimum possible number of its substrings and find out which substrings you should reverse.

You are given a string s — original state of your string and string t — state of the string after hurricane. You should select k non-intersecting substrings of t in such a way that after reverse of these substrings string will be equal s and k is minimum possible.

## Input Format
First line of input contains string s and second line contains string t. Both strings have same length and consist of lowercase English letters. 1 ≤ |s| = |t| ≤ 5·105

## Output Format
In first line print k — minimum number of substrings you should reverse. Next output k lines. Each line should contain two integers li, ri meaning that you should reverse substring from symbol number li to symbol ri (strings are 1-indexed). These substrings shouldn't intersect. If there are multiple answers print any. If it's impossible to restore string output -1.

## Examples
```input
abcxxxdef
cbaxxxfed
```
```output
2
7 9
1 3
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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
Yesterday was a fair in a supermarket's grocery section. There were n jars with spices on the fair. Before the event the jars were numbered from 1 to n from the left to the right. After the event the jars were moved and the grocer had to sort them by the increasing of the numbers.

The grocer has a special machine at his disposal. The machine can take any 5 or less jars and rearrange them in the way the grocer wants. Note that the jars do not have to stand consecutively. For example, from the permutation 2, 6, 5, 4, 3, 1 one can get permutation 1, 2, 3, 4, 5, 6, if pick the jars on the positions 1, 2, 3, 5 and 6.

Which minimum number of such operations is needed to arrange all the jars in the order of their numbers' increasing?

## Input Format
The first line contains an integer n (1 ≤ n ≤ 105). The second line contains n space-separated integers ai (1 ≤ ai ≤ n) — the i-th number represents the number of a jar that occupies the i-th position. It is guaranteed that all the numbers are distinct.

## Output Format
Print on the first line the least number of operations needed to rearrange all the jars in the order of the numbers' increasing. Then print the description of all actions in the following format.

On the first line of the description of one action indicate the number of jars that need to be taken (k), on the second line indicate from which positions the jars need to be taken (b1, b2, ..., bk), on the third line indicate the jar's new order (c1, c2, ..., ck). After the operation is fulfilled the jar from position bi will occupy the position ci. The set (c1, c2, ..., ck) should be the rearrangement of the set (b1, b2, ..., bk).

If there are multiple solutions, output any.

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

## Note
Let's consider the first sample. The jars can be sorted within two actions.

During the first action we take the jars from positions 1, 3, 6 and 4 and put them so that the jar that used to occupy the position 1 will occupy the position 3 after the operation is completed. The jar from position 3 will end up in position 6, the jar from position 6 will end up in position 4 and the jar from position 4 will end up in position 1.

After the first action the order will look like that: 1, 5, 3, 4, 2, 6.

During the second operation the jars in positions 2 and 5 will change places.

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
East or west, home is best. That's why family reunion, the indispensable necessity of Lunar New Year celebration, is put in such a position.

After the reunion dinner, Little Tommy plays a game with the family. Here is a concise introduction to this game:

1. There is a sequence of n non-negative integers p1, p2, ..., pn in the beginning. It is ruled that each integer in this sequence should be non-negative at any time.
2. You can select two consecutive positive integers in this sequence, pi and pi + 1 (1 ≤ i < n), and then decrease them by their minimum (i. e. min(pi, pi + 1)), the cost of this operation is equal to min(pi, pi + 1). We call such operation as a descension.
3. The game immediately ends when there are no two consecutive positive integers. Your task is to end the game so that the total cost of your operations is as small as possible.

Obviously, every game ends after at most n - 1 descensions. Please share your solution of this game with the lowest cost.

## Input Format
The first line contains one integer n (1 ≤ n ≤ 3·105).

The second line contains n space-separated integers p1, p2, ..., pn (0 ≤ pi ≤ 109, i = 1, 2, ..., n).

## Output Format
In the first line print one integer as the number of descensions m (0 ≤ m ≤ n - 1).

In the next m lines print the descensions chronologically. More precisely, in each line of the next m lines print one integer i (1 ≤ i < n) representing a descension would operate on pi and pi + 1 such that all the descensions could be utilized from top to bottom.

If there are many possible solutions to reach the minimal cost, print any of them.

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

## Note
In the first sample, one possible best solution is $$\begin{bmatrix}
2 & 1 & 3 & 1
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 0 & 3 & 1
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 0 & 2 & 0
\end{bmatrix}$$, of which the cost is 1 + 1 = 2.

In the second sample, one possible best solution is $$\begin{bmatrix}
2 & 2 & 1 & 3 & 1
\end{bmatrix}
\rightarrow
\begin{bmatrix}
2 & 1 & 0 & 3 & 1
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 0 & 0 & 3 & 1
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 0 & 0 & 2 & 0
\end{bmatrix}$$, of which the cost is 1 + 1 + 1 = 3.

Now solve the problem and return the code.