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 his spare time Vladik estimates beauty of the flags.

Every flag could be represented as the matrix n × m which consists of positive integers.

Let's define the beauty of the flag as number of components in its matrix. We call component a set of cells with same numbers and between any pair of cells from that set there exists a path through adjacent cells from same component. Here is the example of the partitioning some flag matrix into components:

But this time he decided to change something in the process. Now he wants to estimate not the entire flag, but some segment. Segment of flag can be described as a submatrix of the flag matrix with opposite corners at (1, l) and (n, r), where conditions 1 ≤ l ≤ r ≤ m are satisfied.

Help Vladik to calculate the beauty for some segments of the given flag.

## Input Format
First line contains three space-separated integers n, m, q (1 ≤ n ≤ 10, 1 ≤ m, q ≤ 105) — dimensions of flag matrix and number of segments respectively.

Each of next n lines contains m space-separated integers — description of flag matrix. All elements of flag matrix is positive integers not exceeding 106.

Each of next q lines contains two space-separated integers l, r (1 ≤ l ≤ r ≤ m) — borders of segment which beauty Vladik wants to know.

## Output Format
For each segment print the result on the corresponding line.

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

## Note
Partitioning on components for every segment from first test case:

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
Walking through the streets of Marshmallow City, Slastyona have spotted some merchants selling a kind of useless toy which is very popular nowadays – caramel spinner! Wanting to join the craze, she has immediately bought the strange contraption.

Spinners in Sweetland have the form of V-shaped pieces of caramel. Each spinner can, well, spin around an invisible magic axis. At a specific point in time, a spinner can take 4 positions shown below (each one rotated 90 degrees relative to the previous, with the fourth one followed by the first one):

After the spinner was spun, it starts its rotation, which is described by a following algorithm: the spinner maintains its position for a second then majestically switches to the next position in clockwise or counter-clockwise order, depending on the direction the spinner was spun in.

Slastyona managed to have spinner rotating for exactly n seconds. Being fascinated by elegance of the process, she completely forgot the direction the spinner was spun in! Lucky for her, she managed to recall the starting position, and wants to deduct the direction given the information she knows. Help her do this.

## Input Format
There are two characters in the first string – the starting and the ending position of a spinner. The position is encoded with one of the following characters: v (ASCII code 118, lowercase v), < (ASCII code 60), ^ (ASCII code 94) or > (ASCII code 62) (see the picture above for reference). Characters are separated by a single space.

In the second strings, a single number n is given (0 ≤ n ≤ 109) – the duration of the rotation.

It is guaranteed that the ending position of a spinner is a result of a n second spin in any of the directions, assuming the given starting position.

## Output Format
Output cw, if the direction is clockwise, ccw – if counter-clockwise, and undefined otherwise.

## Examples
```input
^ >
1
```
```output
cw
```
-----
```input
< ^
3
```
```output
ccw
```
-----
```input
^ v
6
```
```output
undefined
```

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
It's the end of July – the time when a festive evening is held at Jelly Castle! Guests from all over the kingdom gather here to discuss new trends in the world of confectionery. Yet some of the things discussed here are not supposed to be disclosed to the general public: the information can cause discord in the kingdom of Sweetland in case it turns out to reach the wrong hands. So it's a necessity to not let any uninvited guests in.

There are 26 entrances in Jelly Castle, enumerated with uppercase English letters from A to Z. Because of security measures, each guest is known to be assigned an entrance he should enter the castle through. The door of each entrance is opened right before the first guest's arrival and closed right after the arrival of the last guest that should enter the castle through this entrance. No two guests can enter the castle simultaneously.

For an entrance to be protected from possible intrusion, a candy guard should be assigned to it. There are k such guards in the castle, so if there are more than k opened doors, one of them is going to be left unguarded! Notice that a guard can't leave his post until the door he is assigned to is closed.

Slastyona had a suspicion that there could be uninvited guests at the evening. She knows the order in which the invited guests entered the castle, and wants you to help her check whether there was a moment when more than k doors were opened.

## Input Format
Two integers are given in the first string: the number of guests n and the number of guards k (1 ≤ n ≤ 106, 1 ≤ k ≤ 26).

In the second string, n uppercase English letters s1s2... sn are given, where si is the entrance used by the i-th guest.

## Output Format
Output «YES» if at least one door was unguarded during some time, and «NO» otherwise.

You can output each letter in arbitrary case (upper or lower).

## Examples
```input
5 1
AABBB
```
```output
NO
```
-----
```input
5 1
ABABB
```
```output
YES
```

## Note
In the first sample case, the door A is opened right before the first guest's arrival and closed when the second guest enters the castle. The door B is opened right before the arrival of the third guest, and closed after the fifth one arrives. One guard can handle both doors, as the first one is closed before the second one is opened.

In the second sample case, the door B is opened before the second guest's arrival, but the only guard can't leave the door A unattended, as there is still one more guest that should enter the castle through this door.

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

# Problem
Alice and Bob are playing a game with a string of characters, with Alice going first. The string consists n characters, each of which is one of the first k letters of the alphabet. On a player’s turn, they can either arbitrarily permute the characters in the words, or delete exactly one character in the word (if there is at least one character). In addition, their resulting word cannot have appeared before throughout the entire game. The player unable to make a valid move loses the game.

Given n, k, p, find the number of words with exactly n characters consisting of the first k letters of the alphabet such that Alice will win if both Alice and Bob play optimally. Return this number modulo the prime number p.

## Input Format
The first line of input will contain three integers n, k, p (1 ≤ n ≤ 250 000, 1 ≤ k ≤ 26, 108 ≤ p ≤ 109 + 100, p will be prime).

## Output Format
Print a single integer, the number of winning words for Alice, modulo p.

## Examples
```input
4 2 100000007
```
```output
14
```

## Note
There are 14 strings that that Alice can win with. For example, some strings are "bbaa" and "baaa". Alice will lose on strings like "aaaa" or "bbbb".

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
There is an airplane which has n rows from front to back. There will be m people boarding this airplane.

This airplane has an entrance at the very front and very back of the plane.

Each person has some assigned seat. It is possible for multiple people to have the same assigned seat. The people will then board the plane one by one starting with person 1. Each person can independently choose either the front entrance or back entrance to enter the plane.

When a person walks into the plane, they walk directly to their assigned seat and will try to sit in it. If it is occupied, they will continue walking in the direction they walked in until they are at empty seat - they will take the earliest empty seat that they can find. If they get to the end of the row without finding a seat, they will be angry.

Find the number of ways to assign tickets to the passengers and board the plane without anyone getting angry. Two ways are different if there exists a passenger who chose a different entrance in both ways, or the assigned seat is different. Print this count modulo 109 + 7.

## Input Format
The first line of input will contain two integers n, m (1 ≤ m ≤ n ≤ 1 000 000), the number of seats, and the number of passengers, respectively.

## Output Format
Print a single number, the number of ways, modulo 109 + 7.

## Examples
```input
3 3
```
```output
128
```

## Note
Here, we will denote a passenger by which seat they were assigned, and which side they came from (either "F" or "B" for front or back, respectively).

For example, one valid way is 3B, 3B, 3B (i.e. all passengers were assigned seat 3 and came from the back entrance). Another valid way would be 2F, 1B, 3F.

One invalid way would be 2B, 2B, 2B, since the third passenger would get to the front without finding a seat.

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 an strictly convex polygon with n vertices. It is guaranteed that no three points are collinear. You would like to take a maximum non intersecting path on the polygon vertices that visits each point at most once.

More specifically your path can be represented as some sequence of distinct polygon vertices. Your path is the straight line segments between adjacent vertices in order. These segments are not allowed to touch or intersect each other except at the vertices in your sequence.

Given the polygon, print the maximum length non-intersecting path that visits each point at most once.

## Input Format
The first line of input will contain a single integer n (2 ≤ n ≤ 2 500), the number of points.

The next n lines will contain two integers xi, yi (|xi|, |yi| ≤ 109), denoting the coordinates of the i-th vertex.

It is guaranteed that these points are listed in clockwise order.

## Output Format
Print a single floating point number, representing the longest non-intersecting path that visits the vertices at most once.

Your answer will be accepted if it has absolute or relative error at most 10 - 9. More specifically, if your answer is a and the jury answer is b, your answer will be accepted if $${ \frac { | a - b | } { \operatorname* { m a x } ( 1, b ) } } \leq 1 0 ^ { - 9 }$$.

## Examples
```input
4
0 0
0 1
1 1
1 0
```
```output
3.4142135624
```

## Note
One optimal path is to visit points 0,1,3,2 in order.

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
Masha is fond of cacti. When she was a little girl, she decided to plant a tree. Now Masha wants to make a nice cactus out of her tree.

Recall that tree is a connected undirected graph that has no cycles. Cactus is a connected undirected graph such that each vertex belongs to at most one cycle.

Masha has some additional edges that she can add to a tree. For each edge she knows which vertices it would connect and the beauty of this edge. Masha can add some of these edges to the graph if the resulting graph is a cactus. Beauty of the resulting cactus is sum of beauties of all added edges.

Help Masha find out what maximum beauty of the resulting cactus she can achieve.

## Input Format
The first line of the input data contains two integers n and m — the number of vertices in a tree, and the number of additional edges available (3 ≤ n ≤ 2·105; 0 ≤ m ≤ 2·105).

Let us describe Masha's tree. It has a root at vertex 1. The second line contains n - 1 integers: p2, p3, ..., pn, here pi — is the parent of a vertex i — the first vertex on a path from the vertex i to the root of the tree (1 ≤ pi < i).

The following m lines contain three integers ui, vi and ci — pairs of vertices to be connected by the additional edges that Masha can add to the tree and beauty of edge (1 ≤ ui, vi ≤ n; ui ≠ vi; 1 ≤ ci ≤ 104).

It is guaranteed that no additional edge coincides with the edge of the tree.

## Output Format
Output one integer — the maximum beauty of a cactus Masha can achieve.

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

# Problem
As you may know, MemSQL has American offices in both San Francisco and Seattle. Being a manager in the company, you travel a lot between the two cities, always by plane.

You prefer flying from Seattle to San Francisco than in the other direction, because it's warmer in San Francisco. You are so busy that you don't remember the number of flights you have made in either direction. However, for each of the last n days you know whether you were in San Francisco office or in Seattle office. You always fly at nights, so you never were at both offices on the same day. Given this information, determine if you flew more times from Seattle to San Francisco during the last n days, or not.

## Input Format
The first line of input contains single integer n (2 ≤ n ≤ 100) — the number of days.

The second line contains a string of length n consisting of only capital 'S' and 'F' letters. If the i-th letter is 'S', then you were in Seattle office on that day. Otherwise you were in San Francisco. The days are given in chronological order, i.e. today is the last day in this sequence.

## Output Format
Print "YES" if you flew more times from Seattle to San Francisco, and "NO" otherwise.

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

## Examples
```input
4
FSSF
```
```output
NO
```
-----
```input
2
SF
```
```output
YES
```
-----
```input
10
FFFFFFFFFF
```
```output
NO
```
-----
```input
10
SSFFSFFSFF
```
```output
YES
```

## Note
In the first example you were initially at San Francisco, then flew to Seattle, were there for two days and returned to San Francisco. You made one flight in each direction, so the answer is "NO".

In the second example you just flew from Seattle to San Francisco, so the answer is "YES".

In the third example you stayed the whole period in San Francisco, so the answer is "NO".

In the fourth example if you replace 'S' with ones, and 'F' with zeros, you'll get the first few digits of π in binary representation. Not very useful information though.

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
Luba has to do n chores today. i-th chore takes ai units of time to complete. It is guaranteed that for every $$i \in [2..n]$$ the condition ai ≥ ai - 1 is met, so the sequence is sorted.

Also Luba can work really hard on some chores. She can choose not more than k any chores and do each of them in x units of time instead of ai ($${ x < \operatorname* { m i n } _ { i = 1 } ^ { n } a _ { i } }$$).

Luba is very responsible, so she has to do all n chores, and now she wants to know the minimum time she needs to do everything. Luba cannot do two chores simultaneously.

## Input Format
The first line contains three integers n, k, x (1 ≤ k ≤ n ≤ 100, 1 ≤ x ≤ 99) — the number of chores Luba has to do, the number of chores she can do in x units of time, and the number x itself.

The second line contains n integer numbers ai (2 ≤ ai ≤ 100) — the time Luba has to spend to do i-th chore.

It is guaranteed that $${ x < \operatorname* { m i n } _ { i = 1 } ^ { n } a _ { i } }$$, and for each $$i \in [2..n]$$ ai ≥ ai - 1.

## Output Format
Print one number — minimum time Luba needs to do all n chores.

## Examples
```input
4 2 2
3 6 7 10
```
```output
13
```
-----
```input
5 2 1
100 100 100 100 100
```
```output
302
```

## Note
In the first example the best option would be to do the third and the fourth chore, spending x = 2 time on each instead of a3 and a4, respectively. Then the answer is 3 + 6 + 2 + 2 = 13.

In the second example Luba can choose any two chores to spend x time on them instead of ai. So the answer is 100·3 + 2·1 = 302.

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 string s consisting only of characters 0 and 1. A substring [l, r] of s is a string slsl + 1sl + 2... sr, and its length equals to r - l + 1. A substring is called balanced if the number of zeroes (0) equals to the number of ones in this substring.

You have to determine the length of the longest balanced substring of s.

## Input Format
The first line contains n (1 ≤ n ≤ 100000) — the number of characters in s.

The second line contains a string s consisting of exactly n characters. Only characters 0 and 1 can appear in s.

## Output Format
If there is no non-empty balanced substring in s, print 0. Otherwise, print the length of the longest balanced substring.

## Examples
```input
8
11010111
```
```output
4
```
-----
```input
3
111
```
```output
0
```

## Note
In the first example you can choose the substring [3, 6]. It is balanced, and its length is 4. Choosing the substring [2, 5] is also possible.

In the second example it's impossible to find a non-empty balanced substring.

Now solve the problem and return the code.