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
After Fox Ciel got off a bus, she found that the bus she was on was a wrong bus and she lost her way in a strange town. However, she fortunately met her friend Beaver Taro and asked which way to go to her castle. Taro's response to her was a string s, and she tried to remember the string s correctly.

However, Ciel feels n strings b1, b2, ... , bn are really boring, and unfortunately she dislikes to remember a string that contains a boring substring. To make the thing worse, what she can remember is only the contiguous substring of s.

Determine the longest contiguous substring of s that does not contain any boring string, so that she can remember the longest part of Taro's response.

## Input Format
In the first line there is a string s. The length of s will be between 1 and 105, inclusive.

In the second line there is a single integer n (1 ≤ n ≤ 10).  Next n lines, there is a string bi (1 ≤ i ≤ n). Each length of bi will be between 1 and 10, inclusive.

Each character of the given strings will be either a English alphabet (both lowercase and uppercase) or a underscore ('_') or a digit. Assume that these strings are case-sensitive.

## Output Format
Output in the first line two space-separated integers len and pos: the length of the longest contiguous substring of s that does not contain any bi, and the first position of the substring (0-indexed). The position pos must be between 0 and |s| - len inclusive, where |s| is the length of string s.

If there are several solutions, output any.

## Examples
```input
Go_straight_along_this_street
5
str
long
tree
biginteger
ellipse
```
```output
12 4
```
-----
```input
IhaveNoIdea
9
I
h
a
v
e
N
o
I
d
```
```output
0 0
```
-----
```input
unagioisii
2
ioi
unagi
```
```output
5 5
```

## Note
In the first sample, the solution is traight_alon.

In the second sample, the solution is an empty string, so the output can be «0 0», «0 1», «0 2», and so on.

In the third sample, the solution is either nagio or oisii.

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
Finally Fox Ciel arrived in front of her castle!

She have to type a password to enter her castle. An input device attached to her castle is a bit unusual.

The input device is a 1 × n rectangle divided into n square panels. They are numbered 1 to n from left to right. Each panel has a state either ON or OFF. Initially all panels are in the OFF state. She can enter her castle if and only if x1-th, x2-th, ..., xk-th panels are in the ON state and other panels are in the OFF state.

She is given an array a1, ..., al. In each move, she can perform the following operation: choose an index i (1 ≤ i ≤ l), choose consecutive ai panels, and flip the states of those panels (i.e. ON → OFF, OFF → ON).

Unfortunately she forgets how to type the password with only above operations. Determine the minimal number of operations required to enter her castle.

## Input Format
The first line contains three integers n, k and l (1 ≤ n ≤ 10000, 1 ≤ k ≤ 10, 1 ≤ l ≤ 100), separated by single spaces.

The second line contains k integers x1, ..., xk (1 ≤ x1 < x2 < ... < xk ≤ n), separated by single spaces.

The third line contains l integers a1, ..., al (1 ≤ ai ≤ n), separated by single spaces. It is possible that some elements of the array ai are equal value.

## Output Format
Print the minimal number of moves required to type the password. If it's impossible, print -1.

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

## Note
One possible way to type the password in the first example is following: In the first move, choose 1st, 2nd, 3rd panels and flip those panels. In the second move, choose 5th, 6th, 7th, 8th, 9th panels and flip those panels.

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
Fox Ciel safely returned to her castle, but there was something wrong with the security system of the castle: sensors attached in the castle were covering her.

Ciel is at point (1, 1) of the castle now, and wants to move to point (n, n), which is the position of her room. By one step, Ciel can move from point (x, y) to either (x + 1, y) (rightward) or (x, y + 1) (upward).

In her castle, c2 sensors are set at points (a + i, b + j) (for every integer i and j such that: 0 ≤ i < c, 0 ≤ j < c).

Each sensor has a count value and decreases its count value every time Ciel moves. Initially, the count value of each sensor is t. Every time Ciel moves to point (x, y), the count value of a sensor at point (u, v) decreases by (|u - x| + |v - y|). When the count value of some sensor becomes strictly less than 0, the sensor will catch Ciel as a suspicious individual!

Determine whether Ciel can move from (1, 1) to (n, n) without being caught by a sensor, and if it is possible, output her steps. Assume that Ciel can move to every point even if there is a censor on the point.

## Input Format
In the first line there are five integers n, t, a, b, c (2 ≤ n ≤ 2·105,  0 ≤ t ≤ 1014,  1 ≤ a ≤ n - c + 1,  1 ≤ b ≤ n - c + 1,  1 ≤ c ≤ n).

Please do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin stream (also you may use the %I64d specificator).

## Output Format
If Ciel's objective is possible, output in first line 2n - 2 characters that represent her feasible steps, where i-th character is R if i-th step is moving rightward, or U if moving upward. If there are several solution, output lexicographically first one. Character R is lexicographically earlier than the character U.

If her objective is impossible, output Impossible.

## Examples
```input
5 25 2 4 1
```
```output
RRUURURU
```
-----
```input
3 6 1 2 2
```
```output
URUR
```
-----
```input
3 5 1 2 2
```
```output
Impossible
```
-----
```input
20 492 11 4 8
```
```output
RRRRRRRRRRRRRRRRUUUUURUUUUURRUUUUUUUUU
```

## Note
The answers for the first sample and the second sample are shown on the picture:

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 cities situated along the main road of Berland. Cities are represented by their coordinates — integer numbers a1, a2, ..., an. All coordinates are pairwise distinct.

It is possible to get from one city to another only by bus. But all buses and roads are very old, so the Minister of Transport decided to build a new bus route. The Minister doesn't want to spend large amounts of money — he wants to choose two cities in such a way that the distance between them is minimal possible. The distance between two cities is equal to the absolute value of the difference between their coordinates.

It is possible that there are multiple pairs of cities with minimal possible distance, so the Minister wants to know the quantity of such pairs.

Your task is to write a program that will calculate the minimal possible distance between two pairs of cities and the quantity of pairs which have this distance.

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

The second line contains n integer numbers a1, a2, ..., an ( - 109 ≤ ai ≤ 109). All numbers ai are pairwise distinct.

## Output Format
Print two integer numbers — the minimal distance and the quantity of pairs with this distance.

## Examples
```input
4
6 -3 0 4
```
```output
2 1
```
-----
```input
3
-2 0 2
```
```output
2 2
```

## Note
In the first example the distance between the first city and the fourth city is |4 - 6| = 2, and it is the only pair with this distance.

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 the counting-out game. Children are numbered clockwise from 1 to n. In the beginning, the first child is considered the leader. The game is played in k steps. In the i-th step the leader counts out ai people in clockwise order, starting from the next person. The last one to be pointed at by the leader is eliminated, and the next player after him becomes the new leader.

For example, if there are children with numbers [8, 10, 13, 14, 16] currently in the circle, the leader is child 13 and ai = 12, then counting-out rhyme ends on child 16, who is eliminated. Child 8 becomes the leader.

You have to write a program which prints the number of the child to be eliminated on every step.

## Input Format
The first line contains two integer numbers n and k (2 ≤ n ≤ 100, 1 ≤ k ≤ n - 1).

The next line contains k integer numbers a1, a2, ..., ak (1 ≤ ai ≤ 109).

## Output Format
Print k numbers, the i-th one corresponds to the number of child to be eliminated at the i-th step.

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

## Note
Let's consider first example:

- In the first step child 4 is eliminated, child 5 becomes the leader.
- In the second step child 2 is eliminated, child 3 becomes the leader.
- In the third step child 5 is eliminated, child 6 becomes the leader.
- In the fourth step child 6 is eliminated, child 7 becomes the leader.
- In the final step child 1 is eliminated, child 3 becomes the leader.

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 positive integer number n is written on a blackboard. It consists of not more than 105 digits. You have to transform it into a beautiful number by erasing some of the digits, and you want to erase as few digits as possible.

The number is called beautiful if it consists of at least one digit, doesn't have leading zeroes and is a multiple of 3. For example, 0, 99, 10110 are beautiful numbers, and 00, 03, 122 are not.

Write a program which for the given n will find a beautiful number such that n can be transformed into this number by erasing as few digits as possible. You can erase an arbitraty set of digits. For example, they don't have to go one after another in the number n.

If it's impossible to obtain a beautiful number, print -1. If there are multiple answers, print any of them.

## Input Format
The first line of input contains n — a positive integer number without leading zeroes (1 ≤ n < 10100000).

## Output Format
Print one number — any beautiful number obtained by erasing as few as possible digits. If there is no answer, print  - 1.

## Examples
```input
1033
```
```output
33
```
-----
```input
10
```
```output
0
```
-----
```input
11
```
```output
-1
```

## Note
In the first example it is enough to erase only the first digit to obtain a multiple of 3. But if we erase the first digit, then we obtain a number with a leading zero. So the minimum number of digits to be erased is two.

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
T is a complete binary tree consisting of n vertices. It means that exactly one vertex is a root, and each vertex is either a leaf (and doesn't have children) or an inner node (and has exactly two children). All leaves of a complete binary tree have the same depth (distance from the root). So n is a number such that n + 1 is a power of 2.

In the picture you can see a complete binary tree with n = 15.

Vertices are numbered from 1 to n in a special recursive way: we recursively assign numbers to all vertices from the left subtree (if current vertex is not a leaf), then assign a number to the current vertex, and then recursively assign numbers to all vertices from the right subtree (if it exists). In the picture vertices are numbered exactly using this algorithm. It is clear that for each size of a complete binary tree exists exactly one way to give numbers to all vertices. This way of numbering is called symmetric.

You have to write a program that for given n answers q queries to the tree.

Each query consists of an integer number ui (1 ≤ ui ≤ n) and a string si, where ui is the number of vertex, and si represents the path starting from this vertex. String si doesn't contain any characters other than 'L', 'R' and 'U', which mean traverse to the left child, to the right child and to the parent, respectively. Characters from si have to be processed from left to right, considering that ui is the vertex where the path starts. If it's impossible to process a character (for example, to go to the left child of a leaf), then you have to skip it. The answer is the number of vertex where the path represented by si ends.

For example, if ui = 4 and si = «UURL», then the answer is 10.

## Input Format
The first line contains two integer numbers n and q (1 ≤ n ≤ 1018, q ≥ 1). n is such that n + 1 is a power of 2.

The next 2q lines represent queries; each query consists of two consecutive lines. The first of these two lines contains ui (1 ≤ ui ≤ n), the second contains non-empty string si. si doesn't contain any characters other than 'L', 'R' and 'U'.

It is guaranteed that the sum of lengths of si (for each i such that 1 ≤ i ≤ q) doesn't exceed 105.

## Output Format
Print q numbers, i-th number must be the answer to the i-th query.

## Examples
```input
15 2
4
UURL
8
LRLLLLLLLL
```
```output
10
5
```

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
Tavak and Seyyed are good friends. Seyyed is very funny and he told Tavak to solve the following problem instead of longest-path.

You are given l and r. For all integers from l to r, inclusive, we wrote down all of their integer divisors except 1. Find the integer that we wrote down the maximum number of times.

Solve the problem to show that it's not a NP problem.

## Input Format
The first line contains two integers l and r (2 ≤ l ≤ r ≤ 109).

## Output Format
Print single integer, the integer that appears maximum number of times in the divisors.

If there are multiple answers, print any of them.

## Examples
```input
19 29
```
```output
2
```
-----
```input
3 6
```
```output
3
```

## Note
Definition of a divisor: https://www.mathsisfun.com/definitions/divisor-of-an-integer-.html

The first example: from 19 to 29 these numbers are divisible by 2: {20, 22, 24, 26, 28}.

The second example: from 3 to 6 these numbers are divisible by 3: {3, 6}.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
In the beginning of the new year Keivan decided to reverse his name. He doesn't like palindromes, so he changed Naviek to Navick.

He is too selfish, so for a given n he wants to obtain a string of n characters, each of which is either 'a', 'b' or 'c', with no palindromes of length 3 appearing in the string as a substring. For example, the strings "abc" and "abca" suit him, while the string "aba" doesn't. He also want the number of letters 'c' in his string to be as little as possible.

## Input Format
The first line contains single integer n (1 ≤ n ≤ 2·105) — the length of the string.

## Output Format
Print the string that satisfies all the constraints.

If there are multiple answers, print any of them.

## Examples
```input
2
```
```output
aa
```
-----
```input
3
```
```output
bba
```

## Note
A palindrome is a sequence of characters which reads the same backward and forward.

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
Leha and Noora decided to go on a trip in the Baltic States. As you know from the previous problem, Leha has lost his car on the parking of the restaurant. Unfortunately, requests to the watchman didn't helped hacker find the car, so friends decided to go hitchhiking.

In total, they intended to visit n towns. However it turned out that sights in i-th town are open for visitors only on days from li to ri.

What to do? Leha proposed to choose for each town i a day, when they will visit this town, i.e any integer xi in interval [li, ri]. After that Noora choses some subsequence of towns id1, id2, ..., idk, which friends are going to visit, that at first they are strictly increasing, i.e idi < idi + 1 is for all integers i from 1 to k - 1, but also the dates of the friends visits are strictly increasing, i.e xidi < xidi + 1 is true for all integers i from 1 to k - 1.

Please help Leha and Noora in choosing such xi for each town i, and such subsequence of towns id1, id2, ..., idk, so that friends can visit maximal number of towns.

You may assume, that Leha and Noora can start the trip any day.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 3·105) denoting the number of towns Leha and Noora intended to visit.

Each line i of the n subsequent lines contains two integers li, ri (1 ≤ li ≤ ri ≤ 109), denoting that sights in i-th town are open for visitors on any day $$x \in [l_i, r_i]$$.

## Output Format
Print a single integer denoting the maximal number of towns, that Leha and Noora can visit.

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

## Note
Consider the first example.

Let's take this plan: let's visit the sight in the second town on the first day, in the third town on the third day and in the fifth town on the fourth. That's would be the optimal 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 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
At regular competition Vladik and Valera won a and b candies respectively. Vladik offered 1 his candy to Valera. After that Valera gave Vladik 2 his candies, so that no one thought that he was less generous. Vladik for same reason gave 3 candies to Valera in next turn.

More formally, the guys take turns giving each other one candy more than they received in the previous turn.

This continued until the moment when one of them couldn’t give the right amount of candy. Candies, which guys got from each other, they don’t consider as their own. You need to know, who is the first who can’t give the right amount of candy.

## Input Format
Single line of input data contains two space-separated integers a, b (1 ≤ a, b ≤ 109) — number of Vladik and Valera candies respectively.

## Output Format
Pring a single line "Vladik’’ in case, if Vladik first who can’t give right amount of candy, or "Valera’’ otherwise.

## Examples
```input
1 1
```
```output
Valera
```
-----
```input
7 6
```
```output
Vladik
```

## Note
Illustration for first test case:

Illustration for second test case:

Now solve the problem and return the code.