vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: We Need More Bosses

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Your friend is developing a computer game. He has already decided how the game world should look like — it should consist of $n$ locations connected by $m$ two-way passages. The passages are designed in such a way that it should be possible to get from any location to any other location.

Of course, some passages should be guarded by the monsters (if you just can go everywhere without any difficulties, then it's not fun, right?). Some crucial passages will be guarded by really fearsome monsters, requiring the hero to prepare for battle and designing his own tactics of defeating them (commonly these kinds of monsters are called bosses). And your friend wants you to help him place these bosses.

The game will start in location $s$ and end in location $t$, but these locations are not chosen yet. After choosing these locations, your friend will place a boss in each passage such that it is impossible to get from $s$ to $t$ without using this passage. Your friend wants to place as much bosses as possible (because more challenges means more fun, right?), so he asks you to help him determine the maximum possible number of bosses, considering that any location can be chosen as $s$ or as $t$.

Input Specification:
The first line contains two integers $n$ and $m$ ($2 \le n \le 3 \cdot 10^5$, $n - 1 \le m \le 3 \cdot 10^5$) — the number of locations and passages, respectively.

Then $m$ lines follow, each containing two integers $x$ and $y$ ($1 \le x, y \le n$, $x \ne y$) describing the endpoints of one of the passages.

It is guaranteed that there is no pair of locations directly connected by two or more passages, and that any location is reachable from any other location.

Output Specification:
Print one integer — the maximum number of bosses your friend can place, considering all possible choices for $s$ and $t$.

Demo Input:
['5 5\n1 2\n2 3\n3 1\n4 1\n5 2\n', '4 3\n1 2\n4 3\n3 2\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In input string ```word```(1 word):
* replace the vowel with the nearest left consonant.
* replace the consonant with the nearest right vowel.

P.S. To complete this task imagine the alphabet is a circle (connect the first and last element of the array in the mind). For example, 'a' replace with 'z', 'y' with 'a', etc.(see below)

For example:
```
'codewars' => 'enedazuu'
'cat' => 'ezu'
'abcdtuvwxyz' => 'zeeeutaaaaa'
```

It is preloaded: 

```
const alphabet = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
const consonants = ['b','c','d','f','g','h','j','k','l','m','n','p','q','r','s','t','v','w','x','y','z'];
const vowels = ['a','e','i','o','u'];
```

P.S. You work with lowercase letters only.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Menger Sponge is a three-dimensional fractal, first described by Karl Menger in 1926.

![Mengers Sponge (Level 0-3)](http://i.imgur.com/V6Rb4Za.jpg)
###### _An illustration of the iterative construction of a Menger sponge_

A method of constructing a Menger Sponge can be visualized as follows:
1. Start from a cube (first part of image).
2. Scale down the cube so that side length is 1/3 of its original, and make 20 copies of it.
3. Place the copies so that they measure the same size as the original cube but without its central parts (next part of image)
4. Repeat the process from step 2 for the new smaller cubes from the previous step.
5. In each iteration (e.g. repeating the last three steps), the effect will be that parts of the cube will be removed, they'll never be added. Menger sponge will always consist of parts will never be removed, regardless of how many iterations you do.

___

An alternative explanation:
1. Start from a cube (first part of image).
2. Devide each cube into 27 equal sized cubes.
3. Remove the middle-cube and the six cubes on each side of the group of 27 cubes (second part of image).
4. Repeat the process from step 2 for the smaller cubes (third and fourth part of image).

## Task
In this kata you will create a function that takes non negative integers (from 0 to n) and return the amount of cubes that the Menger Sponge would have in that specific iteration.


## Example
```
calc_ms(0) == 1
calc_ms(1) == 20
calc_ms(2) == 400
calc_ms(3) == 8000
calc_ms(4) == 160000
calc_ms(5) == 3200000
calc_ms(6) == 64000000
```

Happy coding!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Haiku is a genre of Japanese traditional poetry.

A haiku poem consists of 17 syllables split into three phrases, containing 5, 7 and 5 syllables correspondingly (the first phrase should contain exactly 5 syllables, the second phrase should contain exactly 7 syllables, and the third phrase should contain exactly 5 syllables). A haiku masterpiece contains a description of a moment in those three phrases. Every word is important in a small poem, which is why haiku are rich with symbols. Each word has a special meaning, a special role. The main principle of haiku is to say much using a few words.

To simplify the matter, in the given problem we will consider that the number of syllable in the phrase is equal to the number of vowel letters there. Only the following letters are regarded as vowel letters: "a", "e", "i", "o" and "u".

Three phases from a certain poem are given. Determine whether it is haiku or not.

Input

The input data consists of three lines. The length of each line is between 1 and 100, inclusive. The i-th line contains the i-th phrase of the poem. Each phrase consists of one or more words, which are separated by one or more spaces. A word is a non-empty sequence of lowercase Latin letters. Leading and/or trailing spaces in phrases are allowed. Every phrase has at least one non-space character. See the example for clarification.

Output

Print "YES" (without the quotes) if the poem is a haiku. Otherwise, print "NO" (also without the quotes).

Examples

Input

on  codeforces 
beta round is running
   a rustling of keys 


Output

YES

Input

how many gallons
of edo s rain did you drink
                                cuckoo


Output

NO

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Since the giant heads have appeared in the sky all humanity is in danger, so all Ricks and Mortys from all parallel universes are gathering in groups to find a solution to get rid of them. 

There are *n* parallel universes participating in this event (*n* Ricks and *n* Mortys). I. e. each of *n* universes has one Rick and one Morty. They're gathering in *m* groups. Each person can be in many groups and a group can contain an arbitrary number of members.

Ricks and Mortys have registered online in these groups. So, a person can have joined a group more than once (developer of this website hadn't considered this possibility).

Summer from universe #1 knows that in each parallel universe (including hers) exactly one of Rick and Morty from that universe is a traitor and is loyal, but no one knows which one. She knows that we are doomed if there's a group such that every member in that group is a traitor (they will plan and destroy the world). 

Summer knows that if there's a possibility that world ends (there's a group where all members are traitors) she should immediately cancel this event. So she wants to know if she should cancel the event. You have to tell her yes if and only if there's at least one scenario (among all 2*n* possible scenarios, 2 possible scenarios for who a traitor in each universe) such that in that scenario the world will end.

Input Specification:
The first line of input contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=104) — number of universes and number of groups respectively.

The next *m* lines contain the information about the groups. *i*-th of them first contains an integer *k* (number of times someone joined *i*-th group, *k*<=&gt;<=0) followed by *k* integers *v**i*,<=1,<=*v**i*,<=2,<=...,<=*v**i*,<=*k*. If *v**i*,<=*j* is negative, it means that Rick from universe number <=-<=*v**i*,<=*j* has joined this group and otherwise it means that Morty from universe number *v**i*,<=*j* has joined it.

Sum of *k* for all groups does not exceed 104.

Output Specification:
In a single line print the answer to Summer's question. Print "YES" if she should cancel the event and "NO" otherwise.

Demo Input:
['4 2\n1 -3\n4 -2 3 2 -3\n', '5 2\n5 3 -2 1 -1 5\n3 -5 2 5\n', '7 2\n3 -1 6 7\n7 -5 4 2 4 7 -3 4\n']

Demo Output:
['YES\n', 'NO\n', 'YES\n']

Note:
In the first sample testcase, 1st group only contains the Rick from universe number 3, so in case he's a traitor, then all members of this group are traitors and so Summer should cancel the event.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In an electric circuit, when two resistors R_1 and R_2 are connected in parallel, the equivalent resistance R_3 can be derived from the following formula:

* \frac{1}{R_1} + \frac{1}{R_2} = \frac{1}{R_3}



Given R_1 and R_2, find R_3.

Constraints

* 1 \leq R_1, R_2 \leq 100
* R_1 and R_2 are integers.

Input

The input is given from Standard Input in the following format:


R_1 R_2


Output

Print the value of R_3.

The output is considered correct if the absolute or relative error is at most 10^{-6}.

Examples

Input

2 3


Output

1.2000000000


Input

100 99


Output

49.7487437186

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monk's favourite game is Football and his favourite club is "Manchester United". Manchester United has qualified for the Champions League Final which is to be held at the Wembley Stadium in London. So, he decided to go there and watch his favourite team play. After reaching the stadium, he saw that many people have lined up for the match tickets. He knows that there are M rows in the stadium with different seating capacities. They may or may not be equal. The price of the ticket depends on the row. If the row has K(always greater than 0) vacant seats, then the price of the ticket will be K pounds(units of British Currency). Now, every football fan standing in the line will get a ticket one by one.
Given the seating capacities of different rows, find the maximum possible pounds that the club will gain with the help of the ticket sales.

Input:
The first line consists of M and N. M denotes the number of seating rows in the stadium and N denotes the number of football fans waiting in the line to get a ticket for the match.
Next line consists of M space separated integers X[1],X[2],X[3].... X[M] where X[i] denotes the number of empty seats initially in the i^th row.  

Output:
Print in a single line the maximum pounds the club will gain.  

Constraints:
1 ≤ M ≤ 1000000
1 ≤ N ≤ 1000000
1 ≤ X[i] ≤ 1000000
Sum of X[i] for all 1 ≤ i ≤ M will always be greater than N.

SAMPLE INPUT
3 4
1 2 4

SAMPLE OUTPUT
11

Explanation

In the sample test case, number of rows is 3 and the 4 people waiting in line to get a ticket.
Since the maximum cost of ticket initially is 4 pounds, therefore the first person in line will buy a ticket for the 3rd row.
The person standing in line will again choose the 3rd row as it has the maximum number of seats, which will cost him 3 pounds.
The next person will have 2 choices, he can either choose the 2nd row or the 3rd row which will cost him 2 pounds.
Similarly, the last person will choose the row will 2 seats remaining, which will cost him 2 pounds.  
Total cost = 4+3+2+2 = 11 pounds.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a string *A*. Find a string *B*, where *B* is a palindrome and *A* is a subsequence of *B*.

A subsequence of a string is a string that can be derived from it by deleting some (not necessarily consecutive) characters without changing the order of the remaining characters. For example, "cotst" is a subsequence of "contest".

A palindrome is a string that reads the same forward or backward.

The length of string *B* should be at most 104. It is guaranteed that there always exists such string.

You do not need to find the shortest answer, the only restriction is that the length of string *B* should not exceed 104.

Input Specification:
First line contains a string *A* (1<=≤<=|*A*|<=≤<=103) consisting of lowercase Latin letters, where |*A*| is a length of *A*.

Output Specification:
Output single line containing *B* consisting of only lowercase Latin letters. You do not need to find the shortest answer, the only restriction is that the length of string *B* should not exceed 104. If there are many possible *B*, print any of them.

Demo Input:
['aba\n', 'ab\n']

Demo Output:
['aba', 'aabaa']

Note:
In the first example, "aba" is a subsequence of "aba" which is a palindrome.

In the second example, "ab" is a subsequence of "aabaa" which is a palindrome.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
I see a pink boar and I want it painted black. Black boars look much more awesome and mighty than the pink ones. Since Jaggy became the ruler of the forest, he has been trying his best to improve the diplomatic relations between the forest region and the nearby ones. 

Some other rulers, however, have requested too much in return for peace between their two regions, so he realized he has to resort to intimidation. Once a delegate for diplomatic relations of a neighboring region visits Jaggy’s forest, if they see a whole bunch of black boars, they might suddenly change their mind about attacking Jaggy. Black boars are really scary, after all. 

Jaggy’s forest can be represented as a tree (connected graph without cycles) with n vertices. Each vertex represents a boar and is colored either black or pink. Jaggy has sent a squirrel to travel through the forest and paint all the boars black. The squirrel, however, is quite unusually trained and while it traverses the graph, it changes the color of every vertex it visits, regardless of its initial color: pink vertices become black and black vertices become pink. 

Since Jaggy is too busy to plan the squirrel’s route, he needs your help. He wants you to construct a walk through the tree starting from vertex 1 such that in the end all vertices are black. A walk is a sequence of vertices, such that every consecutive pair has an edge between them in a tree.

Input

The first line of input contains integer n (2 ≤ n ≤ 200 000), denoting the number of vertices in the tree. The following n lines contains n integers, which represent the color of the nodes.

If the i-th integer is 1, if the i-th vertex is black and  - 1 if the i-th vertex is pink.

Each of the next n - 1 lines contains two integers, which represent the indexes of the vertices which are connected by the edge. Vertices are numbered starting with 1.

Output

Output path of a squirrel: output a sequence of visited nodes' indexes in order of visiting. In case of all the nodes are initially black, you should print 1. Solution is guaranteed to exist. If there are multiple solutions to the problem you can output any of them provided length of sequence is not longer than 107.

Example

Input

5
1
1
-1
1
-1
2 5
4 3
2 4
4 1


Output

1 4 2 5 2 4 3 4 1 4 1

Note

At the beginning squirrel is at node 1 and its color is black. Next steps are as follows: 

  * From node 1 we walk to node 4 and change its color to pink. 
  * From node 4 we walk to node 2 and change its color to pink. 
  * From node 2 we walk to node 5 and change its color to black. 
  * From node 5 we return to node 2 and change its color to black. 
  * From node 2 we walk to node 4 and change its color to black. 
  * We visit node 3 and change its color to black. 
  * We visit node 4 and change its color to pink. 
  * We visit node 1 and change its color to pink. 
  * We visit node 4 and change its color to black. 
  * We visit node 1 and change its color to black. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef got into a fight with the evil Dr Doof. Dr Doof has decided to destroy all even numbers from the universe using his Evil-Destroy-inator. Chef has $N$ integers with him. To stop Doof, Chef has to find an odd number which is an integer multiple of all $N$ numbers that he has with him. Find if it is possible for Chef to prevent Dr Doof from destroying the even numbers.
Formally, given $N$ positive integers, find if there exists an odd number which is an integer multiple of all the given $N$ numbers. If yes, print "YES", otherwise "NO". You can print any letter in any case.

-----Input-----
- First line contains $T$, number of testcases. Each testcase consists of $2$ lines.
- The first line of each test case consists of a positive integer $N$, denoting the number of positive integers Chef has.
- The second line of each test case contains $N$ space separated integers $A_i$ each denoting an integer that Chef has with him.

-----Output-----
For every test case, if there exists such an odd number, print "YES" on a separate line, otherwise "NO". The judge is case insensitive. That means, your code can print any letter in any case ( "Yes", "yes" or "YES" are all accepted).

-----Constraints-----
- $1 \leq T \leq 10^3$
- $1 \leq N \leq 10^3$
- $1 \leq A_i \leq 10^3$

-----Sample Input-----
2
5
1 2 5 4 3
1
7

-----Sample Output-----
NO
YES

-----Explanation-----
For test $1$: There exists no odd number.
For test $2$: The possible odd numbers can be $7$, $21$, $49$, $315$, …

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Getting an A

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Translator's note: in Russia's most widespread grading system, there are four grades: 5, 4, 3, 2, the higher the better, roughly corresponding to A, B, C and F respectively in American grading system.

The term is coming to an end and students start thinking about their grades. Today, a professor told his students that the grades for his course would be given out automatically  — he would calculate the simple average (arithmetic mean) of all grades given out for lab works this term and round to the nearest integer. The rounding would be done in favour of the student — $4.5$ would be rounded up to $5$ (as in example 3), but $4.4$ would be rounded down to $4$.

This does not bode well for Vasya who didn't think those lab works would influence anything, so he may receive a grade worse than $5$ (maybe even the dreaded $2$). However, the professor allowed him to redo some of his works of Vasya's choosing to increase his average grade. Vasya wants to redo as as few lab works as possible in order to get $5$ for the course. Of course, Vasya will get $5$ for the lab works he chooses to redo.

Help Vasya — calculate the minimum amount of lab works Vasya has to redo.

Input Specification:
The first line contains a single integer $n$ — the number of Vasya's grades ($1 \leq n \leq 100$).

The second line contains $n$ integers from $2$ to $5$ — Vasya's grades for his lab works.

Output Specification:
Output a single integer — the minimum amount of lab works that Vasya has to redo. It can be shown that Vasya can always redo enough lab works to get a $5$.

Demo Input:
['3\n4 4 4\n', '4\n5 4 5 5\n', '4\n5 3 3 5\n']

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

Note:
In the first sample, it is enough to redo two lab works to make two $4$s into $5$s.

In the second sample, Vasya's average is already $4.75$ so he doesn't have to redo anything to get a $5$.

In the second sample Vasya has to redo one lab work to get rid of one of the $3$s, that will make the average exactly $4.5$ so the final grade would be $5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the number of factors for a given integer N.
 
Example 1:
Input:
N = 5
Output:
2
Explanation:
5 has 2 factors 1 and 5
Example 2:
Input:
N = 25
Output:
3
Explanation:
25 has 3 factors 1, 5, 25
Your Task:
You don't need to read input or print anything. Your task is to complete the function countFactors() which takes an integer N as input parameters and returns an integer, total number factor of N.
 
Expected Time Complexity: O(sqrt(N))
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 100000

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

My TV remote control has arrow buttons and an `OK` button.

I can use these to move a "cursor" on a logical screen keyboard to type "words"...

The screen "keyboard" layout looks like this


  #tvkb {
    width : 300px;
    border: 5px solid gray; border-collapse: collapse;
  }
  #tvkb td {
    color : orange;
    background-color : black;
    text-align : right;
    border: 3px solid gray; border-collapse: collapse;
  }


abcde123
fghij456
klmno789
pqrst.@0
uvwxyz_/


# Kata task

How many button presses on my remote are required to type a given `word`?

## Notes

* The cursor always starts on the letter `a` (top left)
* Remember to also press `OK` to "accept" each character.
* Take a direct route from one character to the next
* The cursor does not wrap (e.g. you cannot leave one edge and reappear on the opposite edge)
* A "word" (for the purpose of this Kata) is any sequence of characters available on my virtual "keyboard" 

# Example

word = `codewars`

* c => `a`-`b`-`c`-OK = 3
* o => `c`-`d`-`e`-`j`-`o`-OK = 5
* d => `o`-`j`-`e`-`d`-OK = 4
* e => `d`-`e`-OK = 2
* w => `e`-`j`-`o`-`t`-`y`-`x`-`w`-OK = 7
* a => `w`-`r`-`m`-`h`-`c`-`b`-`a`-OK = 7
* r => `a`-`f`-`k`-`p`-`q`-`r`-OK = 6
* s => `r`-`s`-OK = 2

Answer = 3 + 5 + 4 + 2 + 7 + 7 + 6 + 2 = 36



*Good Luck!
DM.*



Series
* TV Remote
* TV Remote (shift and space)
* TV Remote (wrap)
* TV Remote (symbols)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a string S of length N consisting of characters `0` and `1`. You will perform the following operation for each i = 1, 2, ..., m:

* Arbitrarily permute the characters within the substring of S starting at the l_i-th character from the left and extending through the r_i-th character.



Here, the sequence l_i is non-decreasing.

How many values are possible for S after the M operations, modulo 1000000007(= 10^9+7)?

Constraints

* 2≦N≦3000
* 1≦M≦3000
* S consists of characters `0` and `1`.
* The length of S equals N.
* 1≦l_i < r_i≦N
* l_i ≦ l_{i+1}

Input

The input is given from Standard Input in the following format:


N M
S
l_1 r_1
:
l_M r_M


Output

Print the number of the possible values for S after the M operations, modulo 1000000007.

Examples

Input

5 2
01001
2 4
3 5


Output

6


Input

9 3
110111110
1 4
4 6
6 9


Output

26


Input

11 6
00101000110
2 4
2 3
4 7
5 6
6 10
10 11


Output

143

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation p of size n is the sequence p_1, p_2, ..., p_{n}, consisting of n distinct integers, each of them is from 1 to n (1 ≤ p_{i} ≤ n).

A lucky permutation is such permutation p, that any integer i (1 ≤ i ≤ n) meets this condition p_{p}_{i} = n - i + 1.

You have integer n. Find some lucky permutation p of size n.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the required permutation size.


-----Output-----

Print "-1" (without the quotes) if the lucky permutation p of size n doesn't exist.

Otherwise, print n distinct integers p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ n) after a space — the required permutation.

If there are multiple answers, you can print any of them.


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

Output
1 

Input
2

Output
-1

Input
4

Output
2 4 1 3 

Input
5

Output
2 5 3 1 4

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