vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: BerOS file system

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
The new operating system BerOS has a nice feature. It is possible to use any number of characters '/' as a delimiter in path instead of one traditional '/'. For example, strings //usr///local//nginx/sbin// and /usr/local/nginx///sbin are equivalent. The character '/' (or some sequence of such characters) at the end of the path is required only in case of the path to the root directory, which can be represented as single character '/'.

A path called normalized if it contains the smallest possible number of characters '/'.

Your task is to transform a given path to the normalized form.

Input Specification:
The first line of the input contains only lowercase Latin letters and character '/' — the path to some directory. All paths start with at least one character '/'. The length of the given line is no more than 100 characters, it is not empty.

Output Specification:
The path in normalized form.

Demo Input:
['//usr///local//nginx/sbin\n']

Demo Output:
['/usr/local/nginx/sbin\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A of length N. 

The *interesting value* of a subarray is defined as the product of the maximum and minimum elements of the subarray.

Find the minimum and maximum *interesting value* over all subarrays for the given array.

Note: A subarray is obtained by deletion of several (possibly zero) elements from the beginning of the array and several (possibly zero) elements from the end of the array.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first line of each test case contains an integer N - the length of the array A.
- The second line of each test case contains N space-separated integers A_{1},A_{2},\ldots,A_{N}.

------ Output Format ------ 

For each test case, output two space-separated integers on a new line the minimum and maximum *interesting value* over all subarrays for the given array.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$-10^{9} ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
2
2 2
3
5 0 9

----- Sample Output 1 ------ 
4 4
0 81
----- explanation 1 ------ 
Test case $1$: The minimum *interesting value* possible is $4$. A subarray with *interesting value* equal to $4$ is $[2,2]$. Here, both minimum and maximum elements of the subarray are $2$. It can be proven that no subarray of the array has *interesting value* less than $4$.  
The maximum *interesting value* possible is $4$. A subarray with *interesting value* equal to $4$ is $[2,2]$. Here, both minimum and maximum elements of the subarray are $2$. It can be proven that no subarray of the array has *interesting value* greater than $4$.

Test case $2$: The minimum *interesting value* possible is $0$. A subarray with *interesting value* equal to $0$ is $[5, 0, 9]$. Here, minimum element is $0$ and maximum element is $9$. It can be proven that no subarray of the array has *interesting value* less than $0$.  
The maximum *interesting value* possible is $81$. A subarray with *interesting value* equal to $81$ is $[9]$. Here, both minimum and maximum elements of the subarray are $9$. It can be proven that no subarray of the array has *interesting value* more than $81$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya is a CEO of a big construction company. And as any other big boss he has a spacious, richly furnished office with two crystal chandeliers. To stay motivated Vasya needs the color of light at his office to change every day. That's why he ordered both chandeliers that can change its color cyclically. For example: red – brown – yellow – red – brown – yellow and so on.

There are many chandeliers that differs in color set or order of colors. And the person responsible for the light made a critical mistake — they bought two different chandeliers.

Since chandeliers are different, some days they will have the same color, but some days — different. Of course, it looks poor and only annoys Vasya. As a result, at the $k$-th time when chandeliers will light with different colors, Vasya will become very angry and, most probably, will fire the person who bought chandeliers.

Your task is to calculate the day, when it happens (counting from the day chandeliers were installed). You can think that Vasya works every day without weekends and days off.


-----Input-----

The first line contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 500000$; $1 \le k \le 10^{12}$) — the number of colors in the first and the second chandeliers and how many times colors should differ to anger Vasya.

The second line contains $n$ different integers $a_i$ ($1 \le a_i \le 2 \cdot \max(n, m)$) that describe the first chandelier's sequence of colors.

The third line contains $m$ different integers $b_j$ ($1 \le b_i \le 2 \cdot \max(n, m)$) that describe the second chandelier's sequence of colors.

At the $i$-th day, the first chandelier has a color $a_x$, where $x = ((i - 1) \mod n) + 1)$ and the second one has a color $b_y$, where $y = ((i - 1) \mod m) + 1)$.

It's guaranteed that sequence $a$ differs from sequence $b$, so there are will be days when colors of chandeliers differs.


-----Output-----

Print the single integer — the index of day when Vasya will become angry.


-----Examples-----

Input
4 2 4
4 2 3 1
2 1
Output
5
Input
3 8 41
1 3 2
1 6 4 3 5 7 2 8
Output
47
Input
1 2 31
1
1 2
Output
62


-----Note-----

In the first example, the chandeliers will have different colors at days $1$, $2$, $3$ and $5$. That's why the answer is $5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')
Each vowel 'a' may only be followed by an 'e'.
Each vowel 'e' may only be followed by an 'a' or an 'i'.
Each vowel 'i' may not be followed by another 'i'.
Each vowel 'o' may only be followed by an 'i' or a 'u'.
Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.
 
Example 1:
Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2:
Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3: 
Input: n = 5
Output: 68
 
Constraints:

1 <= n <= 2 * 10^4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a chess board with $n$ rows and $n$ columns. Initially all cells of the board are empty, and you have to put a white or a black knight into each cell of the board.

A knight is a chess piece that can attack a piece in cell ($x_2$, $y_2$) from the cell ($x_1$, $y_1$) if one of the following conditions is met:

  $|x_1 - x_2| = 2$ and $|y_1 - y_2| = 1$, or  $|x_1 - x_2| = 1$ and $|y_1 - y_2| = 2$. 

Here are some examples of which cells knight can attack. In each of the following pictures, if the knight is currently in the blue cell, it can attack all red cells (and only them).

 [Image] 

A duel of knights is a pair of knights of different colors such that these knights attack each other. You have to put a knight (a white one or a black one) into each cell in such a way that the number of duels is maximum possible.


-----Input-----

The first line contains one integer $n$ ($3 \le n \le 100$) — the number of rows (and columns) in the board.


-----Output-----

Print $n$ lines with $n$ characters in each line. The $j$-th character in the $i$-th line should be W, if the cell ($i$, $j$) contains a white knight, or B, if it contains a black knight. The number of duels should be maximum possible. If there are multiple optimal answers, print any of them.


-----Example-----
Input
3

Output
WBW
BBB
WBW



-----Note-----

In the first example, there are $8$ duels:

  the white knight in ($1$, $1$) attacks the black knight in ($3$, $2$);  the white knight in ($1$, $1$) attacks the black knight in ($2$, $3$);  the white knight in ($1$, $3$) attacks the black knight in ($3$, $2$);  the white knight in ($1$, $3$) attacks the black knight in ($2$, $1$);  the white knight in ($3$, $1$) attacks the black knight in ($1$, $2$);  the white knight in ($3$, $1$) attacks the black knight in ($2$, $3$);  the white knight in ($3$, $3$) attacks the black knight in ($1$, $2$);  the white knight in ($3$, $3$) attacks the black knight in ($2$, $1$).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array A1,A2...AN, you have to print the size of the largest contiguous subarray such that
GCD of all integers in that subarray is 1.
Formally, For a subarray Ai,Ai+1...Aj where 1 ≤ i < j ≤ N to be valid: GCD(Ai,Ai+1...Aj) should be 1. You have to print the size of the largest valid subarray.
If no valid subarray exists, output -1.
Note:A single element is not considered as a subarray according to the definition of this problem.

Input
First line contains T, the number of testcases. Each testcase consists of N in one line followed by N integers in the next line.

Output
For each testcase, print the required answer in one line.

Constraints

1 ≤ T ≤ 10
2 ≤ N ≤ 10^5
1 ≤ Ai ≤ 10^5


Example
Input:
2
2
7 2
3
2 2 4

Output:
2
-1

Explanation

Example case 1.GCD(2,7)=1. So the subarray [A1,A2] is valid.
Example case 2.No subarray satisfies.

Note: Use scanf/print instead of cin/cout. Large input files.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three integers A, B and C. Find the minimum number of operations required to make A, B and C all equal by repeatedly performing the following two kinds of operations in any order:
 - Choose two among A, B and C, then increase both by 1.
 - Choose one among A, B and C, then increase it by 2.
It can be proved that we can always make A, B and C all equal by repeatedly performing these operations.

-----Constraints-----
 - 0 \leq A,B,C \leq 50
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
A B C

-----Output-----
Print the minimum number of operations required to make A, B and C all equal.

-----Sample Input-----
2 5 4

-----Sample Output-----
2

We can make A, B and C all equal by the following operations:
 - Increase A and C by 1. Now, A, B, C are 3, 5, 5, respectively.
 - Increase A by 2. Now, A, B, C are 5, 5, 5, respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Levko loves tables that consist of n rows and n columns very much. He especially loves beautiful tables. A table is beautiful to Levko if the sum of elements in each row and column of the table equals k.

Unfortunately, he doesn't know any such table. Your task is to help him to find at least one of them. 


-----Input-----

The single line contains two integers, n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1000).


-----Output-----

Print any beautiful table. Levko doesn't like too big numbers, so all elements of the table mustn't exceed 1000 in their absolute value.

If there are multiple suitable tables, you are allowed to print any of them.


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

Output
1 3
3 1

Input
4 7

Output
2 1 0 4
4 0 2 1
1 3 3 0
0 3 2 2



-----Note-----

In the first sample the sum in the first row is 1 + 3 = 4, in the second row — 3 + 1 = 4, in the first column — 1 + 3 = 4 and in the second column — 3 + 1 = 4. There are other beautiful tables for this sample.

In the second sample the sum of elements in each row and each column equals 7. Besides, there are other tables that meet the statement requirements.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Counting Arrays

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given two positive integer numbers *x* and *y*. An array *F* is called an *y*-factorization of *x* iff the following conditions are met:
 -  There are *y* elements in *F*, and all of them are integer numbers; -  . 
You have to count the number of pairwise distinct arrays that are *y*-factorizations of *x*. Two arrays *A* and *B* are considered different iff there exists at least one index *i* (1<=≤<=*i*<=≤<=*y*) such that *A**i*<=≠<=*B**i*. Since the answer can be very large, print it modulo 109<=+<=7.

Input Specification:
The first line contains one integer *q* (1<=≤<=*q*<=≤<=105) — the number of testcases to solve.

Then *q* lines follow, each containing two integers *x**i* and *y**i* (1<=≤<=*x**i*,<=*y**i*<=≤<=106). Each of these lines represents a testcase.

Output Specification:
Print *q* integers. *i*-th integer has to be equal to the number of *y**i*-factorizations of *x**i* modulo 109<=+<=7.

Demo Input:
['2\n6 3\n4 2\n']

Demo Output:
['36\n6\n']

Note:
In the second testcase of the example there are six *y*-factorizations:
 -  { - 4,  - 1}; -  { - 2,  - 2}; -  { - 1,  - 4}; -  {1, 4}; -  {2, 2}; -  {4, 1}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Ilya and Matrix

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ilya is a very good-natured lion. He likes maths. Of all mathematical objects, his favourite one is matrices. Now he's faced a complicated matrix problem he needs to solve.

He's got a square 2*n*<=×<=2*n*-sized matrix and 4*n* integers. You need to arrange all these numbers in the matrix (put each number in a single individual cell) so that the beauty of the resulting matrix with numbers is maximum.

The beauty of a 2*n*<=×<=2*n*-sized matrix is an integer, obtained by the following algorithm:
 1.  Find the maximum element in the matrix. Let's denote it as *m*. 1.  If *n*<==<=0, then the beauty of the matrix equals *m*. Otherwise, a matrix can be split into 4 non-intersecting 2*n*<=-<=1<=×<=2*n*<=-<=1-sized submatrices, then the beauty of the matrix equals the sum of number *m* and other four beauties of the described submatrices. 
As you can see, the algorithm is recursive.

Help Ilya, solve the problem and print the resulting maximum beauty of the matrix.

Input Specification:
The first line contains integer 4*n* (1<=≤<=4*n*<=≤<=2·106). The next line contains 4*n* integers *a**i* (1<=≤<=*a**i*<=≤<=109) — the numbers you need to arrange in the 2*n*<=×<=2*n*-sized matrix.

Output Specification:
On a single line print the maximum value of the beauty of the described matrix.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Demo Input:
['1\n13\n', '4\n1 2 3 4\n']

Demo Output:
['13\n', '14\n']

Note:
Consider the second sample. You need to arrange the numbers in the matrix as follows:

Then the beauty of the matrix will equal: 4 + 1 + 2 + 3 + 4 = 14.

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

Infinite Chronicle -Princess Castle- is a simple role-playing game. There are $n + 1$ checkpoints, numbered $0$ through $n$, and for each $i = 1, 2, \ldots, n$, there is a unique one-way road running from checkpoint $i - 1$ to $i$. The game starts at checkpoint $0$ and ends at checkpoint $n$. Evil monsters will appear on the roads and the hero will have battles against them. You can save your game progress at any checkpoint; if you lose a battle, you can restart the game from the checkpoint where you have saved for the last time. At the beginning of the game, the progress is automatically saved at checkpoint $0$ with no time.

Rabbit Hanako is fond of this game and now interested in speedrunning. Although Hanako is an expert of the game, she cannot always win the battles because of random factors. For each $i$, she estimated the probability $p_i$ to win all the battles along the road from checkpoint $i - 1$ to $i$. Everytime she starts at checkpoint $i - 1$, after exactly one miniutes, she will be at checkpoint $i$ with probability $p_i$ and where she saved for the last time with probability $1 - p_i$.

What puzzles Hanako is that it also takes one minute (!) to save your progress at a checkpoint, so it might be a good idea to pass some checkpoints without saving in order to proceed quickly. The task is to compute the minimum possible expected time needed to complete the game.

Input

The input consists of multiple datasets. The number of datasets is no more than $50$. Each dataset has two lines: the first line contains an integer $n$ ($1 \le n \le 10^5$), representing the number of roads, and the second line contains $n$ numbers $p_1, p_2, \ldots, p_n$ ($0 \lt p_i \le 1$), representing the winning probabilities. Each $p_i$ has exactly two digits after the decimal point. The end of input is denoted as a line containing only a single zero.

Output

For each dataset, display the minimum expected time in minutes with a relative error of at most $10^{-8}$ in a line.

Sample Input


2
0.50 0.40
2
0.70 0.60
4
0.99 1.00 1.00 0.01
0

Output for the Sample Input


5.5000000000
4.0476190476
104.0101010101





Example

Input

2
0.50 0.40
2
0.70 0.60
4
0.99 1.00 1.00 0.01
0


Output

5.5000000000
4.0476190476
104.0101010101

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The three friends, Kuro, Shiro, and Katie, met up again! It's time for a party...

What the cats do when they unite? Right, they have a party. Since they wanted to have as much fun as possible, they invited all their friends. Now $n$ cats are at the party, sitting in a circle and eating soup. The rules are simple: anyone having finished their soup leaves the circle.

Katie suddenly notices that whenever a cat leaves, the place where she was sitting becomes an empty space, which means the circle is divided into smaller continuous groups of cats sitting next to each other. At the moment Katie observes, there are $m$ cats who left the circle. This raises a question for Katie: what is the maximum possible number of groups the circle is divided into at the moment?

Could you help her with this curiosity?

You can see the examples and their descriptions with pictures in the "Note" section.


-----Input-----

The only line contains two integers $n$ and $m$ ($2 \leq n \leq 1000$, $0 \leq m \leq n$) — the initial number of cats at the party and the number of cats who left the circle at the moment Katie observes, respectively.


-----Output-----

Print a single integer — the maximum number of groups of cats at the moment Katie observes.


-----Examples-----
Input
7 4

Output
3

Input
6 2

Output
2

Input
3 0

Output
1

Input
2 2

Output
0



-----Note-----

In the first example, originally there are $7$ cats sitting as shown below, creating a single group: [Image] 

At the observed moment, $4$ cats have left the table. Suppose the cats $2$, $3$, $5$ and $7$ have left, then there are $3$ groups remaining. It is possible to show that it is the maximum possible number of groups remaining. [Image] 

In the second example, there are $6$ cats sitting as shown below: [Image] 

At the observed moment, $2$ cats have left the table. Suppose the cats numbered $3$ and $6$ left, then there will be $2$ groups remaining ($\{1, 2\}$ and $\{4, 5\}$). It is impossible to have more than $2$ groups of cats remaining. [Image] 

In the third example, no cats have left, so there is $1$ group consisting of all cats.

In the fourth example, all cats have left the circle, so there are $0$ groups.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Interesting drink

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasiliy likes to rest after a hard work, so you may often meet him in some bar nearby. As all programmers do, he loves the famous drink "Beecola", which can be bought in *n* different shops in the city. It's known that the price of one bottle in the shop *i* is equal to *x**i* coins.

Vasiliy plans to buy his favorite drink for *q* consecutive days. He knows, that on the *i*-th day he will be able to spent *m**i* coins. Now, for each of the days he want to know in how many different shops he can buy a bottle of "Beecola".

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=100<=000) — the number of shops in the city that sell Vasiliy's favourite drink.

The second line contains *n* integers *x**i* (1<=≤<=*x**i*<=≤<=100<=000) — prices of the bottles of the drink in the *i*-th shop.

The third line contains a single integer *q* (1<=≤<=*q*<=≤<=100<=000) — the number of days Vasiliy plans to buy the drink.

Then follow *q* lines each containing one integer *m**i* (1<=≤<=*m**i*<=≤<=109) — the number of coins Vasiliy can spent on the *i*-th day.

Output Specification:
Print *q* integers. The *i*-th of them should be equal to the number of shops where Vasiliy will be able to buy a bottle of the drink on the *i*-th day.

Demo Input:
['5\n3 10 8 6 11\n4\n1\n10\n3\n11\n']

Demo Output:
['0\n4\n1\n5\n']

Note:
On the first day, Vasiliy won't be able to buy a drink in any of the shops.

On the second day, Vasiliy can buy a drink in the shops 1, 2, 3 and 4.

On the third day, Vasiliy can buy a drink only in the shop number 1.

Finally, on the last day Vasiliy can buy a drink in any shop.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice has a string s. She really likes the letter "a". She calls a string good if strictly more than half of the characters in that string are "a"s. For example "aaabb", "axaa" are good strings, and "baca", "awwwa", "" (empty string) are not.

Alice can erase some characters from her string s. She would like to know what is the longest string remaining after erasing some characters (possibly zero) to get a good string. It is guaranteed that the string has at least one "a" in it, so the answer always exists.

Input

The first line contains a string s (1 ≤ |s| ≤ 50) consisting of lowercase English letters. It is guaranteed that there is at least one "a" in s.

Output

Print a single integer, the length of the longest good string that Alice can get after erasing some characters from s.

Examples

Input


xaxxxxa


Output


3


Input


aaabaa


Output


6

Note

In the first example, it's enough to erase any four of the "x"s. The answer is 3 since that is the maximum number of characters that can remain.

In the second example, we don't need to erase any characters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the performance version of [this kata](https://www.codewars.com/kata/59afff65f1c8274f270020f5).

---

Imagine two rings with numbers on them. The inner ring spins clockwise and the outer ring spins anti-clockwise. We start with both rings aligned on 0 at the top, and on each move we spin each ring by 1. How many moves will it take before both rings show the same number at the top again?

The inner ring has integers from 0 to innerMax and the outer ring has integers from 0 to outerMax, where innerMax and outerMax are integers >= 1.

```
e.g. if innerMax is 2 and outerMax is 3 then after
1 move: inner = 2, outer = 1
2 moves: inner = 1, outer = 2
3 moves: inner = 0, outer = 3
4 moves: inner = 2, outer = 0
5 moves: inner = 1, outer = 1
Therefore it takes 5 moves for the two rings to reach the same number
Therefore spinningRings(2, 3) = 5
```
```
e.g. if innerMax is 3 and outerMax is 2 then after
1 move: inner = 3, outer = 1
2 moves: inner = 2, outer = 2
Therefore it takes 2 moves for the two rings to reach the same number
spinningRings(3, 2) = 2
```

---

Test input range:

- `100` tests with `1 <= innerMax, outerMax <= 10000`
- `400` tests with `1 <= innerMax, outerMax <= 2^48`

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