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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* employees in Alternative Cake Manufacturing (ACM). They are now voting on some very important question and the leading world media are trying to predict the outcome of the vote.

Each of the employees belongs to one of two fractions: depublicans or remocrats, and these two fractions have opposite opinions on what should be the outcome of the vote. The voting procedure is rather complicated: 
 1.  Each of *n* employees makes a statement. They make statements one by one starting from employees 1 and finishing with employee *n*. If at the moment when it's time for the *i*-th employee to make a statement he no longer has the right to vote, he just skips his turn (and no longer takes part in this voting). 1.  When employee makes a statement, he can do nothing or declare that one of the other employees no longer has a right to vote. It's allowed to deny from voting people who already made the statement or people who are only waiting to do so. If someone is denied from voting he no longer participates in the voting till the very end. 1.  When all employees are done with their statements, the procedure repeats: again, each employees starting from 1 and finishing with *n* who are still eligible to vote make their statements. 1.  The process repeats until there is only one employee eligible to vote remaining and he determines the outcome of the whole voting. Of course, he votes for the decision suitable for his fraction. 
You know the order employees are going to vote and that they behave optimal (and they also know the order and who belongs to which fraction). Predict the outcome of the vote.

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=200<=000) — the number of employees. 

The next line contains *n* characters. The *i*-th character is 'D' if the *i*-th employee is from depublicans fraction or 'R' if he is from remocrats.

Output Specification:
Print 'D' if the outcome of the vote will be suitable for depublicans and 'R' if remocrats will win.

Demo Input:
['5\nDDRRR\n', '6\nDDRRRR\n']

Demo Output:
['D\n', 'R\n']

Note:
Consider one of the voting scenarios for the first sample: 
 1.  Employee 1 denies employee 5 to vote. 1.  Employee 2 denies employee 3 to vote. 1.  Employee 3 has no right to vote and skips his turn (he was denied by employee 2). 1.  Employee 4 denies employee 2 to vote. 1.  Employee 5 has no right to vote and skips his turn (he was denied by employee 1). 1.  Employee 1 denies employee 4. 1.  Only employee 1 now has the right to vote so the voting ends with the victory of depublicans.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chandu and chandni are playing a game ! Game is very similar to the game of chess, But there is only one piece on the board i.e Queen. Also, Queen is allowed to move only towards top left corner.. 
For clarification, If Queen is placed at i,j then in a turn queen can move:
1) Any number of cells leftwards.
2) Any number of cells upwards.
3) Any number of cells Diagonally(only N-W direction).  

Please note that board is quarter infinite i.e there is a top left corner but it extends to infinity in south and east direction..  

Rules:
1) Chandni will always play the first turn.
2) They both will get alternative turns.
3) They must move the queen in their turn (No skip option) and that too according to the rule specified above.
4) Whosoever is unable to make a move loses.  

Given The position of queen on the board(0 index based). Print who will win the game.  

Input:
First line of input contains an integer t - no of test cases.
Each test case is described as a line containing two integers a and b. which is the position of queen on the board.

Output:
print the name of person who will win the game.

Constraints:
1 ≤ t ≤ 10000
0 ≤ a,b ≤ 1000000  

SAMPLE INPUT
1
1 2

SAMPLE OUTPUT
Chandu

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are positive integers A and B.
Let us choose some number of positive common divisors of A and B.
Here, any two of the chosen divisors must be coprime.
At most, how many divisors can we choose?Definition of common divisor
An integer d is said to be a common divisor of integers x and y when d divides both x and y.Definition of being coprime
Integers x and y are said to be coprime when x and y have no positive common divisors other than 1.Definition of dividing
An integer x is said to divide another integer y when there exists an integer \alpha such that y = \alpha x.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq A, B \leq 10^{12}

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
Print the maximum number of divisors that can be chosen to satisfy the condition.

-----Sample Input-----
12 18

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

12 and 18 have the following positive common divisors: 1, 2, 3, and 6.
1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fox Ciel studies number theory.

She thinks a non-empty set S contains non-negative integers is perfect if and only if for any $a, b \in S$ (a can be equal to b), $(a \text{xor} b) \in S$. Where operation xor means exclusive or operation (http://en.wikipedia.org/wiki/Exclusive_or).

Please calculate the number of perfect sets consisting of integers not greater than k. The answer can be very large, so print it modulo 1000000007 (10^9 + 7).


-----Input-----

The first line contains an integer k (0 ≤ k ≤ 10^9).


-----Output-----

Print a single integer — the number of required sets modulo 1000000007 (10^9 + 7).


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

Output
2

Input
2

Output
3

Input
3

Output
5

Input
4

Output
6



-----Note-----

In example 1, there are 2 such sets: {0} and {0, 1}. Note that {1} is not a perfect set since 1 xor 1 = 0 and {1} doesn't contain zero.

In example 4, there are 6 such sets: {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4} and {0, 1, 2, 3}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job. 
Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i]. 
Every worker can be assigned at most one job, but one job can be completed multiple times.
For example, if 3 people attempt the same job that pays $1, then the total profit will be $3.  If a worker cannot complete any job, his profit is $0.
What is the most profit we can make?
Example 1:
Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100 
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.
Notes:

1 <= difficulty.length = profit.length <= 10000
1 <= worker.length <= 10000
difficulty[i], profit[i], worker[i]  are in range [1, 10^5]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monica decides that she would like to get to know the neighbours in the apartment better. She makes a batch of wonderful chocolates and hangs them on the door in a basket hoping that her neighbors will take some and they can meet. The neighbours (including Joey) eventually go crazy over the candy and demand more. Eventually, she keeps a bowl full of chocolates at the door for the last time.

There are N neighbours. The i^{th} neigbhour has initial energy equal to A_{i}. There is one bowl filled with chocolates. The neighbours are made to stand in a row and the bowl is passed around by obeying the following rules:

Any person can hold the bowl initially. 
If the person holding the bowl has positive energy, he/she passes the bowl to the person on the immediate right of him/her. The rightmost person in the row passes the bowl to the leftmost person in the row. 
The act of passing the bowl takes 1 second. 
If the person holding the bowl has non-positive energy, he/she drops the bowl.  
After each pass, the energy of the person reduces by 1. 

Among all possible ways in which the N neighbours start the game, find the maximum time until the bowl is dropped.

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

- First line will contain T, number of testcases. Then the testcases follow.
- First line of each testcase contains one integer N.
- Second line of each testcase contains of N integers, denoting the elements of array A.

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

For each testcase, output in a single line the maximum time until the bowl is dropped.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A[i] ≤ 10^{6}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

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

----- Sample Output 1 ------ 
4
1
3

----- explanation 1 ------ 
Test case 1: One of the optimal orders in which all the neighbours can stand in the row is:   
$1$ $\rightarrow$ $2$ $\rightarrow$ $3$ $\rightarrow$ $1$. The bowl is initially with person $1$. 
- Person $1$, in one second, passes the bowl to person $2$ and his/her own energy becomes $1$. 
- Person $2$, in one second, passes the bowl to person $3$ and his/her own energy becomes $0$.
- Person $3$, in one second, passes the bowl to person $1$ and his/her own energy becomes $0$.
- Person $1$, in one second, passes the bowl to person $2$ and his/her own energy becomes $0$.
- Person $2$ has $0$ energy, so he/she drops the bowl. 
Thus, the bowl is dropped after $4$ seconds.

Test case 2: One of the optimal orders in which all the neighbours can stand in the row is:   
$2$ $\rightarrow$ $1$ $\rightarrow$ $3$ $\rightarrow$ $2$. The bowl is initially with person $2$. Thus, it would travel as $2$ $\rightarrow$ $1$. The bowl can not be passed further due to $0$ energy of person $1$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
MoEngage has 3 decks. Each deck consists of N cards, numbered from 1 to N. He draws out 1 card from each deck randomly with each card having an equal probability of being drawn.

MoEngage drew cards numbered A and B from the decks 1 and 2 respectively. Now, he wonders what is the probability that he will end up with a *funny hand* after drawing the third card.

A *funny hand* is when 3 consecutive numbered cards are present in your hand.  
Help MoEngage calculate the probability of ending up with a *funny hand* after drawing the third card.

If the final probability of ending up with a *funny hand* is P, you need to print the value P\cdot N. It can be shown that this value is an integer.

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

- First line will contain T, the number of test cases. Then the test cases follow.
- Each test case contains a single line of input consisting of three space-separated integers N, A, and B denoting the size of each deck, the card drawn from the first deck, and the card drawn from the second deck respectively.

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

For each test case, output a single integer, denoting P\cdot N on a separate line.

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

$1 ≤ T ≤ 1000$
$3 ≤ N ≤ 1000$
$1 ≤ A, B ≤ N$

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

----- Sample Output 1 ------ 
2
1
0

----- explanation 1 ------ 
Test case $1$: Drawing the cards $1$ or $4$ will result in a funny hand. Hence, the probability will be $P = \frac{1}{2}$. The value $P \cdot N = \frac{1}{2} \cdot 4 = 2$.

Test case $2$: Drawing the card $3$ will result in a funny hand. Hence, the probability will be $P = \frac{1}{6}$. The value $P \cdot N = \frac{1}{6} \cdot 6 = 1$.

Test case $3$: No matter what card MoEngage draws, he will never end up with a funny hand.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an easier version of the problem. In this version $n \le 1000$

The outskirts of the capital are being actively built up in Berland. The company "Kernel Panic" manages the construction of a residential complex of skyscrapers in New Berlskva. All skyscrapers are built along the highway. It is known that the company has already bought $n$ plots along the highway and is preparing to build $n$ skyscrapers, one skyscraper per plot.

Architects must consider several requirements when planning a skyscraper. Firstly, since the land on each plot has different properties, each skyscraper has a limit on the largest number of floors it can have. Secondly, according to the design code of the city, it is unacceptable for a skyscraper to simultaneously have higher skyscrapers both to the left and to the right of it.

Formally, let's number the plots from $1$ to $n$. Then if the skyscraper on the $i$-th plot has $a_i$ floors, it must hold that $a_i$ is at most $m_i$ ($1 \le a_i \le m_i$). Also there mustn't be integers $j$ and $k$ such that $j < i < k$ and $a_j > a_i < a_k$. Plots $j$ and $k$ are not required to be adjacent to $i$.

The company wants the total number of floors in the built skyscrapers to be as large as possible. Help it to choose the number of floors for each skyscraper in an optimal way, i.e. in such a way that all requirements are fulfilled, and among all such construction plans choose any plan with the maximum possible total number of floors.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 1000$) — the number of plots.

The second line contains the integers $m_1, m_2, \ldots, m_n$ ($1 \leq m_i \leq 10^9$) — the limit on the number of floors for every possible number of floors for a skyscraper on each plot.


-----Output-----

Print $n$ integers $a_i$ — the number of floors in the plan for each skyscraper, such that all requirements are met, and the total number of floors in all skyscrapers is the maximum possible.

If there are multiple answers possible, print any of them.


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

Output
1 2 3 2 1 

Input
3
10 6 8

Output
10 6 6 



-----Note-----

In the first example, you can build all skyscrapers with the highest possible height.

In the second test example, you cannot give the maximum height to all skyscrapers as this violates the design code restriction. The answer $[10, 6, 6]$ is optimal. Note that the answer of $[6, 6, 8]$ also satisfies all restrictions, but is not optimal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke is standing on a two-dimensional plane. In one operation, he can move by 1 in the positive x-direction, or move by 1 in the positive y-direction.
Let us define a function f(r, c) as follows:
 - f(r,c) :=  (The number of paths from the point (0, 0) to the point (r, c) that Snuke can trace by repeating the operation above)
Given are integers r_1, r_2, c_1, and c_2.
Find the sum of f(i, j) over all pair of integers (i, j) such that r_1 ≤ i ≤ r_2 and c_1 ≤ j ≤ c_2, and compute this value modulo (10^9+7).

-----Constraints-----
 - 1 ≤ r_1 ≤ r_2 ≤ 10^6
 - 1 ≤ c_1 ≤ c_2 ≤ 10^6
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
r_1 c_1 r_2 c_2

-----Output-----
Print the sum of f(i, j) modulo (10^9+7).

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

-----Sample Output-----
14

For example, there are two paths from the point (0, 0) to the point (1, 1): (0,0) → (0,1) → (1,1) and (0,0) → (1,0) → (1,1), so f(1,1)=2.
Similarly, f(1,2)=3, f(2,1)=3, and f(2,2)=6. Thus, the sum is 14.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider integer coordinates x, y in the Cartesian plan and three functions f, g, h
defined by:
```
f: 1 <= x <= n, 1 <= y <= n --> f(x, y) = min(x, y)
g: 1 <= x <= n, 1 <= y <= n --> g(x, y) = max(x, y)
h: 1 <= x <= n, 1 <= y <= n --> h(x, y) = x + y
``` 
where n is a given integer (n >= 1, guaranteed) and x, y are integers.

In the table below you can see the value of the function f with n = 6.

  ---|*0* |*1*|*2*|*3*|*4*|*5*|*6*|
  -- |--|--|--|--|--|--|--|
  *6*|- |1 |2 |3 |4 |5 |6 |
  *5*|- |1 |2 |3 |4 |5 |5 |
  *4*|- |1 |2 |3 |4 |4 |4 |
  *3*|- |1 |2 |3 |3 |3 |3 |
  *2*|- |1 |2 |2 |2 |2 |2 |
  *1*|- |1 |1 |1 |1 |1 |1 |
  *0*|- |- |- |- |- |- |- |

The task is to calculate the sum of f(x, y), g(x, y) and h(x, y) for all integers x and y such that (1 <= x <= n, 1 <= y <= n).

The function sumin (sum of f) will take n as a parameter and return the sum of min(x, y) in the domain 1 <= x <= n, 1 <= y <= n.
The function sumax (sum of g) will take n as a parameter and return the sum of max(x, y) in the same domain.
The function sumsum (sum of h) will take n as a parameter and return the sum of x + y in the same domain.


#Examples:
```
sumin(6) --> 91
sumin(45) --> 31395
sumin(999) --> 332833500
sumin(5000) --> 41679167500

sumax(6) --> 161
sumax(45) --> 61755
sumax(999) --> 665167500
sumax(5000) --> 83345832500

sumsum(6) --> 252
sumsum(45) --> 93150
sumsum(999) --> 998001000
sumsum(5000) --> 125025000000
```

#Hint:
1. Try to avoid nested loops
2. Note that h = f + g

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ilya got tired of sports programming, left university and got a job in the subway. He was given the task to determine the escalator load factor. 

Let's assume that n people stand in the queue for the escalator. At each second one of the two following possibilities takes place: either the first person in the queue enters the escalator with probability p, or the first person in the queue doesn't move with probability (1 - p), paralyzed by his fear of escalators and making the whole queue wait behind him.

Formally speaking, the i-th person in the queue cannot enter the escalator until people with indices from 1 to i - 1 inclusive enter it. In one second only one person can enter the escalator. The escalator is infinite, so if a person enters it, he never leaves it, that is he will be standing on the escalator at any following second. Ilya needs to count the expected value of the number of people standing on the escalator after t seconds. 

Your task is to help him solve this complicated task.

Input

The first line of the input contains three numbers n, p, t (1 ≤ n, t ≤ 2000, 0 ≤ p ≤ 1). Numbers n and t are integers, number p is real, given with exactly two digits after the decimal point.

Output

Print a single real number — the expected number of people who will be standing on the escalator after t seconds. The absolute or relative error mustn't exceed 10 - 6.

Examples

Input

1 0.50 1


Output

0.5


Input

1 0.50 4


Output

0.9375


Input

4 0.20 2


Output

0.4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
These days, many carmakers are developing cars that run on electricity instead of gasoline. The batteries used in these cars are generally very heavy and expensive, so designers must make an important tradeoffs when determining the battery capacity, and therefore the range, of these vehicles. Your task is to help determine the minimum range necessary so that it is possible for the car to travel between any two cities on the continent.

The road network on the continent consists of cities connected by bidirectional roads of different lengths. Each city contains a charging station. Along a route between two cities, the car may pass through any number of cities, but the distance between each pair of consecutive cities along the route must be no longer than the range of the car. What is the minimum range of the car so that there is a route satisfying this constraint between every pair of cities on the continent?

-----Input-----
The first line of the input contains two nonnegative integers $n$ and $m$, the number of cities and roads. Each of these integers is no larger than one million. The cities are numbered from 0 to $n-1$. The first line is followed by $m$ more lines, each describing a road. Each such line contains three non-negative integers. The first two integers are the numbers of the two cities connected by the road. The third integer is the length of the road, a positive integer no larger than $10^9$.

-----Output-----
For each road network, output a line containing one integer, the minimum range of the car that enables it to drive from every city to every other city. If it is not possible to drive from some city to some other city regardless of the range of the car, instead output a line containing the word IMPOSSIBLE.

-----Examples-----
Sample Input:
3 3
0 1 3
1 2 4
2 1 5
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a huge blanket on your bed but unfortunately it has N stains. You cover them using 
a single, rectangular silk cloth. The silk is expensive, which is why the rectangular piece needs to have the least area as possible. You love this blanket and decide to minimize the area covering the  stains. You buy some cleaning liquid to remove the stains but sadly it isn't enough to clean all of them. You can just remove exactly K stains. The rest of the stains need to be covered using a single, rectangular fragment of silk cloth.

Let X denote the area of the smallest possible silk cloth that may cover all the stains originally. You need to find the number of different ways in which you may remove K stains so that the remaining N-K stains can be covered with silk of area strictly less than X (We are looking for any configuration that will reduce the cost).

Assume that each stain is a point and that the rectangle is aligned parallel to the axes.  

Input Format

The first line contains two integers N (1<=N<=1000) and K (0<=K<=N). 
Next follow N lines, one for each stain. Each line contains two integers in the form 'X Y', (0<=X,Y<100000), the coordinates of each stain into the blanket. Each pair of coordinates is unique.

Output Format

Output a single integer. The remainder of the division by 1000000007 of the answer.

Sample Input
5 2
0 1
3 3
2 0
0 3
2 3

Sample Output
8

Explanation

We can clean two spots. So removing any of the following set of stains will lead us to a conbination that will need less amount of silk.(The numbers refer to the indices of the stains in the input and they begin from 1).

1, 4
2, 1
2, 3
2, 4
2, 5
3, 1
3, 4
3, 5

So there are 8 ways.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Flash has invited his nemesis The Turtle (He actually was a real villain! ) to play his favourite card game, SNAP. In this game a 52 card deck is dealt out so both Flash and the Turtle get 26 random cards. 

Each players cards will be represented by an array like below

Flash’s pile:
```[ 'A', '5', 'Q', 'Q', '6', '2', 'A', '9', '10', '6', '4', '3', '10', '9', '3', '8', 'K', 'J', 'J', 'K', '7', '9', '5', 'J', '7', '2' ]```

Turtle’s pile:
```[ '8', 'A', '2', 'Q', 'K', '8', 'J', '6', '4', '8', '7', 'A', '5', 'K', '3', 'Q', '6', '9', '4', '3', '4', '10', '2', '7', '10', '5' ]```

The players take it in turn to take the top card from their deck (the first element in their array) and place it in a face up pile in the middle. Flash goes first.

When a card is placed on the face up pile that matches the card it is placed on top of the first player to shout ‘SNAP!’ wins that round. Due to Flash's speed he wins every round.

Face up pile in the middle:
```[ 'A', '8', '5', 'A', 'Q', '2', 'Q', 'Q',```  =>  SNAP!

The face up pile of cards in the middle are added to the bottom of Flash's pile.

Flash’s pile after one round:
```['6', '2', 'A', '9', '10', '6', '4', '3', '10', '9', '3', '8', 'K', 'J', 'J', 'K', '7', '9', '5', 'J', '7', '2', 'A', '8', '5', 'A', 'Q', '2', 'Q', 'Q' ]```

Flash then starts the next round by putting down the next card.

When Turtle runs out of cards the game is over.

How many times does Flash get to call Snap before Turtle runs out of cards?

If both the player put down all their cards into the middle without any matches then the game ends a draw and Flash calls SNAP 0 times.

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