vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Rank List

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Another programming contest is over. You got hold of the contest's final results table. The table has the following data. For each team we are shown two numbers: the number of problems and the total penalty time. However, for no team we are shown its final place.

You know the rules of comparing the results of two given teams very well. Let's say that team *a* solved *p**a* problems with total penalty time *t**a* and team *b* solved *p**b* problems with total penalty time *t**b*. Team *a* gets a higher place than team *b* in the end, if it either solved more problems on the contest, or solved the same number of problems but in less total time. In other words, team *a* gets a higher place than team *b* in the final results' table if either *p**a*<=&gt;<=*p**b*, or *p**a*<==<=*p**b* and *t**a*<=&lt;<=*t**b*. 

It is considered that the teams that solve the same number of problems with the same penalty time share all corresponding places. More formally, let's say there is a group of *x* teams that solved the same number of problems with the same penalty time. Let's also say that *y* teams performed better than the teams from this group. In this case all teams from the group share places *y*<=+<=1, *y*<=+<=2, ..., *y*<=+<=*x*. The teams that performed worse than the teams from this group, get their places in the results table starting from the *y*<=+<=*x*<=+<=1-th place.

Your task is to count what number of teams from the given list shared the *k*-th place.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=50). Then *n* lines contain the description of the teams: the *i*-th line contains two integers *p**i* and *t**i* (1<=≤<=*p**i*,<=*t**i*<=≤<=50) — the number of solved problems and the total penalty time of the *i*-th team, correspondingly. All numbers in the lines are separated by spaces.

Output Specification:
In the only line print the sought number of teams that got the *k*-th place in the final results' table.

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

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

Note:
The final results' table for the first sample is: 
 -  1-3 places — 4 solved problems, the penalty time equals 10 -  4 place — 3 solved problems, the penalty time equals 20 -  5-6 places — 2 solved problems, the penalty time equals 1 -  7 place — 1 solved problem, the penalty time equals 10 
The table shows that the second place is shared by the teams that solved 4 problems with penalty time 10. There are 3 such teams.

The final table for the second sample is:
 -  1 place — 5 solved problems, the penalty time equals 3 -  2-5 places — 3 solved problems, the penalty time equals 1 
The table shows that the fourth place is shared by the teams that solved 3 problems with penalty time 1. There are 4 such teams.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: The Wall (easy)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
"The zombies are lurking outside. Waiting. Moaning. And when they come..."

"When they come?"

"I hope the Wall is high enough."

Zombie attacks have hit the Wall, our line of defense in the North. Its protection is failing, and cracks are showing. In places, gaps have appeared, splitting the wall into multiple segments. We call on you for help. Go forth and explore the wall! Report how many disconnected segments there are.

The wall is a two-dimensional structure made of bricks. Each brick is one unit wide and one unit high. Bricks are stacked on top of each other to form columns that are up to *R* bricks high. Each brick is placed either on the ground or directly on top of another brick. Consecutive non-empty columns form a wall segment. The entire wall, all the segments and empty columns in-between, is *C* columns wide.

Input Specification:
The first line of the input consists of two space-separated integers *R* and *C*, 1<=≤<=*R*,<=*C*<=≤<=100. The next *R* lines provide a description of the columns as follows: 
 -  each of the *R* lines contains a string of length *C*, -  the *c*-th character of line *r* is B if there is a brick in column *c* and row *R*<=-<=*r*<=+<=1, and . otherwise.

Output Specification:
The number of wall segments in the input configuration.

Demo Input:
['3 7\n.......\n.......\n.BB.B..\n', '4 5\n..B..\n..B..\nB.B.B\nBBB.B\n', '4 6\n..B...\nB.B.BB\nBBB.BB\nBBBBBB\n', '1 1\nB\n', '10 7\n.......\n.......\n.......\n.......\n.......\n.......\n.......\n.......\n...B...\nB.BB.B.\n', '8 8\n........\n........\n........\n........\n.B......\n.B.....B\n.B.....B\n.BB...BB\n']

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

Note:
In the first sample case, the 2nd and 3rd columns define the first wall segment, and the 5th column defines the second.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of names (consisting of lowercase characters) of candidates in an election. A candidate name in array represents a vote casted to the candidate. Print the name of candidate that received Max votes. If there is tie, print lexicographically smaller name.
Example 1:
Input:
n = 13
Votes[] = {john,johnny,jackie,johnny,john 
jackie,jamie,jamie,john,johnny,jamie,
johnny,john}
Output: john 4
Explanation: john has 4 votes casted for 
him, but so does johny. john is 
lexicographically smaller, so we print 
john and the votes he received.
Example 2:
Input:
n = 3
Votes[] = {andy,blake,clark}
Output: andy 1
Explanation: All the candidates get 1 
votes each. We print andy as it is 
lexicographically smaller.
Your Task:
You only need to complete the function winner() that takes an array of strings arr, and n as parameters and returns the name of the candiate with maximum votes and the number of votes the candidate got as an array of size 2.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 <= n <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For months Maxim has been coming to work on his favorite bicycle. And quite recently he decided that he is ready to take part in a cyclists' competitions.

He knows that this year n competitions will take place. During the i-th competition the participant must as quickly as possible complete a ride along a straight line from point si to point fi (si < fi).

Measuring time is a complex process related to usage of a special sensor and a time counter. Think of the front wheel of a bicycle as a circle of radius r. Let's neglect the thickness of a tire, the size of the sensor, and all physical effects. The sensor is placed on the rim of the wheel, that is, on some fixed point on a circle of radius r. After that the counter moves just like the chosen point of the circle, i.e. moves forward and rotates around the center of the circle.

At the beginning each participant can choose any point bi, such that his bike is fully behind the starting line, that is, bi < si - r. After that, he starts the movement, instantly accelerates to his maximum speed and at time tsi, when the coordinate of the sensor is equal to the coordinate of the start, the time counter starts. The cyclist makes a complete ride, moving with his maximum speed and at the moment the sensor's coordinate is equal to the coordinate of the finish (moment of time tfi), the time counter deactivates and records the final time. Thus, the counter records that the participant made a complete ride in time tfi - tsi.

<image>

Maxim is good at math and he suspects that the total result doesn't only depend on his maximum speed v, but also on his choice of the initial point bi. Now Maxim is asking you to calculate for each of n competitions the minimum possible time that can be measured by the time counter. The radius of the wheel of his bike is equal to r.

Input

The first line contains three integers n, r and v (1 ≤ n ≤ 100 000, 1 ≤ r, v ≤ 109) — the number of competitions, the radius of the front wheel of Max's bike and his maximum speed, respectively. 

Next n lines contain the descriptions of the contests. The i-th line contains two integers si and fi (1 ≤ si < fi ≤ 109) — the coordinate of the start and the coordinate of the finish on the i-th competition.

Output

Print n real numbers, the i-th number should be equal to the minimum possible time measured by the time counter. Your answer will be considered correct if its absolute or relative error will not exceed 10 - 6. 

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

Examples

Input

2 1 2
1 10
5 9


Output

3.849644710502
1.106060157705

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
N Soldiers are lined up for a memory test. They are numbered from 0 to N-1 from left to right.


In the test, there are M rounds. In each round, Captain selects one position. Soldier at that position will be numbered 0. All the soldiers to the right of selected position will be numbered one greater than the soldier to his left. All the soldiers to the left of selected position will be numbered one greater than the soldier to his right. 
eg. if N = 6 and selected position is 3, then the numbering will be [3, 2, 1, 0, 1, 2].


 After M rounds, Captain asked each soldier to shout out the greatest number he was assigned during the M rounds. In order to check the correctness, Captain asked you to produce the correct values for each soldier (That is the correct value each soldier should shout out).


Input
The first line of the input contains an integer T denoting the number of test cases.
First line of each test case contains two integers, N and M.
Second line of each test case contains M integers, the positions selected by Captain, in that order.

Output
For each test case, output one line with N space separated integers.

Constraints

1 ≤ T ≤ 10^4
1 ≤ N ≤ 10^5
1 ≤ M ≤ 10^5
1 ≤ Sum of N over all testcases ≤ 10^5
1 ≤ Sum of M over all testcases ≤ 10^5
0 ≤ Positions selected by captain ≤ N-1


Example
Input
2
4 1
1
6 2
2 3

Output
1 0 1 2
3 2 1 1 2 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have two friends. You want to present each of them several positive integers. You want to present cnt_1 numbers to the first friend and cnt_2 numbers to the second friend. Moreover, you want all presented numbers to be distinct, that also means that no number should be presented to both friends.

In addition, the first friend does not like the numbers that are divisible without remainder by prime number x. The second one does not like the numbers that are divisible without remainder by prime number y. Of course, you're not going to present your friends numbers they don't like.

Your task is to find such minimum number v, that you can form presents using numbers from a set 1, 2, ..., v. Of course you may choose not to present some numbers at all.

A positive integer number greater than 1 is called prime if it has no positive divisors other than 1 and itself.


-----Input-----

The only line contains four positive integers cnt_1, cnt_2, x, y (1 ≤ cnt_1, cnt_2 < 10^9; cnt_1 + cnt_2 ≤ 10^9; 2 ≤ x < y ≤ 3·10^4) — the numbers that are described in the statement. It is guaranteed that numbers x, y are prime.


-----Output-----

Print a single integer — the answer to the problem.


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

Output
5

Input
1 3 2 3

Output
4



-----Note-----

In the first sample you give the set of numbers {1, 3, 5} to the first friend and the set of numbers {2} to the second friend. Note that if you give set {1, 3, 5} to the first friend, then we cannot give any of the numbers 1, 3, 5 to the second friend. 

In the second sample you give the set of numbers {3} to the first friend, and the set of numbers {1, 2, 4} to the second friend. Thus, the answer to the problem is 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. KM, the mayor of KM city, decided to build a new elementary school. The site for the school has an awkward polygonal shape, which caused several problems. The most serious problem was that there was not enough space for a short distance racetrack. Your task is to help Mr. KM to calculate the maximum possible length for the racetrack that can be built in the site. The track can be considered as a straight line segment whose width can be ignored. The boundary of the site has a simple polygonal shape without self-intersection, and the track can touch the boundary. Note that the boundary might not be convex.



Input

The input consists of multiple test cases, followed by a line containing "0". Each test case has the following format. The first line contains an integer N (3 \leq N \leq 100). Each of the following N lines contains two integers x_i and y_i (-1,000 \leq x_i, y_i \leq 1,000), which describe the coordinates of a vertex of the polygonal border of the site, in counterclockwise order.

Output

For each test case, print its case number and the maximum possible length of the track in a line. The answer should be given as a floating point number with an absolute error of at most 10^{-6}.

Example

Input

4
0 0
10 0
10 10
0 10
3
0 0
1 0
0 1
0


Output

Case 1: 14.142135624
Case 2: 1.41421356

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

## Input

A positive integer:
```
0 < n < 1000000000
```

## Output

The end result of the base reduction.

If it cannot be fully reduced (reduced down to a single-digit number), return -1.

Assume that if 150 conversions from base 11 take place in a row, the number cannot be fully reduced.

## Description

Base reduction is a process where a number is inputted, repeatedly converted into another base, and then outputted if it cannot be reduced anymore. If it cannot be fully reduced, return -1.

During the base conversions, the number is converted from the lowest base it can be converted from into base 10. For example, 123 would be converted from base 4 to base 10, since base 4 is the lowest base that 123 can be in (123 base 3 is impossible; in base 3, there is no digit 3).

If the lowest possible base the number can be converted into is 10, convert the number from base 11 to base 10. For example, 53109 would be converted from base 11 to base 10, since base 10 is the lowest base it can be in.

In the end, you should get a number that cannot be reduced by this process (a single digit number).

## Example

Starting with 5312:
```
5312 base 6 = 1196 base 10
1196 base 11 = 1557 base 10
1557 base 8 = 879 base 10
879 base 11 = 1054 base 10
1054 base 6 = 250 base 10
250 base 6 = 102 base 10
102 base 3 = 11 base 10
11 base 2 = 3 base 10
```
The output would be 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gray code is a form of binary encoding where transitions between consecutive numbers differ by only one bit. This is a useful encoding for reducing hardware data hazards with values that change rapidly and/or connect to slower hardware as inputs. It is also useful for generating inputs for Karnaugh maps.

Here is an exemple of what the code look like:

```
0:    0000
1:    0001
2:    0011
3:    0010
4:    0110
5:    0111
6:    0101
7:    0100
8:    1100
```

The goal of this kata is to build two function bin2gray and gray2bin wich will convert natural binary to Gray Code and vice-versa. We will use the "binary reflected Gray code". The input and output will be arrays of 0 and 1, MSB at index 0.

There are "simple" formula to implement these functions. It is a very interesting exercise to find them by yourself.

All input will be correct binary arrays.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
For the given set `S` its powerset is the set of all possible subsets of `S`.

Given an array of integers nums, your task is to return the powerset of its elements.

Implement an algorithm that does it in a depth-first search fashion. That is, for every integer in the set, we can either choose to take or not take it. At first, we choose `NOT` to take it, then we choose to take it(see more details in exampele).

# Example

For `nums = [1, 2]`, the output should be `[[], [2], [1], [1, 2]].`

Here's how the answer is obtained:
```
don't take element 1
----don't take element 2
--------add []
----take element 2
--------add [2]
take element 1
----don't take element 2
--------add [1]
----take element 2
--------add [1, 2]```

For `nums = [1, 2, 3]`, the output should be 

`[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]`.

# Input/Output

`[input]` integer array `nums`

Array of positive integers, `1 ≤ nums.length ≤ 10`.

[output] 2D integer array

The powerset of nums.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Baby Badawy's first words were "AND 0 SUM BIG", so he decided to solve the following problem. Given two integers $n$ and $k$, count the number of arrays of length $n$ such that:

all its elements are integers between $0$ and $2^k-1$ (inclusive);

the bitwise AND of all its elements is $0$;

the sum of its elements is as large as possible.

Since the answer can be very large, print its remainder when divided by $10^9+7$.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10$) — the number of test cases you need to solve.

Each test case consists of a line containing two integers $n$ and $k$ ($1 \le n \le 10^{5}$, $1 \le k \le 20$).


-----Output-----

For each test case, print the number of arrays satisfying the conditions. Since the answer can be very large, print its remainder when divided by $10^9+7$.


-----Examples-----

Input
2
2 2
100000 20
Output
4
226732710


-----Note-----

In the first example, the $4$ arrays are:

$[3,0]$,

$[0,3]$,

$[1,2]$,

$[2,1]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Since most contestants do not read this part, I have to repeat that Bitlandians are quite weird. They have their own jobs, their own working method, their own lives, their own sausages and their own games!

Since you are so curious about Bitland, I'll give you the chance of peeking at one of these games.

BitLGM and BitAryo are playing yet another of their crazy-looking genius-needed Bitlandish games. They've got a sequence of n non-negative integers a_1, a_2, ..., a_{n}. The players make moves in turns. BitLGM moves first. Each player can and must do one of the two following actions in his turn:

  Take one of the integers (we'll denote it as a_{i}). Choose integer x (1 ≤ x ≤ a_{i}). And then decrease a_{i} by x, that is, apply assignment: a_{i} = a_{i} - x.  Choose integer x $(1 \leq x \leq \operatorname{min}_{i = 1} a_{i})$. And then decrease all a_{i} by x, that is, apply assignment: a_{i} = a_{i} - x, for all i. 

The player who cannot make a move loses.

You're given the initial sequence a_1, a_2, ..., a_{n}. Determine who wins, if both players plays optimally well and if BitLGM and BitAryo start playing the described game in this sequence.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 3).

The next line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} < 300).


-----Output-----

Write the name of the winner (provided that both players play optimally well). Either "BitLGM" or "BitAryo" (without the quotes).


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

Output
BitLGM

Input
2
1 2

Output
BitAryo

Input
3
1 2 1

Output
BitLGM

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp analyzes the prices of the new berPhone. At his disposal are the prices for $n$ last days: $a_1, a_2, \dots, a_n$, where $a_i$ is the price of berPhone on the day $i$.

Polycarp considers the price on the day $i$ to be bad if later (that is, a day with a greater number) berPhone was sold at a lower price. For example, if $n=6$ and $a=[3, 9, 4, 6, 7, 5]$, then the number of days with a bad price is $3$ — these are days $2$ ($a_2=9$), $4$ ($a_4=6$) and $5$ ($a_5=7$).

Print the number of days with a bad price.

You have to answer $t$ independent data sets.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10000$) — the number of sets of input data in the test. Input data sets must be processed independently, one after another.

Each input data set consists of two lines. The first line contains an integer $n$ ($1 \le n \le 150000$) — the number of days. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the price on the $i$-th day.

It is guaranteed that the sum of $n$ over all data sets in the test does not exceed $150000$.


-----Output-----

Print $t$ integers, the $j$-th of which should be equal to the number of days with a bad price in the $j$-th input data set.


-----Example-----
Input
5
6
3 9 4 6 7 5
1
1000000
2
2 1
10
31 41 59 26 53 58 97 93 23 84
7
3 2 1 2 3 4 5

Output
3
0
1
8
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A consisting of N integers. A group of disjoint subarrays in it will be a collection of subarrays of the array. Formally a group of subarrays consisting of K subarrays can be denoted by 2 * K indices, [i1, j1], [i2, j2] , ..., [iK, jK], such that i1 ≤ j1 < i2 ≤ j2 < ... < iK ≤ jK.

For example, in array A = {5, 6, 7}. A group of subarrays could be the subarrays denoted by indices [1, 1], [2, 3]. The subarray corresponding to indices [1, 1] will be {5}. The subarray corresponding to indices [2, 3] will be {6, 7}. So, we have i1 = 1, j1 = 1, i2 = 2, j2 = 3 and K = 2. You can check that the indices satisfy the property i1 ≤ j1 < i2 ≤ j2.

Note that the group of subarrays [1, 2] and [2, 3] won't be disjoint, as it does not satisfy the property j1 < i2. In other words, the index 2 is common in two subarrays, which should not happen.

Let M denote the maximum value of K in a group of K disjoint subarrays of array A, such that there are not two elements (not indices) common in those subarrays. This means, that if the group contained subarrays [A[i1], A[j1], [A[i2], A[j2]] , ..., A[[iK, jK]], then there should not be an element which is present in more than one subarrays.

You have to find maximum number of group of disjoint subarrays that number of subarrays in those groups are equal to M. As the answer could be large, output it modulo 109 + 7.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
First line of the each test case contains a single integer N denoting number of elements in array A.
Second line of each test case contains N space separated integers denoting the elements of the array A

-----Output-----
For each test case, output a single line corresponding to maximum number of group of disjoint subarrays of array A.

-----Constraints-----
- 1 ≤ T, N ≤ 105
- 1 ≤ Ai ≤ n
- Sum of N over all the test cases in a single file won't exceed 105

-----Subtasks-----
Subtask #1 (30 points)

- 1 ≤ T, N ≤ 103
- 1 ≤ Ai ≤ n
- Sum of N over all the test cases in a single file won't exceed 103

Subtask #2 (70 points)
- original constraints

-----Example-----
Input
3
2
3 4
3
1 2 2
5
1 1 2 2 2

Output:
1
3
18

-----Explanation-----
Example case 1. M will be equal to 2. The subarrays will be {[1, 1], [2, 2]}.
Example case 2. M will be equal to 3. The subarrays will be {[1, 1], [2, 2]}, {[1, 1], [3, 3]} and {[1, 1], [2, 3]}. Note that {[2, 2], [3, 3]} won't be a non-intersecting subarray as A[2] = 2 and A[3] = 2. So, 2 is common in both these subarrays.

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