vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Navi is at the Beer Bar where he has ordered N beers. After seeing his love with the beers, Bar's Manager has decided to make as much money as they can by asking Navi to pay  K * i^3 Rupees for the i^th beer. But Navi has only M Rupees in his purse. So you are required to lent him some money so that he can still be able to pay for all of the N beers.

Input:

First line will contain T (No. of test cases).
Each test case will contain only one line having three space separated integers : N, K and M
Output:

For every test case, print the required answer in a new line.

Constraints: 
1 ≤ T ≤ 10^5
1 ≤ N, K ≤ 10^3
1 ≤ M ≤ 10^6
Sample Code:

  #include <iostream>
    using namespace std;

    int main()
    {
        //taking input for number of test cases, T.
        cin>>T;

        //For every test case, taking input for N , K and M.
        cin>>N>>K>>M;
        //let the answer be in variable **Ans**
        cout << Ans << endl; //print your answer for every test case.
        return 0;
    }

SAMPLE INPUT
1
2 2 10

SAMPLE OUTPUT
8

Explanation

Total Money required is : 2 * 1^3 + 2 * 2^3 = 18 but he already has 10 so ans is 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
ASC Week 1 Challenge 4 (Medium #1) 

Write a function that converts any sentence into a V  A  P  O  R  W  A  V  E sentence. a V  A  P  O  R  W  A  V  E sentence converts all the letters into uppercase, and adds 2 spaces between each letter (or special character) to create this V  A  P  O  R  W  A  V  E effect.

Examples:
```javascript 
  vaporcode("Lets go to the movies") // output => "L  E  T  S  G  O  T  O  T  H  E  M  O  V  I  E  S"
  vaporcode("Why isn't my code working?") // output => "W  H  Y  I  S  N  '  T  M  Y  C  O  D  E  W  O  R  K  I  N  G  ?"
```
```ruby 
  vaporcode("Lets go to the movies") # output => "L  E  T  S  G  O  T  O  T  H  E  M  O  V  I  E  S"
  vaporcode("Why isn't my code working?") # output => "W  H  Y  I  S  N  '  T  M  Y  C  O  D  E  W  O  R  K  I  N  G  ?"
```
```python 
  vaporcode("Lets go to the movies") # output => "L  E  T  S  G  O  T  O  T  H  E  M  O  V  I  E  S"
  vaporcode("Why isn't my code working?") # output => "W  H  Y  I  S  N  '  T  M  Y  C  O  D  E  W  O  R  K  I  N  G  ?"
```
```crystal 
  vaporcode("Lets go to the movies") # output => "L  E  T  S  G  O  T  O  T  H  E  M  O  V  I  E  S"
  vaporcode("Why isn't my code working?") # output => "W  H  Y  I  S  N  '  T  M  Y  C  O  D  E  W  O  R  K  I  N  G  ?"
```
```cpp 
  vaporcode("Lets go to the movies") // output => "L  E  T  S  G  O  T  O  T  H  E  M  O  V  I  E  S"
  vaporcode("Why isn't my code working?") // output => "W  H  Y  I  S  N  '  T  M  Y  C  O  D  E  W  O  R  K  I  N  G  ?"
```
```haskell 
  vaporcode "Lets go to the movies" 
  -- output => "L  E  T  S  G  O  T  O  T  H  E  M  O  V  I  E  S"
  vaporcode "Why isn't my code working?" 
  -- output => "W  H  Y  I  S  N  '  T  M  Y  C  O  D  E  W  O  R  K  I  N  G  ?"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
David and Martin retired from their jobs and became shepherds. After each winter they need to rebuild the sheep pen. Each year they have a different collection of straight fence segments of various lengths. Naturally, they want to build a sheep pen that covers the largest area. They always spend a lot of time choosing, rearranging, and placing the segments but they are never sure whether they got the optimal solution. Please help them.

-----Input-----
The only input line starts with $n$, the number of fence segments and then contains a list of $n$ integers, the lengths (in meters) of the fence segments. The lengths are integers between $1$ and $100$. The number of fence segments $n$ is between $3$ and $80$.

-----Output-----
The output contains one line with the maximum area (in square meters) of a polygon whose sides have lengths given by the input. Not all segment lengths listed need to be used. Answers with an absolute error of at most $0.005$ will be accepted. If no sheep pen can be built, output $0$.

-----Examples-----
Sample Input 1:
4 1 1 1 1
Sample Output 1:
1.0

Sample Input 2:
3 1 1 1
Sample Output 2:
0.433

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given the participants' score sheet for your University Sports Day, you are required to find the runner-up score. You are given $n$ scores. Store them in a list and find the score of the runner-up. 

Input Format

The first line contains $n$. The second line contains an array $\mbox{A}[$ $\mathrm{~l~}$ of $n$ integers each separated by a space.  

Constraints

$2\leq n\leq10$  
$-100\le A[i]\le100$

Output Format

Print the runner-up score.

Sample Input 0
5
2 3 6 6 5

Sample Output 0
5

Explanation 0

Given list is $[2,3,6,6,5]$. The maximum score is $\boldsymbol{6}$, second maximum is $5$. Hence, we print $5$ as the runner-up score.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an array of positive integers *a*1,<=*a*2,<=...,<=*a**n*<=×<=*T* of length *n*<=×<=*T*. We know that for any *i*<=&gt;<=*n* it is true that *a**i*<==<=*a**i*<=-<=*n*. Find the length of the longest non-decreasing sequence of the given array.

Input Specification:
The first line contains two space-separated integers: *n*, *T* (1<=≤<=*n*<=≤<=100, 1<=≤<=*T*<=≤<=107). The second line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=300).

Output Specification:
Print a single number — the length of a sought sequence.

Demo Input:
['4 3\n3 1 4 2\n']

Demo Output:
['5\n']

Note:
The array given in the sample looks like that: 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4, 2. The elements in bold form the largest non-decreasing subsequence.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
MoEngage has given you an array A consisting of N positive integers.

You should perform Q queries of the following two types:

1 i X : Set A_{i} to X.
2 L R : Find the minimum non-negative integer K such that the sequence [|A_{L} - K|, |A_{L+1} - K|, \ldots, |A_{R-1} - K|, |A_{R} - K|] is sorted in non-decreasing order. Print -1 if no such K exists.

For each query of type 2, output the minimum non-negative integer K satisfying the constraint, or -1 if there isn't any.

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

- The first line contains two integers N, Q.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.
- Then, the i^{th} of the next Q lines contains three integers describing the queries 1 i X or 2 L R.

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

For each query of type 2, output the minimum integer K satisfying the constraint, or -1 if there isn't any in a new line.

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

$1 ≤ N, Q ≤ 2\cdot 10^{5}$
$0 ≤ A_{i}, X ≤ 10^{9}$
$1 ≤ L ≤ R ≤ N$

----- Sample Input 1 ------ 
5 7
5 3 2 6 0
2 1 5
1 2 7
2 1 5
1 4 2
2 1 5
1 2 5
2 1 2
----- Sample Output 1 ------ 
4
-1
5
0

----- explanation 1 ------ 
- In the first query, selecting $K=4$ makes the sequence $[|A_{1} - K|, |A_{2} - K|, |A_{3} - K|, |A_{4} - K|, |A_{5} - K|] = [1, 1, 2, 2, 4]$. This sequence is sorted in non-decreasing order. Also, there exists no value of $K$ less than $4$ satisfying this.

- In the second query, change $A_{2} = 7$. After the second query, the array $A$ becomes $[5, 7, 2, 6, 0]$.

- In the third query, there exists no value of $K$ satisfying the constraints.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Apart from having lots of holidays throughout the year, residents of Berland also have whole lucky years. Year is considered lucky if it has no more than 1 non-zero digit in its number. So years 100, 40000, 5 are lucky and 12, 3001 and 12345 are not.

You are given current year in Berland. Your task is to find how long will residents of Berland wait till the next lucky year.

Input Specification:
The first line contains integer number *n* (1<=≤<=*n*<=≤<=109) — current year in Berland.

Output Specification:
Output amount of years from the current year to the next lucky one.

Demo Input:
['4\n', '201\n', '4000\n']

Demo Output:
['1\n', '99\n', '1000\n']

Note:
In the first example next lucky year is 5. In the second one — 300. In the third — 5000.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke had N cards numbered 1 through N.
Each card has an integer written on it; written on Card i is a_i.
Snuke did the following procedure:
 - Let X and x be the maximum and minimum values written on Snuke's cards, respectively.
 - If X = x, terminate the procedure. Otherwise, replace each card on which X is written with a card on which X-x is written, then go back to step 1.
Under the constraints in this problem, it can be proved that the procedure will eventually terminate. Find the number written on all of Snuke's cards after the procedure.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 10^{5}
 - 1 \leq a_i \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 a_2 \cdots a_N

-----Output-----
Print the number written on all of Snuke's cards after the procedure.

-----Sample Input-----
3
2 6 6

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

 - At the beginning of the procedure, the numbers written on Snuke's cards are (2,6,6).
 - Since x=2 and X=6, he replaces each card on which 6 is written with a card on which 4 is written.
 - Now, the numbers written on Snuke's cards are (2,4,4).
 - Since x=2 and X=4, he replaces each card on which 4 is written with a card on which 2 is written.
 - Now, the numbers written on Snuke's cards are (2,2,2).
 - Since x=2 and X=2, he terminates the procedure.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A bracket is considered to be any one of the following characters: (, ), {, }, [, or ]. 

Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is balanced if the following conditions are met:

It contains no unmatched brackets.
The subset of brackets enclosed within the confines of a matched pair of brackets  is also a matched pair of brackets.

Given $n$ strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, return YES.  Otherwise, return NO.  

Function Description  

Complete the function isBalanced in the editor below.   

isBalanced has the following parameter(s):

string s: a string of brackets   

Returns   

string: either YES or NO  

Input Format

The first line contains a single integer $n$, the number of strings. 

Each of the next $n$ lines contains a single string $s$, a sequence of brackets.

Constraints

$1\leq n\leq10^3$  
$1\leq|s|\leq10^3$, where $|s|$ is the length of the sequence.  
All chracters in the sequences ∈ { {, }, (, ), [, ] }.

Output Format

For each string, return YES or NO.

Sample Input
STDIN           Function
-----           --------
3               n = 3
{[()]}          first s = '{[()]}'
{[(])}          second s = '{[(])}'
{{[[(())]]}}    third s ='{{[[(())]]}}'

Sample Output
YES
NO
YES

Explanation

The string {[()]} meets both criteria for being a balanced string. 
The string {[(])} is not balanced because the brackets enclosed by the matched pair { and } are not balanced: [(]).      
The string {{[[(())]]}} meets both criteria for being a balanced string.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N print total number of divisors of N. It is guaranteed that N is a multiple of prime numbers less than 10^6.

Input 
First line contains T (number of test cases). 
Next T lines contains integer N.  
Constraints

1 ≤ T ≤ 100 
1 ≤ N ≤ 10^18

SAMPLE INPUT
6
1
2
3
4
5
20

SAMPLE OUTPUT
1
2
2
3
2
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Points and Powers of Two

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are $n$ distinct points on a coordinate line, the coordinate of $i$-th point equals to $x_i$. Choose a subset of the given set of points such that the distance between each pair of points in a subset is an integral power of two. It is necessary to consider each pair of points, not only adjacent. Note that any subset containing one element satisfies the condition above. Among all these subsets, choose a subset with maximum possible size.

In other words, you have to choose the maximum possible number of points $x_{i_1}, x_{i_2}, \dots, x_{i_m}$ such that for each pair $x_{i_j}$, $x_{i_k}$ it is true that $|x_{i_j} - x_{i_k}| = 2^d$ where $d$ is some non-negative integer number (not necessarily the same for each pair of points).

Input Specification:
The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of points.

The second line contains $n$ pairwise distinct integers $x_1, x_2, \dots, x_n$ ($-10^9 \le x_i \le 10^9$) — the coordinates of points.

Output Specification:
In the first line print $m$ — the maximum possible number of points in a subset that satisfies the conditions described above.

In the second line print $m$ integers — the coordinates of points in the subset you have chosen.

If there are multiple answers, print any of them.

Demo Input:
['6\n3 5 4 7 10 12\n', '5\n-1 2 5 8 11\n']

Demo Output:
['3\n7 3 5', '1\n8\n']

Note:
In the first example the answer is $[7, 3, 5]$. Note, that $|7-3|=4=2^2$, $|7-5|=2=2^1$ and $|3-5|=2=2^1$. You can't find a subset having more points satisfying the required property.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Fox And Jumping

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Fox Ciel is playing a game. In this game there is an infinite long tape with cells indexed by integers (positive, negative and zero). At the beginning she is standing at the cell 0.

There are also *n* cards, each card has 2 attributes: length *l**i* and cost *c**i*. If she pays *c**i* dollars then she can apply *i*-th card. After applying *i*-th card she becomes able to make jumps of length *l**i*, i. e. from cell *x* to cell (*x*<=-<=*l**i*) or cell (*x*<=+<=*l**i*).

She wants to be able to jump to any cell on the tape (possibly, visiting some intermediate cells). For achieving this goal, she wants to buy some cards, paying as little money as possible. 

If this is possible, calculate the minimal cost.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=300), number of cards.

The second line contains *n* numbers *l**i* (1<=≤<=*l**i*<=≤<=109), the jump lengths of cards.

The third line contains *n* numbers *c**i* (1<=≤<=*c**i*<=≤<=105), the costs of cards.

Output Specification:
If it is impossible to buy some cards and become able to jump to any cell, output -1. Otherwise output the minimal cost of buying such set of cards.

Demo Input:
['3\n100 99 9900\n1 1 1\n', '5\n10 20 30 40 50\n1 1 1 1 1\n', '7\n15015 10010 6006 4290 2730 2310 1\n1 1 1 1 1 1 10\n', '8\n4264 4921 6321 6984 2316 8432 6120 1026\n4264 4921 6321 6984 2316 8432 6120 1026\n']

Demo Output:
['2\n', '-1\n', '6\n', '7237\n']

Note:
In first sample test, buying one card is not enough: for example, if you buy a card with length 100, you can't jump to any cell whose index is not a multiple of 100. The best way is to buy first and second card, that will make you be able to jump to any cell.

In the second sample test, even if you buy all cards, you can't jump to any cell whose index is not a multiple of 10, so you should output -1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bala's room is in a mess. He's been so busy doing research that he hasn't bothered to clean out his room for months. Now he has decided to sort out all the items in his room and keep only the essential ones. He knows the usefulness of each of the 'N' items that he has, and wants to keep only the 'K' most useful items. Bala is also very forgetful, so he wants a procedure that doesn't require him to remember too many things at once.


Input
The first line of input contains 'T', the number of test cases (1 ≤ T ≤ 100). This is followed by T test cases. Each test case begins with a blank line followed by one line containing two numbers 'N' (number of items), and 'K' (number of essential items) (1 ≤ K ≤ N ≤ 100000000). This is followed by one line containing the usefulness of all the 'N' items, seperated by spaces.



Output
The output should consist of 'T' lines corresponding to the 'T' test cases. Each line should contain one number, which is the sum of the usefulness of the 'K' most useful items.


Example

Input:
2

5 2
10 23 47 3 17

10 4
87 45 99 27 58 100 38 50 31 62


Output:
70
348

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the following game:

There are two players, First and Second, sitting in front of a pile of $n$ stones. First always plays first.
There is a set, $\mbox{S}$, of $m$ distinct integers defined as $S=\{s_0,s_1,\ldots,s_{m-1}\}$.
The players move in alternating turns. During each turn, a player chooses some $s_i\in S$ and splits one of the piles into exactly $s_i$ smaller piles of equal size. If no $s_i$ exists that will split one of the available piles into exactly $s_i$ equal smaller piles, the player loses.
Both players always play optimally.

Given $n$, $m$, and the contents of $\mbox{S}$, find and print the winner of the game. If First wins, print First; otherwise, print Second.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ (the size of the initial pile) and $m$ (the size of the set). 

The second line contains $m$ distinct space-separated integers describing the respective values of $s_0,s_1,\ldots,s_{m-1}$.

Constraints

$1\leq n\leq10^{18}$
$1\leq m\leq10$
$2\leq s_i\leq10^{18}$

Output Format

Print First if the First player wins the game; otherwise, print Second.

Sample Input 0
15 3
5 2 3

Sample Output 0
Second

Explanation 0

The initial pile has $n=15$ stones, and $S=\{5,2,3\}$. During First's initial turn, they have two options:

Split the initial pile into $5$ equal piles, which forces them to lose after the following sequence of turns: 

Split the initial pile into $3$ equal piles, which forces them to lose after the following sequence of turns: 

Because First never has any possible move that puts them on the path to winning, we print Second as our answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer sequence of length N: A_1,A_2,...,A_N. Let us perform Q operations in order. The i-th operation is described by two integers X_i and Y_i. In this operation, we will choose one of the following two actions and perform it:

* Swap the values of A_{X_i} and A_{Y_i}
* Do nothing



There are 2^Q ways to perform these operations. Find the sum of the inversion numbers of the final sequences for all of these ways to perform operations, modulo 10^9+7.

Here, the inversion number of a sequence P_1,P_2,...,P_M is the number of pairs of integers (i,j) such that 1\leq i < j\leq M and P_i > P_j.

Constraints

* 1 \leq N \leq 3000
* 0 \leq Q \leq 3000
* 0 \leq A_i \leq 10^9(1\leq i\leq N)
* 1 \leq X_i,Y_i \leq N(1\leq i\leq Q)
* X_i\neq Y_i(1\leq i\leq Q)
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
A_1
:
A_N
X_1 Y_1
:
X_Q Y_Q


Output

Print the sum of the inversion numbers of the final sequences, modulo 10^9+7.

Examples

Input

3 2
1
2
3
1 2
1 3


Output

6


Input

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


Output

36


Input

9 5
3
1
4
1
5
9
2
6
5
3 5
8 9
7 9
3 2
3 8


Output

425

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the easy version of the problem. The difference between the versions is the constraint on $n$ and the required number of operations. You can make hacks only if all versions of the problem are solved.

There are two binary strings $a$ and $b$ of length $n$ (a binary string is a string consisting of symbols $0$ and $1$). In an operation, you select a prefix of $a$, and simultaneously invert the bits in the prefix ($0$ changes to $1$ and $1$ changes to $0$) and reverse the order of the bits in the prefix.

For example, if $a=001011$ and you select the prefix of length $3$, it becomes $011011$. Then if you select the entire string, it becomes $001001$.

Your task is to transform the string $a$ into $b$ in at most $3n$ operations. It can be proved that it is always possible.


-----Input-----

The first line contains a single integer $t$ ($1\le t\le 1000$)  — the number of test cases. Next $3t$ lines contain descriptions of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 1000$)  — the length of the binary strings.

The next two lines contain two binary strings $a$ and $b$ of length $n$.

It is guaranteed that the sum of $n$ across all test cases does not exceed $1000$.


-----Output-----

For each test case, output an integer $k$ ($0\le k\le 3n$), followed by $k$ integers $p_1,\ldots,p_k$ ($1\le p_i\le n$). Here $k$ is the number of operations you use and $p_i$ is the length of the prefix you flip in the $i$-th operation.


-----Example-----
Input
5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1

Output
3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1



-----Note-----

In the first test case, we have $01\to 11\to 00\to 10$.

In the second test case, we have $01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100$.

In the third test case, the strings are already the same. Another solution is to flip the prefix of length $2$, which will leave $a$ unchanged.

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