vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The recent schoolboard elections were hotly contested: a proposal to swap school start times for elementary and high school students, a controversial new dress code proposal that bans athletic clothes in school, and a proposal to raise real-estate taxes to pay for a new football practice facility, and the list goes on and on. It is now hours after the polls have closed and a winner has yet to emerge! 

In their desperation, the election officials turn to you and ask you to write a program to count the vote!

-----Input-----
The input consists of a single test case, which is a list of votes cast. Each line in the input contains the name of a candidate for whom a vote was cast. A name may consist of multiple words, separated by spaces. Words contain letters or hyphens, but no other punctuation characters. There will be at least $2$ votes on the list. The list of votes ends with a single line containing the characters ***. This line should not be counted. There can be up to $100000$ valid votes.

-----Output-----
If a candidate obtained a simple or absolute majority of all votes cast (that is, more than any other candidate), output the name of this candidate! If no candidate obtained a simple majority, output: “Runoff!” (don’t forget to include the exclamation mark!)

-----Examples-----
Sample Input:
Penny Franklin
Marti Graham
Connie Froggatt
Joseph Ivers
Connie Froggatt
Penny Franklin
Connie Froggatt
Bruce Stanger
Connie Froggatt
Barbara Skinner
Barbara Skinner
***
Sample Output:
Connie Froggatt

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of n integers a1, a2, ..., an. 

Determine a real number x such that the weakness of the sequence a1 - x, a2 - x, ..., an - x is as small as possible.

The weakness of a sequence is defined as the maximum value of the poorness over all segments (contiguous subsequences) of a sequence.

The poorness of a segment is defined as the absolute value of sum of the elements of segment.

Input

The first line contains one integer n (1 ≤ n ≤ 200 000), the length of a sequence.

The second line contains n integers a1, a2, ..., an (|ai| ≤ 10 000).

Output

Output a real number denoting the minimum possible weakness of a1 - x, a2 - x, ..., an - x. Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

Examples

Input

3
1 2 3


Output

1.000000000000000


Input

4
1 2 3 4


Output

2.000000000000000


Input

10
1 10 2 9 3 8 4 7 5 6


Output

4.500000000000000

Note

For the first case, the optimal value of x is 2 so the sequence becomes  - 1, 0, 1 and the max poorness occurs at the segment "-1" or segment "1". The poorness value (answer) equals to 1 in this case. 

For the second sample the optimal value of x is 2.5 so the sequence becomes  - 1.5, - 0.5, 0.5, 1.5 and the max poorness occurs on segment "-1.5 -0.5" or "0.5 1.5". The poorness value (answer) equals to 2 in this case.

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

An undirected graph with positive values ​​at the vertices is given. The vertices are numbered from 1 to N, and the i-th vertex has a value of w_i. You can start from the first vertex and move on the graph with the constraint that you cannot pass the edge that you just passed. At each vertex, you can get the score of the value that the vertex has only when you visit it for the first time.

Find the maximum sum of the points you can get.

Constraints

* 1 ≤ N ≤ 100000
* N − 1 ≤ M ≤ 100000
* 1 ≤ w_i ≤ 1000
* 1 ≤ u_i, v_i ≤ N
* There are no multiple edges or self edges
* The graph is concatenated



Input Format

Input is given from standard input in the following format.


N M
w_1 w_2 ... w_N
u_1 v_1
u_2 v_2
...
u_M v_M


In the first line, the number of vertices N of the graph and the integer M representing the number of edges are entered.
The value w_i of each vertex is entered in the second line.
In addition, the number of the two vertices connected by each side is entered in the M line.


Output Format

Print the answer on one line.

Sample Input 1


6 6
1 2 3 4 5 6
1 2
twenty three
3 4
14
4 5
5 6


Sample Output 1


twenty one


<image>
You can collect the points of all vertices by going from vertices 1 → 2 → 3 → 4 → 5 → 6.

Sample Input 2


7 8
1 3 3 5 2 2 3
1 2
twenty three
3 1
14
1 7
1 5
1 6
5 6


Sample Output 2


16


<image>
You can collect 16 points by going from vertices 1 → 2 → 3 → 1 → 5 → 6 → 1 → 4.





Example

Input

6 6
1 2 3 4 5 6
1 2
2 3
3 4
1 4
4 5
5 6


Output

21

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kevin and Stuart want to play the 'The Minion Game'.

Game Rules

Both players are given the same string, $\mbox{S}$.

Both players have to make substrings using the letters of the string $\mbox{S}$.

Stuart has to make words starting with consonants.

Kevin has to make words starting with vowels. 

The game ends when both players have made all possible substrings.

Scoring

A player gets +1 point for each occurrence of the substring in the string $\mbox{S}$.

For Example:

String $\mbox{S}$ = BANANA

Kevin's vowel beginning word = ANA

Here, ANA occurs twice in BANANA. Hence, Kevin will get 2 Points.

For better understanding, see the image below: 

Your task is to determine the winner of the game and their score.

Function Description   

Complete the minion_game in the editor below.    

minion_game has the following parameters:   

string string: the string to analyze   

Prints   

string: the winner's name and score, separated by a space on one line, or Draw if there is no winner   

Input Format

A single line of input containing the string $\mbox{S}$. 

Note: The string $\mbox{S}$ will contain only uppercase letters: $\left[{\mbox{A}-\mbox{Z}}\right]$.  

Constraints

$0<len(S)\leq10^6$

Sample Input
BANANA

Sample Output
Stuart 12

Note : 

Vowels are only defined as $\textit{AEIOU}$. In this problem, $\mathbf{Y}$ is not considered a vowel.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a dice with one letter of the alphabet (a ~ z, A ~ Z) drawn on each side.


<image>


Consider combining eight such dice to make a 2 x 2 x 2 cube.


<image>


There are conditions on how to combine the dice, and the facing faces of each dice must have the same alphabet, one in lowercase and the other in uppercase. For example, a surface marked a can be touched by a face marked A. However, the orientation of the characters when touching them does not matter.


<image>


According to this rule, input the information of 8 dice and create a program to judge whether or not you can make a cube. If you can make a cube, output YES (half-width uppercase letters), and if you cannot make it, output NO (half-width uppercase letters).

The letters on each side of the dice will be represented as c1 to c6 as shown in the following figure. Also, assume that the same letter is never drawn multiple times on a single dice (uppercase and lowercase letters of the same alphabet are not the case).


<image>



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. Each dataset is given in the following format:


s1
s2
::
s8


The i-line gives the information si of the i-th dice. si is a string of length 6 and the jth character corresponds to each side cj of the dice.

The number of datasets does not exceed 50.

Output

The judgment result (half-width uppercase letters) is output to one line for each data set.

Example

Input

zabZNq
BCxmAi
ZcbBCj
aizXCm
QgmABC
JHzMop
ImoXGz
MZTOhp
zabZnQ
BCxmAi
ZcbBCj
aizXCm
QgmABC
JHzMop
ImoXGz
MZTOhp
abcdef
ABDCFE
FBDCAE
abcdef
BEACDF
bfcaed
fabcde
DEABCF
UnivOf
AizuaH
zTXZYW
piglIt
GRULNP
higGtH
uAzIXZ
FizmKZ
UnivOf
AizuaH
piglIt
higGtH
GRULNP
uAzIXZ
FizmKZ
ZTXzYW
0


Output

YES
NO
YES
YES
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A study has shown that playing a musical instrument helps in increasing one's IQ by 7 points.
Chef knows he can't beat Einstein in physics, but he wants to try to beat him in an IQ competition.

You know that Einstein had an IQ of 170, and Chef currently has an IQ of X.

Determine if, after learning to play a musical instrument, Chef's IQ will become strictly greater than Einstein's.

Print "Yes" if it is possible for Chef to beat Einstein, else print "No" (without quotes).

You may print each character of the string in either uppercase or lowercase (for example, the strings yEs, yes, Yes, and YES will all be treated as identical).

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

- The first and only line of input will contain a single integer X, the current IQ of Chef.

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

- For each testcase, output in a single line "Yes" or "No"
- You may print each character of the string in either uppercase or lowercase (for example, the strings yEs, yes, Yes, and YES will all be treated as identical).

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

$100 ≤ X ≤ 169$

------ subtasks ------ 

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
165
----- Sample Output 1 ------ 
Yes
----- explanation 1 ------ 
After learning a musical instrument, Chef's final IQ will be $165+7=172$. Since $172 > 170$, Chef can beat Einstein.

----- Sample Input 2 ------ 
120
----- Sample Output 2 ------ 
No
----- explanation 2 ------ 
After learning a musical instrument, Chef's final IQ will be $120+7=127$. Since $127 < 170$, Chef cannot beat Einstein.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Denis, after buying flowers and sweets (you will learn about this story in the next task), went to a date with Nastya to ask her to become a couple. Now, they are sitting in the cafe and finally... Denis asks her to be together, but ... Nastya doesn't give any answer. 

The poor boy was very upset because of that. He was so sad that he punched some kind of scoreboard with numbers. The numbers are displayed in the same way as on an electronic clock: each digit position consists of $7$ segments, which can be turned on or off to display different numbers. The picture shows how all $10$ decimal digits are displayed: 

 [Image] 

After the punch, some segments stopped working, that is, some segments might stop glowing if they glowed earlier. But Denis remembered how many sticks were glowing and how many are glowing now. Denis broke exactly $k$ segments and he knows which sticks are working now. Denis came up with the question: what is the maximum possible number that can appear on the board if you turn on exactly $k$ sticks (which are off now)? 

It is allowed that the number includes leading zeros.


-----Input-----

The first line contains integer $n$ $(1 \leq n \leq 2000)$  — the number of digits on scoreboard and $k$ $(0 \leq k \leq 2000)$  — the number of segments that stopped working.

The next $n$ lines contain one binary string of length $7$, the $i$-th of which encodes the $i$-th digit of the scoreboard.

Each digit on the scoreboard consists of $7$ segments. We number them, as in the picture below, and let the $i$-th place of the binary string be $0$ if the $i$-th stick is not glowing and $1$ if it is glowing. Then a binary string of length $7$ will specify which segments are glowing now.

 [Image] 

Thus, the sequences "1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011" encode in sequence all digits from $0$ to $9$ inclusive.


-----Output-----

Output a single number consisting of $n$ digits  — the maximum number that can be obtained if you turn on exactly $k$ sticks or $-1$, if it is impossible to turn on exactly $k$ sticks so that a correct number appears on the scoreboard digits.


-----Examples-----
Input
1 7
0000000

Output
8
Input
2 5
0010010
0010010

Output
97
Input
3 5
0100001
1001001
1010011

Output
-1


-----Note-----

In the first test, we are obliged to include all $7$ sticks and get one $8$ digit on the scoreboard.

In the second test, we have sticks turned on so that units are formed. For $5$ of additionally included sticks, you can get the numbers $07$, $18$, $34$, $43$, $70$, $79$, $81$ and $97$, of which we choose the maximum  — $97$.

In the third test, it is impossible to turn on exactly $5$ sticks so that a sequence of numbers appears on the scoreboard.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Nod is an astrologist and has defined a new constellation. He took two photos of the constellation to foretell a future of his friend. The constellation consists of n stars. The shape of the constellation in these photos are the same, but the angle of them are different because these photos were taken on a different day. He foretells a future by the difference of the angle of them.

Your job is to write a program to calculate the difference of the angle of two constellation.



Input

The input is a sequence of datasets. Each dataset is given in the following format:


n
x1,1 y1,1
...
x1,n y1,n
x2,1 y2,1
...
x2,n y2,n


The first line of each dataset contains a positive integers n (n ≤ 1,000). The next n lines contain two real numbers x1,i and y1,i (|x1,i|, |y1,i| ≤ 100), where (x1,i , y1,i) denotes the coordinates of the i-th star of the constellation in the first photo. The next n lines contain two real numbers x2,i and y2,i (|x2,i|, |y2,i| ≤ 100), where (x2,i , y2,i ) denotes the coordinates of the i-th star of the constellation in the second photo.

Note that the ordering of the stars does not matter for the sameness. It is guaranteed that distance between every pair of stars in each photo is larger than 10-5.

The input is terminated in case of n = 0. This is not part of any datasets and thus should not be processed.

Output

For each dataset, you should print a non-negative real number which is the difference of the angle of the constellation in the first photo and in the second photo. The difference should be in radian, and should not be negative. If there are two or more solutions, you should print the smallest one. The difference may be printed with any number of digits after decimal point, provided the absolute error does not exceed 10-7. No extra space or character is allowed.

Example

Input

3
0.0 0.0
1.0 1.0
0.0 1.0
3.0 3.0
2.0 2.0
3.0 2.0
0


Output

3.14159265359

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Take an integer `n (n >= 0)` and a digit `d (0 <= d <= 9)` as an integer. Square all numbers `k (0 <= k <= n)` between 0 and n. Count the numbers of 
digits `d` used in the writing of all the `k**2`. Call `nb_dig` (or nbDig or ...) the function taking `n` and `d` as parameters and returning this count.

#Examples:
```
n = 10, d = 1, the k*k are 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
We are using the digit 1 in 1, 16, 81, 100. The total count is then 4.

nb_dig(25, 1):
the numbers of interest are
1, 4, 9, 10, 11, 12, 13, 14, 19, 21 which squared are 1, 16, 81, 100, 121, 144, 169, 196, 361, 441
so there are 11 digits `1` for the squares of numbers between 0 and 25.
```
Note that `121` has twice the digit `1`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is an empty array.
The following N operations will be performed to insert integers into the array.
In the i-th operation (1≤i≤N), b_i copies of an integer a_i are inserted into the array.
Find the K-th smallest integer in the array after the N operations.
For example, the 4-th smallest integer in the array \{1,2,2,3,3,3\} is 3.

-----Constraints-----
 - 1≤N≤10^5 
 - 1≤a_i,b_i≤10^5 
 - 1≤K≤b_1…+…b_n
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:  
N K
a_1 b_1
:  
a_N b_N

-----Output-----
Print the K-th smallest integer in the array after the N operations.  

-----Sample Input-----
3 4
1 1
2 2
3 3

-----Sample Output-----
3

The resulting array is the same as the one in the problem statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
DZY loves collecting special strings which only contain lowercase letters. For each lowercase letter c DZY knows its value w_{c}. For each special string s = s_1s_2... s_{|}s| (|s| is the length of the string) he represents its value with a function f(s), where $f(s) = \sum_{i = 1}^{|s|}(w_{s_{i}} \cdot i)$

Now DZY has a string s. He wants to insert k lowercase letters into this string in order to get the largest possible value of the resulting string. Can you help him calculate the largest possible value he could get? 


-----Input-----

The first line contains a single string s (1 ≤ |s| ≤ 10^3).

The second line contains a single integer k (0 ≤ k ≤ 10^3).

The third line contains twenty-six integers from w_{a} to w_{z}. Each such number is non-negative and doesn't exceed 1000.


-----Output-----

Print a single integer — the largest possible value of the resulting string DZY could get.


-----Examples-----
Input
abc
3
1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Output
41



-----Note-----

In the test sample DZY can obtain "abcbbc", value = 1·1 + 2·2 + 3·2 + 4·2 + 5·2 + 6·2 = 41.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Doctor Kunj installed new software on cyborg Shresth.
This software introduced Shresth to range minimum queries.
Cyborg Shresth thought of T$T$ different problems in each of which you will be given
an array A$A$ of length N$N$ and an array B$B$ of length M$M$. In each of these problems, you have to calculate:
∑mi=1∑mj=irangeMin(B[i],B[j])$\sum_{i=1}^m \sum_{j=i}^m rangeMin(B[i],B[j])$
Where rangeMin(i,j)$rangeMin(i,j)$ returns the minimum element in the range of indices i$i$ to j$j$ (both included) in array A$A$.
It is given that array B$B$ consists of pairwise distinct elements and is in ascending order.

-----Input Format:-----
- First line will contain T$T$, the number of different problems Cyborg Shresth thought of.
- Each problem's input data will be given in three different lines. 
- The first line will contain N$N$ and M$M$, the length of array A$A$ and B$B$ respectively. 
- The second line will contain N$N$ space separated positive integers, which form the array A$A$. - 
- The third line will contain M$M$ space separated positive integers, which form the array B$B$.

-----Output Format:-----
- For each different problem, print on a new line the answer to the problem, i.e. the value of ∑mi=1∑mj=irangeMin(B[i],B[j])$\sum_{i=1}^m \sum_{j=i}^m rangeMin(B[i],B[j])$ .

-----Constraints:-----
- 1≤T≤105$1 \leq T \leq {10}^5$
- 1≤N≤105$1 \leq N \leq {10}^5$
- 1≤M≤105$1 \leq M \leq {10}^5$
- 1≤A[i]≤109$1 \leq A[i] \leq 10^9$
- 1≤B[i]≤N$1 \leq B[i] \leq N$
It is guaranteed that the sum of N$N$ over all test cases does not exceed 106${10}^6$ .

-----Sample Input:-----
1
7 3
10 3 7 9 1 19 2
1 4 6

-----Sample Output:-----
43

-----Explanation:-----
For the given array A$A$, we have to calculate rangeMin(1,1)+rangeMin(1,4)+rangeMin(1,6)+rangeMin(4,4)+rangeMin(4,6)+rangeMin(6,6)$rangeMin(1,1) + rangeMin(1,4) + rangeMin(1,6) + rangeMin(4,4) + rangeMin(4,6) + rangeMin(6,6) $.
This is equal to 10+3+1+9+1+19=43$10 + 3 + 1 + 9 + 1 +19 = 43$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a rectangle of size n x m, find the minimum number of integer-sided squares that tile the rectangle.
 
Example 1:

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)
Example 2:

Input: n = 5, m = 8
Output: 5

Example 3:

Input: n = 11, m = 13
Output: 6

 
Constraints:

1 <= n <= 13
1 <= m <= 13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
## Welcome to my (amazing) kata!

You are given a gigantic number to decode.  Each number is a code that alternates in a pattern between encoded text and a smaller, encoded number.  The pattern's length varies with every test, but the alternation between encoded text and an encoded number will always be there.  Following this rule, each number tested begins with encoded text and ends with an encoded number.

## How the encoding works

Now, we should probably review how the string of numbers is formed - considering you have to unform it. So, first, some text is taken, and encoded.  The system of encoding is taking each letter's position in the alphabet and adding 100 to it.  For example, `m` in the real text would be `113` in the code-number.

After the text, there is a binary number.  You should convert this number to a normal, base 10 decimal (all of them can be converted into whole, non-negative numbers).

Separating encoded text and encoded numbers, there is a `98`.  Because the numbers are in binary, the only digits they use are '0' and '1', and each letter of the alphabet, encoded, is between 101-127, all instances of `98` are to indicate a separation between encoded text and encoded numbers.  There may also be a `98` at the very end of the number.

When you return your final answer, the text and numbers should always be separated by a comma (`,`)

## Example

```python
decode(103115104105123101118119981001098113113113981000) = "codewars, 18, mmm, 8"
```
The part of the code until the first `98` can be decoded to `"codewars"`.  `10010` is binary for `18`. `113113113` translates to `"mmm"`.  And `1000` is binary for `8`.

Here is a visualisation of the example:

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given N numbers in an array. Your task is to keep at-most K numbers at the top (According to their frequency).  We basically need to print top k numbers when input stream has included k distinct elements, else need to print all distinct elements sorted by frequency.
Example 1:
Input:
N=5, K=4
arr[] = {5, 2, 1, 3, 2} 
Output: 5 2 5 1 2 5 1 2 3 5 2 1 3 5 
Explanation:
Firstly their was 5 whose frequency
is max till now. so print 5.
Then 2 , which is smaller than 5 but
their frequency is same so print 2 5.
Then 1, which is smallet among all the
number arrived, so print 1 2 5.
Then 3 , so print 1 2 3 5
Then again 2, which has the highest
frequency among all number so 2 1 3 5.
Example 2:
Input:
N=5, K=4
arr[] = {5, 2, 1, 3, 4} 
Output: 5 2 5 1 2 5 1 2 3 5 1 2 3 4 
Explanation:
Firstly their was 5 whose frequency is
max till now. so print 5.
Then 2 , which is smaller than 5 but
their frequency is same so print 2 5.
Then 1, Which is smallest among all the
number arrived, so print 1 2 5.
Then 3 , so print 1 2 3 5.
Then 4, so 1 2 3 4 as K is 4 so print
at-most k elements.
 
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function kTop() that takes array a, integer n and integer k as parameters and returns the array that contains our desired output.
 
Expected Time Complexity: O(N*K).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N,K ≤ 10^{3}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The HR manager was disappointed again. The last applicant failed the interview the same way as 24 previous ones. "Do I give such a hard task?" — the HR manager thought. "Just raise number 5 to the power of n and get last two digits of the number. Yes, of course, n can be rather big, and one cannot find the power using a calculator, but we need people who are able to think, not just follow the instructions."

Could you pass the interview in the machine vision company in IT City?


-----Input-----

The only line of the input contains a single integer n (2 ≤ n ≤ 2·10^18) — the power in which you need to raise number 5.


-----Output-----

Output the last two digits of 5^{n} without spaces between them.


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

Output
25

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