vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
As you probably know, Anton goes to school. One of the school subjects that Anton studies is Bracketology. On the Bracketology lessons students usually learn different sequences that consist of round brackets (characters "(" and ")" (without quotes)).

On the last lesson Anton learned about the regular simple bracket sequences (RSBS). A bracket sequence s of length n is an RSBS if the following conditions are met:

  It is not empty (that is n ≠ 0).  The length of the sequence is even.  First $\frac{n}{2}$ charactes of the sequence are equal to "(".  Last $\frac{n}{2}$ charactes of the sequence are equal to ")". 

For example, the sequence "((()))" is an RSBS but the sequences "((())" and "(()())" are not RSBS.

Elena Ivanovna, Anton's teacher, gave him the following task as a homework. Given a bracket sequence s. Find the number of its distinct subsequences such that they are RSBS. Note that a subsequence of s is a string that can be obtained from s by deleting some of its elements. Two subsequences are considered distinct if distinct sets of positions are deleted.

Because the answer can be very big and Anton's teacher doesn't like big numbers, she asks Anton to find the answer modulo 10^9 + 7.

Anton thought of this task for a very long time, but he still doesn't know how to solve it. Help Anton to solve this task and write a program that finds the answer for it!


-----Input-----

The only line of the input contains a string s — the bracket sequence given in Anton's homework. The string consists only of characters "(" and ")" (without quotes). It's guaranteed that the string is not empty and its length doesn't exceed 200 000.


-----Output-----

Output one number — the answer for the task modulo 10^9 + 7.


-----Examples-----
Input
)(()()

Output
6

Input
()()()

Output
7

Input
)))

Output
0



-----Note-----

In the first sample the following subsequences are possible:

  If we delete characters at the positions 1 and 5 (numbering starts with one), we will get the subsequence "(())".  If we delete characters at the positions 1, 2, 3 and 4, we will get the subsequence "()".  If we delete characters at the positions 1, 2, 4 and 5, we will get the subsequence "()".  If we delete characters at the positions 1, 2, 5 and 6, we will get the subsequence "()".  If we delete characters at the positions 1, 3, 4 and 5, we will get the subsequence "()".  If we delete characters at the positions 1, 3, 5 and 6, we will get the subsequence "()". 

The rest of the subsequnces are not RSBS. So we got 6 distinct subsequences that are RSBS, so the answer is 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has $n$ coins, the value of the $i$-th coin is $a_i$. It is guaranteed that all the values are integer powers of $2$ (i.e. $a_i = 2^d$ for some non-negative integer number $d$).

Polycarp wants to know answers on $q$ queries. The $j$-th query is described as integer number $b_j$. The answer to the query is the minimum number of coins that is necessary to obtain the value $b_j$ using some subset of coins (Polycarp can use only coins he has). If Polycarp can't obtain the value $b_j$, the answer to the $j$-th query is -1.

The queries are independent (the answer on the query doesn't affect Polycarp's coins).


-----Input-----

The first line of the input contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of coins and the number of queries.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ — values of coins ($1 \le a_i \le 2 \cdot 10^9$). It is guaranteed that all $a_i$ are integer powers of $2$ (i.e. $a_i = 2^d$ for some non-negative integer number $d$).

The next $q$ lines contain one integer each. The $j$-th line contains one integer $b_j$ — the value of the $j$-th query ($1 \le b_j \le 10^9$).


-----Output-----

Print $q$ integers $ans_j$. The $j$-th integer must be equal to the answer on the $j$-th query. If Polycarp can't obtain the value $b_j$ the answer to the $j$-th query is -1.


-----Example-----
Input
5 4
2 4 8 2 4
8
5
14
10

Output
1
-1
3
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Santa Claus has Robot which lives on the infinite grid and can move along its lines. He can also, having a sequence of m points p_1, p_2, ..., p_{m} with integer coordinates, do the following: denote its initial location by p_0. First, the robot will move from p_0 to p_1 along one of the shortest paths between them (please notice that since the robot moves only along the grid lines, there can be several shortest paths). Then, after it reaches p_1, it'll move to p_2, again, choosing one of the shortest ways, then to p_3, and so on, until he has visited all points in the given order. Some of the points in the sequence may coincide, in that case Robot will visit that point several times according to the sequence order.

While Santa was away, someone gave a sequence of points to Robot. This sequence is now lost, but Robot saved the protocol of its unit movements. Please, find the minimum possible length of the sequence.


-----Input-----

The first line of input contains the only positive integer n (1 ≤ n ≤ 2·10^5) which equals the number of unit segments the robot traveled. The second line contains the movements protocol, which consists of n letters, each being equal either L, or R, or U, or D. k-th letter stands for the direction which Robot traveled the k-th unit segment in: L means that it moved to the left, R — to the right, U — to the top and D — to the bottom. Have a look at the illustrations for better explanation.


-----Output-----

The only line of input should contain the minimum possible length of the sequence.


-----Examples-----
Input
4
RURD

Output
2

Input
6
RRULDD

Output
2

Input
26
RRRULURURUULULLLDLDDRDRDLD

Output
7

Input
3
RLL

Output
2

Input
4
LRLR

Output
4



-----Note-----

The illustrations to the first three tests are given below.

[Image] [Image] [Image]

The last example illustrates that each point in the sequence should be counted as many times as it is presented in the sequence.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Wilbur the pig really wants to be a beaver, so he decided today to pretend he is a beaver and bite at trees to cut them down.

There are n trees located at various positions on a line. Tree i is located at position xi. All the given positions of the trees are distinct.

The trees are equal, i.e. each tree has height h. Due to the wind, when a tree is cut down, it either falls left with probability p, or falls right with probability 1 - p. If a tree hits another tree while falling, that tree will fall in the same direction as the tree that hit it. A tree can hit another tree only if the distance between them is strictly less than h. 

For example, imagine there are 4 trees located at positions 1, 3, 5 and 8, while h = 3 and the tree at position 1 falls right. It hits the tree at position 3 and it starts to fall too. In it's turn it hits the tree at position 5 and it also starts to fall. The distance between 8 and 5 is exactly 3, so the tree at position 8 will not fall.

As long as there are still trees standing, Wilbur will select either the leftmost standing tree with probability 0.5 or the rightmost standing tree with probability 0.5. Selected tree is then cut down. If there is only one tree remaining, Wilbur always selects it. As the ground is covered with grass, Wilbur wants to know the expected total length of the ground covered with fallen trees after he cuts them all down because he is concerned about his grass-eating cow friends. Please help Wilbur.

Input

The first line of the input contains two integers, n (1 ≤ n ≤ 2000) and h (1 ≤ h ≤ 108) and a real number p (0 ≤ p ≤ 1), given with no more than six decimal places.

The second line of the input contains n integers, x1, x2, ..., xn ( - 108 ≤ xi ≤ 108) in no particular order.

Output

Print a single real number — the expected total length of the ground covered by trees when they have all fallen down. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if <image>.

Examples

Input

2 2 0.500000
1 2


Output

3.250000000


Input

4 3 0.4
4 3 1 2


Output

6.631200000

Note

Consider the first example, we have 2 trees with height 2. 

<image> There are 3 scenarios: 

1. Both trees falls left. This can either happen with the right tree falling left first, which has <image> probability (also knocking down the left tree), or the left tree can fall left and then the right tree can fall left, which has <image> probability. Total probability is <image>. 

2. Both trees fall right. This is analogous to (1), so the probability of this happening is <image>. 

3. The left tree fall left and the right tree falls right. This is the only remaining scenario so it must have <image> probability. 

Cases 1 and 2 lead to a total of 3 units of ground covered, while case 3 leads to a total of 4 units of ground covered. Thus, the expected value is <image>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is the last day of covid and you are coming back to your home with two empty sacks. On
the way to your home, you found Ambani brothers donating all their wealth in form of coins
after getting fed up with all the money they have. The coins have both positive and negative
values and they are laid down in a line. Now as you don’t want to go with an empty sack so
you also decided to take some of the money being given by Ambani’s. But anyone who
wants the money has to follow a rule that he/she can choose an only contiguous segment of
coins which are lying in a line (you can also imagine it like an array of coins) whether its value
is positive or negative.
Formally according to the rule if you are given an array [-1,2,3,4,2,0] you can only choose
subarrays like [2,3], [4,2,0], [-1] , [-1,2,3,4,2,0] etc.
Now as you have two siblings you decided to fill both the sacks with some coins. Your task is
to choose the coins in such a way that the sum of values of all the coins(including sacks 1
and 2) is maximum and both sacks are non-empty.
For e.g.:
If the array of coins is:
-1 2 3 4 -3 -5 6 7 1
Following are some ways you can choose the coins:
2 3 4 and -5 6 7
-1 2 3 and 6 7 1
2 3 4 and 6 7 1
and so on….
You can see that among the given ways the 3rd way will yield maximum values (2+3+4) +
(6+7+1)=23
Note: 
Both the sack should be non-empty.
A subarray is a contiguous part of an array. An array that is inside another array.
A coin can be inserted in one and only one sacks i.e you cannot choose a coin more than one time.

-----Input:-----
- The first line contains $n$, the number of coins in the array $c$.
- The next line will contain $n$ space integers denoting the value $coin$ $c[i]$.

-----Output:-----
One and the only line containing the maximum possible sum of values of all the coins in
both sacks.

-----Constraints-----
- $2 \leq n \leq 10^5$
- $-10^5 \leq c[i] \leq 10^5$

-----Sample Input 1:-----
9

-1 2 3 4 -3 -5 6 7 1

-----Sample Output 1:-----
23

-----Sample Input 2:-----
6

-10 -1 -30 -40 -3 -11

-----Sample Output 2:-----
-4

-----EXPLANATION:-----
In first test case you can easily observe that the sum will be maximum if you choose [2,3,4]
and [6,7,1] contiguous subarrays from the given array.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After a long and successful day of preparing food for the banquet, it is time to clean up. There is a list of n jobs to do before the kitchen can be closed for the night. These jobs are indexed from 1 to n.

Most of the cooks have already left and only the Chef and his assistant are left to clean up. Thankfully, some of the cooks took care of some of the jobs before they left so only a subset of the n jobs remain. The Chef and his assistant divide up the remaining jobs in the following manner. The Chef takes the unfinished job with least index, the assistant takes the unfinished job with the second least index, the Chef takes the unfinished job with the third least index, etc. That is, if the unfinished jobs were listed in increasing order of their index then the Chef would take every other one starting with the first job in the list and the assistant would take every other one starting with the second job on in the list.

The cooks logged which jobs they finished before they left. Unfortunately, these jobs were not recorded in any particular order. Given an unsorted list
of finished jobs, you are to determine which jobs the Chef must complete and which jobs his assitant must complete before closing the kitchen for the 
evening.

-----Input-----

The first line contains a single integer T ≤ 50 indicating the number of test cases to follow. Each test case consists of two lines. The first line contains two numbers n,m satisfying 0 ≤ m ≤ n ≤ 1000. Here, n is the total number of jobs that must be completed before closing and m is the number of jobs that have already been completed. The second line contains a list of m distinct integers between 1 and n. These are the indices of the jobs that have already been completed. Consecutive integers are separated by a single space.

-----Output-----

The output for each test case consists of two lines. The first line is a list of the indices of the jobs assigned to the Chef. The second line is a list of the indices of the jobs assigned to his assistant. Both lists must appear in increasing order of indices and consecutive integers should be separated by a single space. If either the Chef or the assistant is not assigned any jobs, then their corresponding line should be blank.

-----Example-----
Input:
3
6 3
2 4 1
3 2
3 2
8 2
3 8

Output:
3 6
5
1

1 4 6
2 5 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given N items.

The value of the i-th item (1 \leq i \leq N) is v_i.

Your have to select at least A and at most B of these items.

Under this condition, find the maximum possible arithmetic mean of the values of selected items.

Additionally, find the number of ways to select items so that the mean of the values of selected items is maximized.  

-----Constraints-----
 - 1 \leq N \leq 50
 - 1 \leq A,B \leq N
 - 1 \leq v_i \leq 10^{15}
 - Each v_i is an integer.

-----Input-----
The input is given from Standard Input in the following format:
N A B
v_1
v_2
...
v_N

-----Output-----
Print two lines.

The first line should contain the maximum possible arithmetic mean of the values of selected items. The output should be considered correct if the absolute or relative error is at most 10^{-6}.

The second line should contain the number of ways to select items so that the mean of the values of selected items is maximized.

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

-----Sample Output-----
4.500000
1

The mean of the values of selected items will be maximized when selecting the fourth and fifth items. Hence, the first line of the output should contain 4.5.

There is no other way to select items so that the mean of the values will be 4.5, and thus the second line of the output should contain 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Approximating a Constant Range

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
When Xellos was doing a practice course in university, he once had to measure the intensity of an effect that slowly approached equilibrium. A good way to determine the equilibrium intensity would be choosing a sufficiently large number of consecutive data points that seems as constant as possible and taking their average. Of course, with the usual sizes of data, it's nothing challenging — but why not make a similar programming contest problem while we're at it?

You're given a sequence of *n* data points *a*1,<=...,<=*a**n*. There aren't any big jumps between consecutive data points — for each 1<=≤<=*i*<=&lt;<=*n*, it's guaranteed that |*a**i*<=+<=1<=-<=*a**i*|<=≤<=1.

A range [*l*,<=*r*] of data points is said to be almost constant if the difference between the largest and the smallest value in that range is at most 1. Formally, let *M* be the maximum and *m* the minimum value of *a**i* for *l*<=≤<=*i*<=≤<=*r*; the range [*l*,<=*r*] is almost constant if *M*<=-<=*m*<=≤<=1.

Find the length of the longest almost constant range.

Input Specification:
The first line of the input contains a single integer *n* (2<=≤<=*n*<=≤<=100<=000) — the number of data points.

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=100<=000).

Output Specification:
Print a single number — the maximum length of an almost constant range of the given sequence.

Demo Input:
['5\n1 2 3 3 2\n', '11\n5 4 5 5 6 7 8 8 8 7 6\n']

Demo Output:
['4\n', '5\n']

Note:
In the first sample, the longest almost constant range is [2, 5]; its length (the number of data points in it) is 4.

In the second sample, there are three almost constant ranges of length 4: [1, 4], [6, 9] and [7, 10]; the only almost constant range of the maximum length 5 is [6, 10].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For strings s and t, we will say that s and t are prefix-free when neither is a prefix of the other.

Let L be a positive integer. A set of strings S is a good string set when the following conditions hold true:

* Each string in S has a length between 1 and L (inclusive) and consists of the characters `0` and `1`.
* Any two distinct strings in S are prefix-free.



We have a good string set S = \\{ s_1, s_2, ..., s_N \\}. Alice and Bob will play a game against each other. They will alternately perform the following operation, starting from Alice:

* Add a new string to S. After addition, S must still be a good string set.



The first player who becomes unable to perform the operation loses the game. Determine the winner of the game when both players play optimally.

Constraints

* 1 \leq N \leq 10^5
* 1 \leq L \leq 10^{18}
* s_1, s_2, ..., s_N are all distinct.
* { s_1, s_2, ..., s_N } is a good string set.
* |s_1| + |s_2| + ... + |s_N| \leq 10^5

Input

Input is given from Standard Input in the following format:


N L
s_1
s_2
:
s_N


Output

If Alice will win, print `Alice`; if Bob will win, print `Bob`.

Examples

Input

2 2
00
01


Output

Alice


Input

2 2
00
11


Output

Bob


Input

3 3
0
10
110


Output

Alice


Input

2 1
0
1


Output

Bob


Input

1 2
11


Output

Alice


Input

2 3
101
11


Output

Bob

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A friend of mine told me privately: "I don't like palindromes". "why not?" - I replied. "Because when I want to do some programming challenges, I encounter 2 or 3 ones first related with palindromes. I'm fed up" - he confess me with anger. I said to myself:"Thankfully, that doesn't happen in Codewars".
Talking seriously, we have to count the palindrome integers. Doing that, perhaps, it will help us to make all the flood of palindrome programming challenges more understandable.

For example all the integers of 1 digit (not including 0) are palindromes, 9 cases.
We have nine of them with two digits, so the total amount of palidromes below ```100``` (10^(2)) is ```18```.
At least, will we be able to calculate the amount of them for a certain number of digits?
Let's say for ```2000``` digits?
Prepare a code that given the number of digits ```n```, may output the amount of palindromes of length equals to n and the total amount of palindromes below 10^(n).

You will see more examples in the box.
Happy coding!!

(You don't know what palindromes are? Investigate, :))

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alice and Bob begin their day with a quick game. They first choose a starting number *X*0<=≥<=3 and try to reach one million by the process described below. 

Alice goes first and then they take alternating turns. In the *i*-th turn, the player whose turn it is selects a prime number smaller than the current number, and announces the smallest multiple of this prime number that is not smaller than the current number.

Formally, he or she selects a prime *p*<=&lt;<=*X**i*<=-<=1 and then finds the minimum *X**i*<=≥<=*X**i*<=-<=1 such that *p* divides *X**i*. Note that if the selected prime *p* already divides *X**i*<=-<=1, then the number does not change.

Eve has witnessed the state of the game after two turns. Given *X*2, help her determine what is the smallest possible starting number *X*0. Note that the players don't necessarily play optimally. You should consider all possible game evolutions.

Input Specification:
The input contains a single integer *X*2 (4<=≤<=*X*2<=≤<=106). It is guaranteed that the integer *X*2 is composite, that is, is not prime.

Output Specification:
Output a single integer — the minimum possible *X*0.

Demo Input:
['14\n', '20\n', '8192\n']

Demo Output:
['6\n', '15\n', '8191\n']

Note:
In the first test, the smallest possible starting number is *X*<sub class="lower-index">0</sub> = 6. One possible course of the game is as follows: 
 -  Alice picks prime 5 and announces *X*<sub class="lower-index">1</sub> = 10 -  Bob picks prime 7 and announces *X*<sub class="lower-index">2</sub> = 14. 
In the second case, let *X*<sub class="lower-index">0</sub> = 15. 
 -  Alice picks prime 2 and announces *X*<sub class="lower-index">1</sub> = 16 -  Bob picks prime 5 and announces *X*<sub class="lower-index">2</sub> = 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Zonal Computing Olympiad 2015, 29 Nov 2014

An interval is a pair of positive integers [a, b] with a ≤ b. It is meant to denote the set of integers that lie between the values a and b. For example [3,5] denotes the set {3,4,5} while the interval [3, 3] denotes the set {3}.

We say that an interval [a, b] is covered by an integer i, if i belongs to the set defined by [a, b]. For example interval [3, 5] is covered by 3 and so is the interval [3, 3].

Given a set of intervals I, and a set of integers S we say that I is covered by S if for each interval [a, b] in I there is an integer i in S such that [a, b] is covered by i. For example, the set {[3, 5], [3, 3]} is covered by the set {3}. The set of intervals {[6, 9], [3, 5], [4, 8]} is covered by the set {4, 5, 8}. It is also covered by the set {4, 7}.

We would like to compute, for any set of intervals I, the size of the smallest set S that covers it. You can check that for the set of intervals {[6, 9], [3, 5], [4, 8]} the answer is 2 while for the set of intervals {[3, 5], [3, 3]} the answer is 1.

Your program should take the set of intervals as input and output the size of the smallest set that covers it as the answer.

-----Input format-----
The first line contains a single integer N, giving the number of intervals in the input.

This is followed by N lines, each containing two integers separated by a space describing an interval, with the first integer guaranteed to be less than or equal to the second integer.

-----Output format-----
Output a single integer giving the size of the smallest set of integers that covers the given set of intervals.

-----Test data-----
You may assume that all integers in the input are in the range 1 to 10^8 inclusive.

Subtask 1 (100 marks) : 1 ≤ N ≤ 5000.

-----Sample Input 1-----
2 
3 5 
3 3

-----Sample Output 1-----
1

-----Sample Input 2-----
3 
6 9 
3 5 
4 8

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

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