vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Complete the function/method so that it takes CamelCase string and returns the string in snake_case notation. Lowercase characters can be numbers. If method gets number, it should return string.

Examples:

``` javascript
//  returns test_controller
toUnderscore('TestController');

// returns movies_and_books
toUnderscore('MoviesAndBooks');

// returns app7_test
toUnderscore('App7Test');

// returns "1"
toUnderscore(1);
```

``` coffeescript  
#  returns test_controller
toUnderscore 'TestController'

# returns movies_and_books
toUnderscore 'MoviesAndBooks'

# returns app7_test
toUnderscore 'App7Test'

# returns "1"
toUnderscore 1
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has got many devices that work on electricity. He's got n supply-line filters to plug the devices, the i-th supply-line filter has a_{i} sockets.

Overall Vasya has got m devices and k electrical sockets in his flat, he can plug the devices or supply-line filters directly. Of course, he can plug the supply-line filter to any other supply-line filter. The device (or the supply-line filter) is considered plugged to electricity if it is either plugged to one of k electrical sockets, or if it is plugged to some supply-line filter that is in turn plugged to electricity. 

What minimum number of supply-line filters from the given set will Vasya need to plug all the devices he has to electricity? Note that all devices and supply-line filters take one socket for plugging and that he can use one socket to plug either one device or one supply-line filter.


-----Input-----

The first line contains three integers n, m, k (1 ≤ n, m, k ≤ 50) — the number of supply-line filters, the number of devices and the number of sockets that he can plug to directly, correspondingly. The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 50) — number a_{i} stands for the number of sockets on the i-th supply-line filter.


-----Output-----

Print a single number — the minimum number of supply-line filters that is needed to plug all the devices to electricity. If it is impossible to plug all the devices even using all the supply-line filters, print -1.


-----Examples-----
Input
3 5 3
3 1 2

Output
1

Input
4 7 2
3 3 2 4

Output
2

Input
5 5 1
1 3 1 2 1

Output
-1



-----Note-----

In the first test case he can plug the first supply-line filter directly to electricity. After he plug it, he get 5 (3 on the supply-line filter and 2 remaining sockets for direct plugging) available sockets to plug. Thus, one filter is enough to plug 5 devices.

One of the optimal ways in the second test sample is to plug the second supply-line filter directly and plug the fourth supply-line filter to one of the sockets in the second supply-line filter. Thus, he gets exactly 7 sockets, available to plug: one to plug to the electricity directly, 2 on the second supply-line filter, 4 on the fourth supply-line filter. There's no way he can plug 7 devices if he use one supply-line filter.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given that 
```
f0 = '0'
f1 = '01'
f2 = '010' = f1 + f0
f3 = '01001' = f2 + f1
```

You will be given a number and your task is to return the `nth` fibonacci string. For example:

```
solve(2) = '010'
solve(3) = '01001'
```

More examples in test cases. Good luck!

If you like sequence Katas, you will enjoy this Kata: [Simple Prime Streaming](https://www.codewars.com/kata/5a908da30025e995880000e3)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The biggest gold mine in Berland consists of n caves, connected by n - 1 transitions. The entrance to the mine leads to the cave number 1, it is possible to go from it to any remaining cave of the mine by moving along the transitions. 

The mine is being developed by the InMine Inc., k miners work for it. Each day the corporation sorts miners into caves so that each cave has at most one miner working there. 

For each cave we know the height of its ceiling hi in meters, and for each miner we know his height sj, also in meters. If a miner's height doesn't exceed the height of the cave ceiling where he is, then he can stand there comfortably, otherwise, he has to stoop and that makes him unhappy.

Unfortunately, miners typically go on strike in Berland, so InMine makes all the possible effort to make miners happy about their work conditions. To ensure that no miner goes on strike, you need make sure that no miner has to stoop at any moment on his way from the entrance to the mine to his cave (in particular, he must be able to stand comfortably in the cave where he works). 

To reach this goal, you can choose exactly one cave and increase the height of its ceiling by several meters. However enlarging a cave is an expensive and complex procedure. That's why InMine Inc. asks you either to determine the minimum number of meters you should raise the ceiling of some cave so that it is be possible to sort the miners into the caves and keep all miners happy with their working conditions or to determine that it is impossible to achieve by raising ceiling in exactly one cave.

Input

The first line contains integer n (1 ≤ n ≤ 5·105) — the number of caves in the mine.

Then follows a line consisting of n positive integers h1, h2, ..., hn (1 ≤ hi ≤ 109), where hi is the height of the ceiling in the i-th cave.

Next n - 1 lines contain the descriptions of transitions between the caves. Each line has the form ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), where ai and bi are the numbers of the caves connected by a path.

The next line contains integer k (1 ≤ k ≤ n).

The last line contains k integers s1, s2, ..., sk (1 ≤ sj ≤ 109), where sj is the j-th miner's height.

Output

In the single line print the minimum number of meters that you need to raise the ceiling by in some cave so that all miners could be sorted into caves and be happy about the work conditions. If it is impossible to do, print  - 1. If it is initially possible and there's no need to raise any ceiling, print 0. 

Examples

Input

6
5 8 4 6 3 12
1 2
1 3
4 2
2 5
6 3
6
7 4 2 5 3 11


Output

6


Input

7
10 14 7 12 4 50 1
1 2
2 3
2 4
5 1
6 5
1 7
6
7 3 4 8 8 10


Output

0


Input

3
4 2 8
1 2
1 3
2
17 15


Output

-1

Note

In the first sample test we should increase ceiling height in the first cave from 5 to 11. After that we can distribute miners as following (first goes index of a miner, then index of a cave): <image>.

In the second sample test there is no need to do anything since it is already possible to distribute miners as following: <image>.

In the third sample test it is impossible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem your goal is to guess some secret permutation A of integers from 1 to 16.

There are 17 tests in this problem. Test number i  for 1 ≤ i ≤ 16 will have the following form:
the first line of the input contains string "ELEMENT" (without quotes)
the second line of the input of the test i contains two integers from 1 to 16 each - i and element A[i] of the secret permutation
the only line of the output file contains one integer - A[i] too.

Input of the last (the 17-th test) will contain the only string "PERMUTATION" (without quotes). For this test your program should output some permutation of integers from 1 to 16 - your variant of the secret permutation.

If this permutation equals to the secret permuation A and passes all the 17 tests with your solution , you will receive 100 points. Otherwise you will receive 0 points. Note that for each wrong try you will receive 20 minutes penalty time after you solved this problem (as in ACM ICPC format)

Let us remind you that after you submit solution you can see a detailed feedback for each test separately.

 You can't use "compile and test" without using custom input. If you want to test your solution on hackerearth platform , please use custom input. 

SAMPLE INPUT
[EXAMPLE OF POSSIBLE TEST #2]
ELEMENT
2 4

[EXAMPLE OF POSSIBLE TEST #17]
PERMUTATION

SAMPLE OUTPUT
4


3 4 5 6 7 1 8 9 10 11 13 15 16 12 2 14

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As AtCoder Beginner Contest 100 is taking place, the office of AtCoder, Inc. is decorated with a sequence of length N, a = {a_1, a_2, a_3, ..., a_N}.

Snuke, an employee, would like to play with this sequence.
Specifically, he would like to repeat the following operation as many times as possible:
For every i satisfying 1 \leq i \leq N, perform one of the following: "divide a_i by 2" and "multiply a_i by 3".  
Here, choosing "multiply a_i by 3" for every i is not allowed, and the value of a_i after the operation must be an integer.

At most how many operations can be performed?

-----Constraints-----
 - N is an integer between 1 and 10 \ 000 (inclusive).
 - a_i is an integer between 1 and 1 \ 000 \ 000 \ 000 (inclusive).

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 a_2 a_3 ... a_N

-----Output-----
Print the maximum number of operations that Snuke can perform.

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

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

The sequence is initially {5, 2, 4}. Three operations can be performed as follows:
 - First, multiply a_1 by 3, multiply a_2 by 3 and divide a_3 by 2. The sequence is now {15, 6, 2}.
 - Next, multiply a_1 by 3, divide a_2 by 2 and multiply a_3 by 3. The sequence is now {45, 3, 6}.
 - Finally, multiply a_1 by 3, multiply a_2 by 3 and divide a_3 by 2. The sequence is now {135, 9, 3}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Not considering number 1, the integer 153 is the first integer having this property:
the sum of the third-power of each of its digits  is equal to 153. Take a look:
153 = 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153

The next number that experiments this particular behaviour is 370 with the same power.

Write the function `eq_sum_powdig()`, that finds the numbers below a given upper limit `hMax` that fulfill this property but with different exponents as a power for the digits.

eq_sum_powdig(hMax, exp): ----> sequence of numbers (sorted list) (Number one should not be considered).

Let's see some cases:
```python
eq_sum_powdig(100, 2) ----> []

eq_sum_powdig(1000, 2) ----> []

eq_sum_powdig(200, 3) ----> [153]

eq_sum_powdig(370, 3) ----> [153, 370]
```
Enjoy it !!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are building advanced chips for machines. Making the chips is easy, but the power supply turns out to be an issue since the available batteries have varied power outputs.

Consider the problem of $n$ machines, each with two chips, where each chip is powered by $k$ batteries. Surprisingly, it does not matter how much power each chip gets, but a machine works best when its two chips have power outputs as close as possible. The power output of a chip is simply the smallest power output of its $k$ batteries.

You have a stockpile of $2nk$ batteries that you want to assign to the chips. It might not be possible to allocate the batteries so that in every machine both chips have equal power outputs, but you want to allocate them so that the differences are as small as possible. To be precise, you want to tell your customers that in all machines the difference of power outputs of the two chips is at most $d$, and you want to make $d$ as small as possible. To do this you must determine an optimal allocation of the batteries to the machines.

Consider Sample Input 1. There are $2$ machines, each requiring $3$ batteries per chip, and a supply of batteries with power outputs $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12$. You can, for instance, assign the batteries with power outputs $1, 3, 5$ to one chip, those with power $2, 4, 12$ to the other chip of the same machine, those with power $6, 8, 9$ to the third chip, and those with power $7, 10, 11$ to the fourth. The power outputs of the chips are $1, 2, 6$, and $7$, respectively, and the difference between power outputs is $1$ in both machines. Note that there are many other ways to achieve this result.

-----Input-----
The input consists of a single test case. A test case consists of two lines. The first line contains two positive integers: the number of machines $n$ and the number of batteries per chip $k$ ($2nk \leq 10^6$). The second line contains $2nk$ integers $p_ i$ specifying the power outputs of the batteries ($1 \leq p_ i \leq 10^9$).

-----Output-----
Display the smallest number $d$ such that you can allocate the batteries so that the difference of power outputs of the two chips in each machine is at most $d$.

-----Examples-----
Sample Input:
2 3
1 2 3 4 5 6 7 8 9 10 11 12
Sample Output:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Mathematical Analysis Rocks!

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Students of group 199 have written their lectures dismally. Now an exam on Mathematical Analysis is approaching and something has to be done asap (that is, quickly). Let's number the students of the group from 1 to *n*. Each student *i* (1<=≤<=*i*<=≤<=*n*) has a best friend *p*[*i*] (1<=≤<=*p*[*i*]<=≤<=*n*). In fact, each student is a best friend of exactly one student. In other words, all *p*[*i*] are different. It is possible that the group also has some really "special individuals" for who *i*<==<=*p*[*i*].

Each student wrote exactly one notebook of lecture notes. We know that the students agreed to act by the following algorithm: 
 -  on the first day of revising each student studies his own Mathematical Analysis notes, -  in the morning of each following day each student gives the notebook to his best friend and takes a notebook from the student who calls him the best friend. 
Thus, on the second day the student *p*[*i*] (1<=≤<=*i*<=≤<=*n*) studies the *i*-th student's notes, on the third day the notes go to student *p*[*p*[*i*]] and so on. Due to some characteristics of the boys' friendship (see paragraph 1), each day each student has exactly one notebook to study.

You are given two sequences that describe the situation on the third and fourth days of revising:
 -  *a*1,<=*a*2,<=...,<=*a**n*, where *a**i* means the student who gets the *i*-th student's notebook on the third day of revising; -  *b*1,<=*b*2,<=...,<=*b**n*, where *b**i* means the student who gets the *i*-th student's notebook on the fourth day of revising. 
You do not know array *p*, that is you do not know who is the best friend to who. Write a program that finds *p* by the given sequences *a* and *b*.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) — the number of students in the group. The second line contains sequence of different integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=*n*). The third line contains the sequence of different integers *b*1,<=*b*2,<=...,<=*b**n* (1<=≤<=*b**i*<=≤<=*n*).

Output Specification:
Print sequence *n* of different integers *p*[1],<=*p*[2],<=...,<=*p*[*n*] (1<=≤<=*p*[*i*]<=≤<=*n*). It is guaranteed that the solution exists and that it is unique.

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

Demo Output:
['4 3 1 2 ', '4 3 2 5 1 ', '2 1 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number n, find the ordered prime signatures and find the number of divisor of n.Any positive integer, ‘n’ can be expressed in the form of its prime factors. If ‘n’ has p_{1}, p_{2},  etc. as its prime factors, then n can be expressed as :
Arrange the obtained exponents of the prime factors of ‘n’ in non-decreasing order. The arrangement thus obtained is called the ordered prime signature of the positive integer ‘n’.
Example 1:
Input: n = 20
Output: 1 2
        6
Explaination: 20 can be written as 2^{2} * 5. The 
ordered pair is 2 1 and the factors are 1, 2, 4, 
5, 10, 20.
Example 2:
Input: n = 13
Output: 1
        2
Explaination: 13 itself is a prime number 
and it has two factors 1 and 13.
Your Task:
You do not need to read input or print anything. Your task is to complete the function orderedPrime() which takes n as input parameter and returns a list containing the powers in non-decreasing manner and the number of factors at the end of the list. The driver code will itself print the number of factors (last element of the returned list) in a new line.
Expected Time Complexity: O(nsqrt(n))
Expected Auxiliary Space: O(n)
Constraints:
2 ≤ n ≤ 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two rectangles on a plane. The centers of both rectangles are located in the origin of coordinates (meaning the center of the rectangle's symmetry). The first rectangle's sides are parallel to the coordinate axes: the length of the side that is parallel to the Ox axis, equals w, the length of the side that is parallel to the Oy axis, equals h. The second rectangle can be obtained by rotating the first rectangle relative to the origin of coordinates by angle α. [Image] 

Your task is to find the area of the region which belongs to both given rectangles. This region is shaded in the picture.


-----Input-----

The first line contains three integers w, h, α (1 ≤ w, h ≤ 10^6; 0 ≤ α ≤ 180). Angle α is given in degrees.


-----Output-----

In a single line print a real number — the area of the region which belongs to both given rectangles.

The answer will be considered correct if its relative or absolute error doesn't exceed 10^{ - 6}.


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

Output
0.828427125

Input
6 4 30

Output
19.668384925



-----Note-----

The second sample has been drawn on the picture above.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a tree with N vertices numbered 1 to N, and N-1 edges numbered 1 to N-1.
Edge i connects Vertex a_i and b_i bidirectionally and has a length of 1.
Snuke will paint each vertex white or black.
The niceness of a way of painting the graph is \max(X, Y), where X is the maximum among the distances between white vertices, and Y is the maximum among the distances between black vertices.
Here, if there is no vertex of one color, we consider the maximum among the distances between vertices of that color to be 0.
There are 2^N ways of painting the graph. Compute the sum of the nicenesses of all those ways, modulo (10^{9}+7).

-----Constraints-----
 - 2 \leq N \leq 2 \times 10^{5}
 - 1 \leq a_i, b_i \leq N
 - The given graph is a tree.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

-----Output-----
Print the sum of the nicenesses of the ways of painting the graph, modulo (10^{9}+7).

-----Sample Input-----
2
1 2

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

 - If we paint Vertex 1 and 2 the same color, the niceness will be 1; if we paint them different colors, the niceness will be 0.
 - The sum of those nicenesses is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is Catmas time again, and that means a lot of stress for everyone. In the Kattis family everyone used to buy gifts for everyone else, but this becomes more and more expensive every year, since our family keeps growing. 

To make things easier, we decided that this year each person will buy just one gift. We will then put all the gifts in a big bag and choose an order among ourselves, with all orderings being equally likely. Then, in this order, each person picks a gift from the bag, where each gift is chosen with equal probability. If it is their own gift (which they can easily recognize since everyone in the Kattis family is a creative individual making completely unique Catmas gift wrapping), they put it back in the bag and pick another gift. This can take some time, since it might happen that somebody picks their own gift a few times in a row.

This strategy is not perfect, because the last person might still end up with their own gift. When this happens, everyone has to put their gifts back in the bag, and then we restart the entire process all over from the beginning. Now the question is, how long will we have to wait until the process ends and we can start opening our Catmas gifts? Specifically, given the size $n$ of our family, what is the expected total number of gifts taken out of the bag until the process ends and everyone has gotten their gift?

-----Input-----
The input contains one line with one integer $n$ ($2\leq n\leq 1000$) – the current size of the Kattis family.

-----Output-----
Output the expected total number of gifts taken out of the bag, accurate to within an absolute error of at most $10^{-6}$.

-----Examples-----
Sample Input:
2
Sample Output:
3.000000000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
George has recently entered the BSUCP (Berland State University for Cool Programmers). George has a friend Alex who has also entered the university. Now they are moving into a dormitory. 

George and Alex want to live in the same room. The dormitory has *n* rooms in total. At the moment the *i*-th room has *p**i* people living in it and the room can accommodate *q**i* people in total (*p**i*<=≤<=*q**i*). Your task is to count how many rooms has free place for both George and Alex.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=100) — the number of rooms.

The *i*-th of the next *n* lines contains two integers *p**i* and *q**i* (0<=≤<=*p**i*<=≤<=*q**i*<=≤<=100) — the number of people who already live in the *i*-th room and the room's capacity.

Output Specification:
Print a single integer — the number of rooms where George and Alex can move in.

Demo Input:
['3\n1 1\n2 2\n3 3\n', '3\n1 10\n0 10\n10 10\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tomya is a girl. She loves Chef Ciel very much.

Tomya like a positive integer p, and now she wants to get a receipt of Ciel's restaurant whose total price is exactly p.
The current menus of Ciel's restaurant are shown the following table.
Name of Menupriceeel flavored water1deep-fried eel bones2clear soup made with eel livers4grilled eel livers served with grated radish8savory egg custard with eel16eel fried rice (S)32eel fried rice (L)64grilled eel wrapped in cooked egg128eel curry rice256grilled eel over rice512deluxe grilled eel over rice1024eel full-course2048

Note that the i-th menu has the price 2i-1 (1 ≤ i ≤ 12).

Since Tomya is a pretty girl, she cannot eat a lot.
So please find the minimum number of menus whose total price is exactly p.
Note that if she orders the same menu twice, then it is considered as two menus are ordered. (See Explanations for details)

-----Input-----

The first line contains an integer T, the number of test cases.
Then T test cases follow.
Each test case contains an integer p.

-----Output-----

For each test case, print the minimum number of menus whose total price is exactly p.

-----Constraints-----

1 ≤ T ≤ 5

1 ≤ p ≤ 100000 (105)

There exists combinations of menus whose total price is exactly p.

-----Sample Input-----
4
10
256
255
4096

-----Sample Output-----
2
1
8
2

-----Explanations-----

In the first sample, examples of the menus whose total price is 10 are the following:

1+1+1+1+1+1+1+1+1+1 = 10 (10 menus)

1+1+1+1+1+1+1+1+2 = 10 (9 menus)

2+2+2+2+2 = 10 (5 menus)

2+4+4 = 10 (3 menus)

2+8 = 10 (2 menus)

Here the minimum number of menus is 2.

In the last sample, the optimal way is 2048+2048=4096 (2 menus).
Note that there is no menu whose price is 4096.

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