vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Sherlock Holmes is your good friend. You are a very good programmer but you also know that Sherlock Holmes has better observing powers. So there is a problem which you two have to solve. Lets see who solves it first.

Given a  sequence of n integers S1,S2,S3,.......,Sn.  You have to chose k windows of size m-1 each (where m is given to you) such that sum of all the elements in these k windows is maximum possible.
Window [l i, r i ] contains all elements from Sl to Sr . Window size ( r i -  l i ) should be equal to m-1 . 

Choose k windows
 [l 1, r 1], [l 2, r 2], [l 3, r 3],......., [l k, r k].                  
   Such that   1 ≤ l 1 ≤ r 1 < l 2 ≤ r 2< ......... <l k ≤r k ≤ n  . (Windows should not overlap).             
 and r i -  l i  =  m - 1

INPUT

First line contains three integers n, m and k (1 ≤ (m × k) ≤ n ≤ 5000). The second line contains n space seperated integers S1,S2,S3,.......,Sn (0 ≤ Si ≤ 10^9)

OUTPUT

Print an integer in a single line — the maximum possible value of sum.

SAMPLE INPUT
5 2 2
1 7 3 6 5

SAMPLE OUTPUT
21

Explanation

The window size is m-1, that is equal to 1 in this case and we have to select 2 windows. 
Windows corresponding to the answer are [2,3] and [4,5] so sum = 7+3+6+5 = 21.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the city of Nevermore, there are 10^8 streets and 10^8 avenues, both numbered from 0 to 10^8-1. All streets run straight from west to east, and all avenues run straight from south to north. The distance between neighboring streets and between neighboring avenues is exactly 100 meters.

Every street intersects every avenue. Every intersection can be described by pair (x, y), where x is avenue ID and y is street ID.

There are N fountains in the city, situated at intersections (X_i, Y_i). Unlike normal intersections, there's a circle with radius 10 meters centered at the intersection, and there are no road parts inside this circle.

The picture below shows an example of how a part of the city with roads and fountains may look like.

1f931bf0c98ec6f07e612b0282cdb094.png

City governors don't like encountering more than one fountain while moving along the same road. Therefore, every street contains at most one fountain on it, as well as every avenue.

Citizens can move along streets, avenues and fountain perimeters. What is the shortest distance one needs to cover in order to get from intersection (x_1, y_1) to intersection (x_2, y_2)?

Constraints

* 0 \leq x_1, y_1, x_2, y_2 < 10^8
* 1 \leq N \leq 200,000
* 0 \leq X_i, Y_i < 10^8
* X_i \neq X_j for i \neq j
* Y_i \neq Y_j for i \neq j
* Intersections (x_1, y_1) and (x_2, y_2) are different and don't contain fountains.
* All input values are integers.

Input

Input is given from Standard Input in the following format:


x_1 y_1 x_2 y_2
N
X_1 Y_1
X_2 Y_2
:
X_N Y_N


Output

Print the shortest possible distance one needs to cover in order to get from intersection (x_1, y_1) to intersection (x_2, y_2), in meters. Your answer will be considered correct if its absolute or relative error doesn't exceed 10^{-11}.

Examples

Input

1 1 6 5
3
3 2
5 3
2 4


Output

891.415926535897938


Input

3 5 6 4
3
3 2
5 3
2 4


Output

400.000000000000000


Input

4 2 2 2
3
3 2
5 3
2 4


Output

211.415926535897938

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.

Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it a_{k}) and delete it, at that all elements equal to a_{k} + 1 and a_{k} - 1 also must be deleted from the sequence. That step brings a_{k} points to the player. 

Alex is a perfectionist, so he decided to get as many points as possible. Help him.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) that shows how many numbers are in Alex's sequence. 

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5).


-----Output-----

Print a single integer — the maximum number of points that Alex can earn.


-----Examples-----
Input
2
1 2

Output
2

Input
3
1 2 3

Output
4

Input
9
1 2 1 3 2 2 2 2 3

Output
10



-----Note-----

Consider the third test example. At first step we need to choose any element equal to 2. After that step our sequence looks like this [2, 2, 2, 2]. Then we do 4 steps, on each step we choose any element equals to 2. In total we earn 10 points.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
High school student Vasya got a string of length n as a birthday present. This string consists of letters 'a' and 'b' only. Vasya denotes beauty of the string as the maximum length of a substring (consecutive subsequence) consisting of equal letters.

Vasya can change no more than k characters of the original string. What is the maximum beauty of the string he can achieve?


-----Input-----

The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — the length of the string and the maximum number of characters to change.

The second line contains the string, consisting of letters 'a' and 'b' only.


-----Output-----

Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.


-----Examples-----
Input
4 2
abba

Output
4

Input
8 1
aabaabaa

Output
5



-----Note-----

In the first sample, Vasya can obtain both strings "aaaa" and "bbbb".

In the second sample, the optimal answer is obtained with the string "aaaaabaa" or with the string "aabaaaaa".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Over the years, Grandpa Bernie has traveled all over the world. He doesn’t travel that much anymore, but he loves to tell his grandchildren stories from all these trips. He’ll tell them the story from when he went to Israel for the first time, or when he went to Greece for the third time.

His memory works in a funny way. He can easily remember his $k$:th trip to a particular country, but he’ll have a hard time remembering in which year he went on that trip. Given a list of all the trips Grandpa Bernie went on, can you answer a number of queries asking in which year he went on his $k$:th trip to a particular country?

-----Input-----
The input consists of:
 - one line with one integer $n$ ($1 \leq n \leq 10^5$), the number of trips Grandpa Bernie went on;
 - $n$ lines each containing the name $s$ ($1 \leq |s| \leq 20$) of a country and an integer $y$ ($1 \leq y \leq 10^6$) representing a trip to country $s$ that Grandpa Bernie went on in year $y$;
 - one line with one integer $q$ ($1 \leq q \leq 10^5$), the number of queries;
 - $q$ lines each containing the name $s$ of a country and an integer $k$ representing a query for the $k$:th time Grandpa Bernie went to country $s$.

Each country name only consists of letters from the English alphabet. It is also guaranteed that, for each query asking for the $k$:th trip to country $s$, $k$ is at least $1$ and no greater than the number of times Grandpa Bernie went to country $s$. In particular, it is guaranteed that Grandpa Bernie has visited country $s$ at least once.

-----Output-----
For each query for the $k$:th trip Grandpa Bernie went to a country $s$, output a single line containing the year in which Grandpa Bernie went on that trip.

-----Examples-----
Sample Input:
4
Iceland 2016
Sweden 2015
Iceland 1982
Norway 1999
3
Sweden 1
Iceland 1
Iceland 2
Sample Output:
2015
1982
2016

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There were $n$ types of swords in the theater basement which had been used during the plays. Moreover there were exactly $x$ swords of each type. $y$ people have broken into the theater basement and each of them has taken exactly $z$ swords of some single type. Note that different people might have taken different types of swords. Note that the values $x, y$ and $z$ are unknown for you.

The next morning the director of the theater discovers the loss. He counts all swords — exactly $a_i$ swords of the $i$-th type are left untouched.

The director has no clue about the initial number of swords of each type in the basement, the number of people who have broken into the basement and how many swords each of them have taken.

For example, if $n=3$, $a = [3, 12, 6]$ then one of the possible situations is $x=12$, $y=5$ and $z=3$. Then the first three people took swords of the first type and the other two people took swords of the third type. Note that you don't know values $x, y$ and $z$ beforehand but know values of $n$ and $a$.

Thus he seeks for your help. Determine the minimum number of people $y$, which could have broken into the theater basement, and the number of swords $z$ each of them has taken.


-----Input-----

The first line of the input contains one integer $n$ $(2 \le n \le 2 \cdot 10^{5})$ — the number of types of swords.

The second line of the input contains the sequence $a_1, a_2, \dots, a_n$ $(0 \le a_i \le 10^{9})$, where $a_i$ equals to the number of swords of the $i$-th type, which have remained in the basement after the theft. It is guaranteed that there exists at least one such pair of indices $(j, k)$ that $a_j \neq a_k$.


-----Output-----

Print two integers $y$ and $z$ — the minimum number of people which could have broken into the basement and the number of swords each of them has taken.


-----Examples-----
Input
3
3 12 6

Output
5 3

Input
2
2 9

Output
1 7

Input
7
2 1000000000 4 6 8 4 2

Output
2999999987 2

Input
6
13 52 0 13 26 52

Output
12 13



-----Note-----

In the first example the minimum value of $y$ equals to $5$, i.e. the minimum number of people who could have broken into the basement, is $5$. Each of them has taken $3$ swords: three of them have taken $3$ swords of the first type, and two others have taken $3$ swords of the third type.

In the second example the minimum value of $y$ is $1$, i.e. the minimum number of people who could have broken into the basement, equals to $1$. He has taken $7$ swords of the first type.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a product engineer and would like to improve the quality of duct tapes that your company manufactures. An entire tape can be represented as a single row of N cells. Each cell has its Stickiness factor, which stands for its ability to stick to an object. We say that a tape is a good quality product, if and only if the total sum of Stickiness factors of grid cells in any of its subarray of size K is at least D.

To make a quality product, consider an augment operation in which you can choose any subarray of size at most K  and a real number (say R), and multiply Stickiness factor of all its cells by R. For each augment operation, the subarray and the value of R can be chosen arbitrarily. However, the size of chosen subarray for augmentation can be at most K, as mentioned before. 

Your task is to calculate the minimum number of augment operations needed to be performed in order to transform the given tape to a good quality product.

INPUT

The first line contains three space separated integers N, K and D, as described above. The next line contains N space separated integers, i^th of which (denoted by Ai) denotes the Stickiness factor of i^th cell.

OUTPUT

Output in single line, an integer, which denotes the minimum number of augment operations needed to be performed in order to transform the tape to a good quality product. In case, if it is impossible to achieve, print -1 instead.

CONSTRAINTS

1 ≤ N, D ≤ 10^5
1 ≤ K ≤ N
0 ≤ Ai ≤ 10^5

SAMPLE INPUT
3 2 4
1 1 1 

SAMPLE OUTPUT
1

Explanation

We can multiply the second element by 3. Now the tape becomes: 1 3 1. 

Any subarray of size 2 has now sum = 4, which satisfies the required condition. We used 1 augment operation, hence the answer is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shil is very bad at greedy algorithms. So he decided to practice a lot of greedy problems. He came across a very good problem.Problem is as follows:      
Given a linear strip of length N. Strip consists of N cells painted in either BLACK or WHITE color. At each move you can do following process:   
Take any  2 or 3  contiguous cells.     
Invert their colors (i.e replace BLACK cells with WHITE cells and WHITE cells with BLACK cells).

You are required to answer minimum number of moves in which you can change all the cells into same color( either WHITE or BLACK). 

Input
First line of input contains N which represents length of strip.
Second line of input consists of string of length N. Each character of string will be W or B . B represents Black cell and W represents White cell.   

Output
Minimum number of moves in which you can change all the cells into same color .i.e make the whole strip consisting of cells having same color.

Constraints 
2 ≤ N ≤ 20     

SAMPLE INPUT
7
WWBBBWW

SAMPLE OUTPUT
1

Explanation

In the give sample case you can make whole string monochromatic as follows:

Method 1:
WWBBBWW to WWWWWWW by performing a move on cells 3 to 5(1-indexed).

Method 2:
WWBBBWW to BBBBBWW  to BBBBBBB in a total of 2 moves.

Thus minimum number of moves is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The $N$ citizens of Eagleton have chosen to build their houses in a row along a single street (so that the houses can be numbered from $1$ to $N$, with $1$ the leftmost house and $N$ the rightmost). The houses have varying heights, with house $i$ being $h_ i$ inches tall. 

Unfortunately, all is not well in Eagleton: the citizens have a bit of an envy problem. Every day, one random citizen (the owner of house $i$, let’s say) emerges from their house and compares their house’s height to the heights of the two neighboring houses. If house $i$ is at least as tall as the average, plus $k$ inches (in other words, if $h_ i \geq (h_{i-1} + h_{i+1}) / 2 + k$), the citizen retreats back into their house, satisfied. Otherwise, the citizen remodels their house to have new height $(h_{i-1} + h_{i+1}) / 2 + k$. (The citizen does this remodeling even if the new height is only a tiny fraction of an inch taller than the old height—like we said, Eagleton has an envy problem.)

The left of house $1$ and the right of house $N$ is a nature preserve; the citizens of these houses treat the preserve as a “house” having height zero inches, for the purposes of the above calculations.

The city council of Eagleton is fed up with the constant construction traffic and noise, and has hired you to compute what Eagleton will look like when all of the remodeling is finally over. After some calculations, you discover that it is guaranteed that each house will converge to a final finite height after infinitely many days of the above remodeling process. Print the final height of the house that ends up tallest.

-----Input-----
The first line of input consists of an integer $N$ and real number $k$, separated by a space $(1 \leq N \leq 100000; 0 \leq k \leq 10^{20})$: the number of houses in Eagleton and the number of inches each citizen wants their own house to be taller than the average of their neighbors.

$N$ lines follow. The $i$th such line (starting at $i=1$) contains a real number $h_ i$ ($0 \leq h_ i \leq 10^{20}$), the initial height (in inches) of house $i$.

The real numbers in the input may be provided in scientific notation (see for instance Sample Input 2) and will have at most ten digits after the decimal point.

-----Output-----
Print the height (in inches) of the tallest house, after all houses have been remodeled over infinitely many days of the process described above. Your answer will be judged correct if the absolute or relative error is within $10^{-6}$.

-----Examples-----
Sample Input:
3 1
39
10
40
Sample Output:
40.5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Patrick likes to play baseball, but sometimes he will spend so many hours hitting home runs that his mind starts to get foggy! Patrick is sure that his scores across $n$ sessions follow the identity permutation (ie. in the first game he scores $1$ point, in the second game he scores $2$ points and so on). However, when he checks back to his record, he sees that all the numbers are mixed up! 

Define a special exchange as the following: choose any subarray of the scores and permute elements such that no element of subarray gets to the same position as it was before the exchange. For example, performing a special exchange on $[1,2,3]$ can yield $[3,1,2]$ but it cannot yield $[3,2,1]$ since the $2$ is in the same position. 

Given a permutation of $n$ integers, please help Patrick find the minimum number of special exchanges needed to make the permutation sorted! It can be proved that under given constraints this number doesn't exceed $10^{18}$.

An array $a$ is a subarray of an array $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains integer $n$ ($1 \leq n \leq 2 \cdot 10^5$)  — the length of the given permutation.

The second line of each test case contains $n$ integers $a_{1},a_{2},...,a_{n}$ ($1 \leq a_{i} \leq n$)  — the initial permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output one integer: the minimum number of special exchanges needed to sort the permutation.


-----Example-----
Input
2
5
1 2 3 4 5
7
3 2 4 5 1 6 7

Output
0
2



-----Note-----

In the first permutation, it is already sorted so no exchanges are needed.

It can be shown that you need at least $2$ exchanges to sort the second permutation.

$[3, 2, 4, 5, 1, 6, 7]$

Perform special exchange on range ($1, 5$)

$[4, 1, 2, 3, 5, 6, 7]$

Perform special exchange on range ($1, 4$)

$[1, 2, 3, 4, 5, 6, 7]$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, capitalize the letters that occupy even indexes and odd indexes separately, and return as shown below. Index `0` will be considered even.

For example, `capitalize("abcdef") = ['AbCdEf', 'aBcDeF']`. See test cases for more examples.

The input will be a lowercase string with no spaces.

Good luck!

If you like this Kata, please try: 

[Indexed capitalization](https://www.codewars.com/kata/59cfc09a86a6fdf6df0000f1)

[Even-odd disparity](https://www.codewars.com/kata/59c62f1bdcc40560a2000060)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya likes to solve equations. Today he wants to solve $(x~\mathrm{div}~k) \cdot (x \bmod k) = n$, where $\mathrm{div}$ and $\mathrm{mod}$ stand for integer division and modulo operations (refer to the Notes below for exact definition). In this equation, $k$ and $n$ are positive integer parameters, and $x$ is a positive integer unknown. If there are several solutions, Vasya wants to find the smallest possible $x$. Can you help him?


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 10^6$, $2 \leq k \leq 1000$).


-----Output-----

Print a single integer $x$ — the smallest positive integer solution to $(x~\mathrm{div}~k) \cdot (x \bmod k) = n$. It is guaranteed that this equation has at least one positive integer solution.


-----Examples-----
Input
6 3

Output
11

Input
1 2

Output
3

Input
4 6

Output
10



-----Note-----

The result of integer division $a~\mathrm{div}~b$ is equal to the largest integer $c$ such that $b \cdot c \leq a$. $a$ modulo $b$ (shortened $a \bmod b$) is the only integer $c$ such that $0 \leq c < b$, and $a - c$ is divisible by $b$.

In the first sample, $11~\mathrm{div}~3 = 3$ and $11 \bmod 3 = 2$. Since $3 \cdot 2 = 6$, then $x = 11$ is a solution to $(x~\mathrm{div}~3) \cdot (x \bmod 3) = 6$. One can see that $19$ is the only other positive integer solution, hence $11$ is the smallest one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 The year of `2013` is the first year after the old `1987` with only distinct digits.

 Now your task is to solve the following problem: given a `year` number, find the minimum year number which is strictly larger than the given one and has only distinct digits.

# Input/Output


 - `[input]` integer `year`

 `1000 ≤ year ≤ 9000`


 - `[output]` an integer

  the minimum year number that is strictly larger than the input number `year` and all its digits are distinct.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ringo found a string s of length n in his [yellow submarine](https://www.youtube.com/watch?v=m2uTFF_3MaA). The string contains only lowercase letters from the English alphabet. As Ringo and his friends love palindromes, he would like to turn the string s into a palindrome by applying two types of operations to the string. 

The first operation allows him to choose i (2 ≤ i ≤ n-1) and to append the substring s_2s_3 … s_i (i - 1 characters) reversed to the front of s.

The second operation allows him to choose i (2 ≤ i ≤ n-1) and to append the substring s_i s_{i + 1}… s_{n - 1} (n - i characters) reversed to the end of s.

Note that characters in the string in this problem are indexed from 1.

For example suppose s=abcdef. If he performs the first operation with i=3 then he appends cb to the front of s and the result will be cbabcdef. Performing the second operation on the resulted string with i=5 will yield cbabcdefedc.

Your task is to help Ringo make the entire string a palindrome by applying any of the two operations (in total) at most 30 times. The length of the resulting palindrome must not exceed 10^6

It is guaranteed that under these constraints there always is a solution. Also note you do not have to minimize neither the number of operations applied, nor the length of the resulting string, but they have to fit into the constraints.

Input

The only line contains the string S (3 ≤ |s| ≤ 10^5) of lowercase letters from the English alphabet.

Output

The first line should contain k (0≤ k ≤ 30) — the number of operations performed.

Each of the following k lines should describe an operation in form L i or R i. L represents the first operation, R represents the second operation, i represents the index chosen.

The length of the resulting palindrome must not exceed 10^6.

Examples

Input


abac


Output


2
R 2
R 5


Input


acccc


Output


2
L 4
L 2


Input


hannah


Output


0

Note

For the first example the following operations are performed:

abac → abacab → abacaba

The second sample performs the following operations: acccc → cccacccc → ccccacccc

The third example is already a palindrome so no operations are required.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.