vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are several (or no) spiders, butterflies, and dragonflies. 

In this kata, a spider has eight legs. A dragonfly or a butterfly has six legs. A __dragonfly__ has __two__ pairs of wings, while a __butterfly__ has __one__ pair of wings. __I am not sure whether they are biologically correct, but the values apply here. __

Given the number of total heads, legs, and __pairs of__ wings, please calculate numbers of each kind of bugs. Of course they are integers. 
_However, I do not guarantee that they are positive in the test cases. 
Please regard the minus numbers as cases that does not make sense. _

If answers make sense, return [n\_spider, n\_butterfly, n\_dragonfly]; 
else, please return [-1, -1, -1]. 

Example: 

cal\_n\_bug(3, 20, 3) = [1, 1, 1]
One spider, one butterfly, one dragonfly in total have three heads, twenty legs (8 for the spider, 6 for the butterfly, and 6 for the dragonfly), and _three pairs_ of wings (1 for the butterfly and 2 for the dragonfly).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kattappa wants Baahubali to master mathematics. They decide to play the following turn-based game.
They will be n x n grid M with random integers. Baahubali begins the game by crossing off an uncrossed row i of the grid. Now it's Kattappa turn and he crosses off an uncrossed column j of the grid. At the end of Kattappa's turn, Baahubali takes the number of candies in the i-th row and j-th column of M, call this value M (i, j), from Kattappa. (If M(i, j) is negative, then Baahubali gives M(i, j) candies to Kattappa.) The game continues alternating turns from Baahubali to Kattappa until the entire board is crossed off. Kattappa wants to know the maximum number of candies that Baahubali can win from him (or the minimum to lose if he cannot win) if both Baahubali and Kattappa play optimally. Help Baahubali find the solution.

Input:

First Line, number of test cases 1 ≤ t ≤ 20

Each test case starts with n (1 ≤ n ≤ 8), the size of the grid

Then follow n lines containing n numbers separated by spaces describing M. We call the j-th number on i-th line M (i, j) -1000 ≤ M(i,j) ≤ 1000

Output:

For each test case, print the maximum number of candies that Baahubali can win from Kattappa. If he cannot win, print the negative number indicating the minimum number of candies he loses.

SAMPLE INPUT
3
2
10 10
-5 -5
2
10 -5
10 -5
2
10 -5
-5 10

SAMPLE OUTPUT
5
5
-10

Explanation

Case 2:
Baahubali selects row 1 (answer doesn't change if row 2 is selected), Kattappa selects second column as -5 is minimum. So the current result is -5.
The only column and row left to be chosen is 10 i.e, second row first column. So the final result is -5 + 10 = 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A geyser has a capacity of X litres of water and a bucket has a capacity of Y litres of water.

One person requires exactly 2 buckets of water to take a bath. Find the maximum number of people that can take bath using water from one completely filled geyser..

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

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains a single line of input, two integers X, Y.

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

For each test case, output the maximum number of people that can take bath.

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

$1 ≤ T ≤ 1000$
$1 ≤ X, Y ≤ 100$

----- Sample Input 1 ------ 
4
10 6
25 1
100 10
30 40

----- Sample Output 1 ------ 
0
12
5
0

----- explanation 1 ------ 
Test Case $1$: One bucket has a capacity of $6$ litres. This means that one person requires $2\cdot 6 = 12$ litres of water to take a bath. Since this is less than the total water present in geyser, $0$ people can take bath.

Test Case $2$: One bucket has a capacity of $1$ litre. This means that one person requires $2\cdot 1 = 2$ litres of water to take a bath. The total amount of water present in geyser is $25$ litres. Thus, $12$ people can take bath. Note that $1$ litre water would remain unused in the geyser.

Test Case $3$: One bucket has a capacity of $10$ litres. This means that one person requires $2\cdot 10 = 20$ litres of water to take a bath. The total amount of water present in geyser is $100$ litres. Thus, $5$ people can take bath. Note that $0$ litres of water would remain unused in the geyser after this.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Iahub and Sorin are the best competitive programmers in their town. However, they can't both qualify to an important contest. The selection will be made with the help of a single problem. Blatnatalag, a friend of Iahub, managed to get hold of the problem before the contest. Because he wants to make sure Iahub will be the one qualified, he tells Iahub the following task.

You're given an (1-based) array *a* with *n* elements. Let's define function *f*(*i*,<=*j*) (1<=≤<=*i*,<=*j*<=≤<=*n*) as (*i*<=-<=*j*)2<=+<=*g*(*i*,<=*j*)2. Function g is calculated by the following pseudo-code:

Find a value *min**i*<=≠<=*j*  *f*(*i*,<=*j*).

Probably by now Iahub already figured out the solution to this problem. Can you?

Input Specification:
The first line of input contains a single integer *n* (2<=≤<=*n*<=≤<=100000). Next line contains *n* integers *a*[1], *a*[2], ..., *a*[*n*] (<=-<=104<=≤<=*a*[*i*]<=≤<=104).

Output Specification:
Output a single integer — the value of *min**i*<=≠<=*j*  *f*(*i*,<=*j*).

Demo Input:
['4\n1 0 0 -1\n', '2\n1 -1\n']

Demo Output:
['1\n', '2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Indian bank issues coins in 4 denominations, ₹1, ₹2, ₹5 and ₹10. 

Given a limited supply of each of the above denominations, in how many ways can you sum them up to a total of ₹N?

Input Format 

The first line contains an integer T (number of testcases). 
Each testcase contains 2 lines. The first line contains integer N (sum to be achieved) 

A, B, C and D in the next line, each representing the number of ₹1, ₹2, ₹5 and ₹10 coins respectively. 

Output Format 

Output the number of ways in which we can achieve the sum N.   

Constraints 

1 <= T <= 150 

1 <= N <= 1000 

1 <= A <= 10000 

1 <= B,C,D <= 1000  

Sample Input  

2
15
2 3 1 1
12
2 2 1 1

Sample Output

2
2

Explanation 

In the first case we need to find the different ways to total to 15. 
We can use one ₹10 coin and one ₹5 coin  or one ₹10 coin two ₹2 coin and one ₹1 coin. Proceed similarly for the second case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Have you ever used the chat application QQ? Well, in a chat group of QQ, administrators can muzzle a user for days.

In Boboniu's chat group, there's a person called Du Yi who likes to make fun of Boboniu every day.

Du will chat in the group for $n$ days. On the $i$-th day:  If Du can speak, he'll make fun of Boboniu with fun factor $a_i$. But after that, he may be muzzled depending on Boboniu's mood.  Otherwise, Du won't do anything. 

Boboniu's mood is a constant $m$. On the $i$-th day:  If Du can speak and $a_i>m$, then Boboniu will be angry and muzzle him for $d$ days, which means that Du won't be able to speak on the $i+1, i+2, \cdots, \min(i+d,n)$-th days.  Otherwise, Boboniu won't do anything. 

The total fun factor is the sum of the fun factors on the days when Du can speak.

Du asked you to find the maximum total fun factor among all possible permutations of $a$.


-----Input-----

The first line contains three integers $n$, $d$ and $m$ ($1\le d\le n\le 10^5,0\le m\le 10^9$).

The next line contains $n$ integers $a_1, a_2, \ldots,a_n$ ($0\le a_i\le 10^9$).


-----Output-----

Print one integer: the maximum total fun factor among all permutations of $a$.


-----Examples-----
Input
5 2 11
8 10 15 23 5

Output
48

Input
20 2 16
20 5 8 2 18 16 2 16 16 1 5 16 2 13 6 16 4 17 21 7

Output
195



-----Note-----

In the first example, you can set $a'=[15, 5, 8, 10, 23]$. Then Du's chatting record will be:  Make fun of Boboniu with fun factor $15$.  Be muzzled.  Be muzzled.  Make fun of Boboniu with fun factor $10$.  Make fun of Boboniu with fun factor $23$. 

Thus the total fun factor is $48$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Compute A \times B.

-----Constraints-----
 - 1 \leq A \leq 100
 - 1 \leq B \leq 100
 - All values in input are integers.

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

-----Output-----
Print the value A \times B as an integer.

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

-----Sample Output-----
10

We have 2 \times 5 = 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a directed acyclic graph G, consisting of n vertexes, numbered from 0 to n - 1. The graph contains n edges numbered from 0 to n - 1. An edge with number i connects vertexes i and (i + 1) mod n, and it can be directed in either direction (from i to (i + 1) mod n, or vise versa).

Operation x mod y means taking the remainder after dividing number x by number y.

Let's call two vertexes u and v in graph G comparable if the graph contains a path either from u to v or from v to u. We'll assume that an antichain is a set of vertexes of graph G, where any two distinct vertexes are not comparable. The size of an antichain is the number of vertexes in the corresponding set. An antichain is maximum if the graph doesn't have antichains of a larger size.

Your task is to find the size of the maximum antichain in graph G.

Input

The first line contains the sequence of characters s0s1... sn - 1 (2 ≤ n ≤ 106), consisting of numbers zero and one. The length of the line (number n) corresponds to the number of vertexes and edges in graph G. If character si (i ≥ 0) equals 0, then the edge between vertexes i and (i + 1) mod n is directed from the i-th vertex to the (i + 1) mod n-th one, otherwise — to the opposite point.

It is guaranteed that the given graph is acyclic.

Output

Print a single integer — the size of the maximum antichain of graph G.

Examples

Input

001


Output

1


Input

110010


Output

3

Note

Consider the first test sample. The graph's G edges are: 0 → 1, 1 → 2, 0 → 2. We can choose the set of vertexes [0] as the maximum antichain. We cannot choose an antichain of larger size.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Somnath is supposed to submit an assignment for his semester, but The Code Goddess cursed his keyboard. While typing the “HOME” and “END” keys gets pressed internally in a random manner.
Since Somnath is in a hurry and he couldn't rectify his assignment. Can you help him with recovering the original text?

Input Format
The first line consists of a single integer T.
Next T lines contains a single string S in each line containing any alphabets and underscores (no spaces) and two special symbols “<” indicating HOME button is pressed and “>” indicating END button is pressed.

Output Format
For each string S output a single line containing the rectified text.

Constraints

1 ≤ T ≤ 10^5 
1 ≤ |S| ≤ 1000

SAMPLE INPUT
2  
_even_debug<Do_you>_bro  
_beautiful_versions_>of_<_perfection_only>brokenness<There_is_no

SAMPLE OUTPUT
Do_you_even_debug_bro  
There_is_no_perfection_only_beautiful_versions_of_brokenness

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: On Segment's Own Points

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Our old friend Alexey has finally entered the University of City N — the Berland capital. Alexey expected his father to get him a place to live in but his father said it was high time for Alexey to practice some financial independence. So, Alexey is living in a dorm. 

The dorm has exactly one straight dryer — a 100 centimeter long rope to hang clothes on. The dryer has got a coordinate system installed: the leftmost end of the dryer has coordinate 0, and the opposite end has coordinate 100. Overall, the university has *n* students. Dean's office allows *i*-th student to use the segment (*l**i*,<=*r**i*) of the dryer. However, the dean's office actions are contradictory and now one part of the dryer can belong to multiple students!

Alexey don't like when someone touch his clothes. That's why he want make it impossible to someone clothes touch his ones. So Alexey wonders: what is the total length of the parts of the dryer that he may use in a such way that clothes of the others (*n*<=-<=1) students aren't drying there. Help him! Note that Alexey, as the most respected student, has number 1.

Input Specification:
The first line contains a positive integer *n* (1<=≤<=*n*<=≤<=100). The (*i*<=+<=1)-th line contains integers *l**i* and *r**i* (0<=≤<=*l**i*<=&lt;<=*r**i*<=≤<=100) — the endpoints of the corresponding segment for the *i*-th student.

Output Specification:
On a single line print a single number *k*, equal to the sum of lengths of the parts of the dryer which are inside Alexey's segment and are outside all other segments.

Demo Input:
['3\n0 5\n2 8\n1 6\n', '3\n0 10\n1 5\n7 15\n']

Demo Output:
['1\n', '3\n']

Note:
Note that it's not important are clothes drying on the touching segments (e.g. (0, 1) and (1, 2)) considered to be touching or not because you need to find the length of segments.

In the first test sample Alexey may use the only segment (0, 1). In such case his clothes will not touch clothes on the segments (1, 6) and (2, 8). The length of segment (0, 1) is 1.

In the second test sample Alexey may dry his clothes on segments (0, 1) and (5, 7). Overall length of these segments is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem the input will consist of a number of lines of English text consisting of the letters of the English alphabet, the punctuation marks ' (apostrophe), . (full stop), , (comma), ; (semicolon), :(colon) and white space characters (blank, newline).
Your task is print the words in the text in lexicographic order (that is, dictionary order). Each word should appear exactly once in your list. You can ignore the case (for instance, "The" and "the" are to be treated as the same word). There should be no uppercase letters in the output.
For example, consider the following candidate for the input text: 
This is a sample piece of text to illustrate this 
problem.

The corresponding output would read as:
a
illustrate
is
of
piece
problem
sample
text
this
to

-----Input format-----
- The first line of input contains a single integer $N$, indicating the number of lines in the input.
- This is followed by $N$ lines of input text.

-----Output format-----
- The first line of output contains a single integer $M$ indicating the number of distinct words in the given text. 
- The next $M$ lines list out these words in lexicographic order.

-----Constraints-----
- $1 \leq N \leq 10000$
- There are at most 80 characters in each line.
- There are at the most 1000 distinct words in the given text.

-----Sample Input-----
2
This is a sample piece of text to illustrate this 
problem. 

-----Sample Output-----
10
a
illustrate
is
of
piece
problem
sample
text
this
to

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The array a with n integers is given. Let's call the sequence of one or more consecutive elements in a segment. Also let's call the segment k-good if it contains no more than k different values.

Find any longest k-good segment.

As the input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input

The first line contains two integers n, k (1 ≤ k ≤ n ≤ 5·105) — the number of elements in a and the parameter k.

The second line contains n integers ai (0 ≤ ai ≤ 106) — the elements of the array a.

Output

Print two integers l, r (1 ≤ l ≤ r ≤ n) — the index of the left and the index of the right ends of some k-good longest segment. If there are several longest segments you can print any of them. The elements in a are numbered from 1 to n from left to right.

Examples

Input

5 5
1 2 3 4 5


Output

1 5


Input

9 3
6 5 1 2 3 2 1 4 5


Output

3 7


Input

3 1
1 2 3


Output

1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One must train much to do well on wizardry contests. So, there are numerous wizardry schools and magic fees.

One of such magic schools consists of n tours. A winner of each tour gets a huge prize. The school is organised quite far away, so one will have to take all the prizes home in one go. And the bags that you've brought with you have space for no more than k huge prizes.

Besides the fact that you want to take all the prizes home, you also want to perform well. You will consider your performance good if you win at least l tours.

In fact, years of organizing contests proved to the organizers that transporting huge prizes is an issue for the participants. Alas, no one has ever invented a spell that would shrink the prizes... So, here's the solution: for some tours the winner gets a bag instead of a huge prize. Each bag is characterized by number ai — the number of huge prizes that will fit into it.

You already know the subject of all tours, so you can estimate the probability pi of winning the i-th tour. You cannot skip the tour under any circumstances.

Find the probability that you will perform well on the contest and will be able to take all won prizes home (that is, that you will be able to fit all the huge prizes that you won into the bags that you either won or brought from home).

Input

The first line contains three integers n, l, k (1 ≤ n ≤ 200, 0 ≤ l, k ≤ 200) — the number of tours, the minimum number of tours to win, and the number of prizes that you can fit in the bags brought from home, correspondingly.

The second line contains n space-separated integers, pi (0 ≤ pi ≤ 100) — the probability to win the i-th tour, in percents.

The third line contains n space-separated integers, ai (1 ≤ ai ≤ 200) — the capacity of the bag that will be awarded to you for winning the i-th tour, or else -1, if the prize for the i-th tour is a huge prize and not a bag.

Output

Print a single real number — the answer to the problem. The answer will be accepted if the absolute or relative error does not exceed 10 - 6.

Examples

Input

3 1 0
10 20 30
-1 -1 2


Output

0.300000000000


Input

1 1 1
100
123


Output

1.000000000000

Note

In the first sample we need either win no tour or win the third one. If we win nothing we wouldn't perform well. So, we must to win the third tour. Other conditions will be satisfied in this case. Probability of wining the third tour is 0.3.

In the second sample we win the only tour with probability 1.0, and go back home with bag for it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a pot and N ingredients. Each ingredient has a real number parameter called value, and the value of the i-th ingredient (1 \leq i \leq N) is v_i.

When you put two ingredients in the pot, they will vanish and result in the formation of a new ingredient. The value of the new ingredient will be (x + y) / 2 where x and y are the values of the ingredients consumed, and you can put this ingredient again in the pot.

After you compose ingredients in this way N-1 times, you will end up with one ingredient. Find the maximum possible value of this ingredient.

Constraints

* 2 \leq N \leq 50
* 1 \leq v_i \leq 1000
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
v_1 v_2 \ldots v_N


Output

Print a decimal number (or an integer) representing the maximum possible value of the last ingredient remaining.

Your output will be judged correct when its absolute or relative error from the judge's output is at most 10^{-5}.

Examples

Input

2
3 4


Output

3.5


Input

3
500 300 200


Output

375


Input

5
138 138 138 138 138


Output

138

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two players are playing a game of Tower Breakers! Player $1$ always moves first, and both players always play optimally.The rules of the game are as follows:   

Initially there are $n$ towers.
Each tower is of height $m$.   
The players move in alternating turns. 
In each turn, a player can choose a tower of height $x$ and reduce its height to $y$, where $1\leq y<x$ and $y$ evenly divides $x$.  
If the current player is unable to make a move, they lose the game.   

Given the values of $n$ and $m$, determine which player will win. If the first player wins, return $1$.  Otherwise, return $2$.  

Example. 
$n=2$ 

$m=6$    

There are $2$ towers, each $6$ units tall.  Player $1$ has a choice of two moves: 

- remove $3$ pieces from a tower to leave $6$ as $6 \quad modulo \quad 3=0$ 

- remove $5$ pieces to leave $1$   

Let Player $1$ remove $3$. Now the towers are $3$ and $6$ units tall.

Player $2$ matches the move. Now the towers are both $3$ units tall. 

Now Player $1$ has only one move. 

Player $1$ removes $2$ pieces leaving $1$.  Towers are $1$ and $2$ units tall. 

Player $2$ matches again.  Towers are both $1$ unit tall.  

Player $1$ has no move and loses. Return $2$.

Function Description  

Complete the towerBreakers function in the editor below.   

towerBreakers has the following paramter(s):  

int n: the number of towers  
int m: the height of each tower  

Returns  

int: the winner of the game   

Input Format

The first line contains a single integer $t$, the number of test cases. 

Each of the next $t$ lines describes a test case in the form of $2$ space-separated integers, $n$ and $m$.  

Constraints

$1\leq t\leq100$
$1\leq n,m\leq10^6$

Sample Input
STDIN   Function
-----   --------
2       t = 2
2 2     n = 2, m = 2
1 4     n = 1, m = 4

Sample Output
2
1

Explanation

We'll refer to player $1$ as $P1$ and player $2$ as $P2$

In the first test case, $P1$ chooses one of the two towers and reduces it to $1$. Then $P2$ reduces the remaining tower to a height of $1$. As both towers now have height $1$, $P1$ cannot make a move so $P2$ is the winner.

In the second test case, there is only one tower of height $4$. $P1$ can reduce it to a height of either $1$ or $2$. $P1$ chooses $1$ as both players always choose optimally. Because $P2$ has no possible move, $P1$ wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An encoded string S is given.  To find and write the decoded string to a tape, the encoded string is read one character at a time and the following steps are taken:

If the character read is a letter, that letter is written onto the tape.
If the character read is a digit (say d), the entire current tape is repeatedly written d-1 more times in total.

Now for some encoded string S, and an index K, find and return the K-th letter (1 indexed) in the decoded string.
 

Example 1:
Input: S = "leet2code3", K = 10
Output: "o"
Explanation: 
The decoded string is "leetleetcodeleetleetcodeleetleetcode".
The 10th letter in the string is "o".


Example 2:
Input: S = "ha22", K = 5
Output: "h"
Explanation: 
The decoded string is "hahahaha".  The 5th letter is "h".


Example 3:
Input: S = "a2345678999999999999999", K = 1
Output: "a"
Explanation: 
The decoded string is "a" repeated 8301530446056247680 times.  The 1st letter is "a".




 
Constraints:

2 <= S.length <= 100
S will only contain lowercase letters and digits 2 through 9.
S starts with a letter.
1 <= K <= 10^9
It's guaranteed that K is less than or equal to the length of the decoded string.
The decoded string is guaranteed to have less than 2^63 letters.

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