vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The Chef has one long loaf of bread of length 1. He wants to cut it into as many little loaves as he can. But he wants to adhere to the following rule: At any moment, the length of the longest loaf which he possesses may not be larger than the length of shortest one, times some constant factor. Every time, he is only allowed to cut exactly one loaf into two shorter ones.

-----Input-----
One floating-point number, 1 ≤ k ≤ 1.999, meaning the stated constant factor. The number will have at most 3 digits after the decimal point.

-----Output-----

First, you should output one number n, the maximal achievable number of loaves for the given value of the constant factor. Then, you should output any proof that this number of loaves is in fact achievable: n-1 descriptions of cutting, using the following notation. At each step, you print two numbers: first, the index of the loaf that you want to cut into two parts; second, the length of the newly created loaf (cut off from the original one). It is assumed that the starting loaf has index 0. Each newly created loaf will be given the lowest possible free integer index (so, at the ith step this will be i). Each time, the size of size of the original loaf will be decreased by the size of the newly created loaf.

-----Example-----
Input:
1.5
Output:
4
0 0.4
0 0.3
1 0.2

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

There are $ V $ islands, numbered $ 0, 1, ..., V-1 $, respectively. There are $ E $ bridges, numbered $ 0, 1, ..., E-1 $, respectively. The $ i $ th bridge spans island $ s_i $ and island $ t_i $ and is $ c_i $ wide.

The AOR Ika-chan Corps (commonly known as the Squid Corps), which has a base on the island $ 0 $, is small in scale, so it is always being killed by the Sosu-Usa Corps (commonly known as the Sosuusa Corps) on the island $ V-1 $. .. One day, the squid group got the information that "the Sosusa group will attack tomorrow." A large number of Sosusa's subordinates move across the island from the Sosusa's base, and if even one of their subordinates reaches the Squid's base, the Squid will perish ...

Therefore, the squid group tried to avoid the crisis by putting a road closure tape on the bridge to prevent it from passing through. The length of the tape used is the sum of the widths of the closed bridges. Also, if all the subordinates of the Sosusa group always pass through a bridge with a width of $ 1 $, the squid group can ambush there to prevent them from passing through the Sosusa group.

The length of the tape it holds is $ 10 ^ 4 $. Considering the future, I would like to consume as little tape as possible. Find the minimum length of tape used to keep Sosusa's subordinates from reaching the squid's base. However, if the tape is not long enough and you are attacked by all means, output $ -1 $.



output

Output the minimum length of tape used to prevent Sosusa's subordinates from reaching the Squid's base. However, if the tape is not long enough and you are attacked by all means, output $ -1 $. Also, output a line break at the end.

Example

Input

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


Output

4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lets define G(x, {A_{1}, A_{2}, A_{3}, ..., A_{x}}) as a game played by 2 players in which we have x piles of stones with ith pile having A_{i} stones. Player 1 moves first. The players move alternatively. In a move a player can select a single non empty pile of stones and remove any number ( > 0 ) of stones from it. When a player cannot make a move, the player loses.

Adarsh and Saharsh are playing a modification of this game. There are N piles of stones lined up and ith pile has A_{i} number of stones. Saharsh needs to divide the N piles into disjoint contiguous segments. It is possible for a pile to not belong in a segment at all. The segments need to be selected in such a way such that, if ith pile is in a segment, then all the j's such that A_{i} = A_{j}, are also in the segment. Now they play games on these segments considering only the 'distinct sized piles' in the segment with Adarsh as Player 1 and Saharsh as Player 2.

Consider A = {1, 1, 2, 3, 3, 2}.

A possible division is {1, 1} and {2, 3, 3, 2}. 

For the segment {1, 1}, game G(1, {1}) would be played. For the segment {2, 3, 3, 2}, game G(2, {2, 3}) would be played.
      
G(1, {1}) would be won by Player 1
G(2, {2, 3}) would be won by Player 1
      
So number of games that Player 2 wins would be 0.

Another possible division is {1, 1, 2, 3, 3, 2}. 

For the segment {1, 1, 2, 3, 3, 2}, game G(3, {1, 2, 3}) would be played. 
G(3, {1, 2, 3}) would be won by Player 2
So number of games that Player 2 wins would be 1.

What is the maximum possible games that Saharsh can win?

------ Input Format: ------ 
 
The first line contains an integer N, the number of piles.

Next line contains N space separated integers where ith integer denotes number of stones in the ith pile, A_{i}.

------ Output Format: ------ 

For each test case, output the corresponding answer.

------ Constraints: ------ 

$1≤ N ≤500000$
$1≤ A_{i} ≤500000$

------ Sample Input: ------ 

6

1 1 2 3 3 2

------ Sample Output: ------ 

1

------ Explanation: ------ 

Given in the problem statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ganesh lives in Gopalmath. He is looking for Jojo. So he decides to collect Aadhar Card Information of all the citizens of India from UIDAI.
Someone told Ganesh that the sum of all the digits of Jojo’s Aadhar number is divisible by 10 and it is greater than zero. After finding all Aadhar numbers which are divisible by 10, Jojo’s Aadhar number is $N$th smallest Aadhar number. Hence, Ganesh wants to find Jojo’s  Aadhar number which satisfies all of the above conditions. (In this chaotic world, Aadhar numbers can be any natural number.)
However, Guruji refused Ganesh to carry out this task, because he is weak in Maths. Therefore, Ganesh assigns this task to Paritoshbhai who possesses excellent Mathematical skills. Since Paritoshbhai is busy in his jewellery business, help him in this task.

-----Input:-----
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains a single integer N.

-----Output:-----
For each test case, print a single line containing Aadhar number of Jojo.

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq N \leq 10^{100,000}$

-----Sample Input:-----
1
3

-----Sample Output:-----
37

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ football teams in the world. 

The Main Football Organization (MFO) wants to host at most $m$ games. MFO wants the $i$-th game to be played between the teams $a_i$ and $b_i$ in one of the $k$ stadiums. 

Let $s_{ij}$ be the numbers of games the $i$-th team played in the $j$-th stadium. MFO does not want a team to have much more games in one stadium than in the others. Therefore, for each team $i$, the absolute difference between the maximum and minimum among $s_{i1}, s_{i2}, \ldots, s_{ik}$ should not exceed $2$.

Each team has $w_i$ — the amount of money MFO will earn for each game of the $i$-th team. If the $i$-th team plays $l$ games, MFO will earn $w_i \cdot l$.

MFO needs to find what games in what stadiums they need to host in order to earn as much money as possible, not violating the rule they set.

However, this problem is too complicated for MFO. Therefore, they are asking you to help them.


-----Input-----

The first line contains three integers $n$, $m$, $k$ ($3 \leq n \leq 100$, $0 \leq m \leq 1\,000$, $1 \leq k \leq 1\,000$) — the number of teams, the number of games, and the number of stadiums.

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($1 \leq w_i \leq 1\,000$) — the amount of money MFO will earn for each game of the $i$-th game.

Each of the following $m$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) — the teams that can play the $i$-th game. It is guaranteed that each pair of teams can play at most one game.


-----Output-----

For each game in the same order, print $t_i$ ($1 \leq t_i \leq k$) — the number of the stadium, in which $a_i$ and $b_i$ will play the game. If the $i$-th game should not be played, $t_i$ should be equal to $0$.

If there are multiple answers, print any.


-----Example-----
Input
7 11 3
4 7 8 10 10 9 3
6 2
6 1
7 6
4 3
4 6
3 1
5 3
7 5
7 3
4 2
1 4

Output
3
2
1
1
3
1
2
1
2
3
2



-----Note-----

One of possible solutions to the example is shown below: [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: st-Spanning Tree

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an undirected connected graph consisting of *n* vertices and *m* edges. There are no loops and no multiple edges in the graph.

You are also given two distinct vertices *s* and *t*, and two values *d**s* and *d**t*. Your task is to build any spanning tree of the given graph (note that the graph is not weighted), such that the degree of the vertex *s* doesn't exceed *d**s*, and the degree of the vertex *t* doesn't exceed *d**t*, or determine, that there is no such spanning tree.

The spanning tree of the graph *G* is a subgraph which is a tree and contains all vertices of the graph *G*. In other words, it is a connected graph which contains *n*<=-<=1 edges and can be obtained by removing some of the edges from *G*.

The degree of a vertex is the number of edges incident to this vertex.

Input Specification:
The first line of the input contains two integers *n* and *m* (2<=≤<=*n*<=≤<=200<=000, 1<=≤<=*m*<=≤<=*min*(400<=000,<=*n*·(*n*<=-<=1)<=/<=2)) — the number of vertices and the number of edges in the graph. 

The next *m* lines contain the descriptions of the graph's edges. Each of the lines contains two integers *u* and *v* (1<=≤<=*u*,<=*v*<=≤<=*n*, *u*<=≠<=*v*) — the ends of the corresponding edge. It is guaranteed that the graph contains no loops and no multiple edges and that it is connected.

The last line contains four integers *s*, *t*, *d**s*, *d**t* (1<=≤<=*s*,<=*t*<=≤<=*n*, *s*<=≠<=*t*, 1<=≤<=*d**s*,<=*d**t*<=≤<=*n*<=-<=1).

Output Specification:
If the answer doesn't exist print "No" (without quotes) in the only line of the output. 

Otherwise, in the first line print "Yes" (without quotes). In the each of the next (*n*<=-<=1) lines print two integers — the description of the edges of the spanning tree. Each of the edges of the spanning tree must be printed exactly once.

You can output edges in any order. You can output the ends of each edge in any order.

If there are several solutions, print any of them.

Demo Input:
['3 3\n1 2\n2 3\n3 1\n1 2 1 1\n', '7 8\n7 4\n1 3\n5 4\n5 7\n3 2\n2 4\n6 1\n1 2\n6 4 1 4\n']

Demo Output:
['Yes\n3 2\n1 3\n', 'Yes\n1 3\n5 7\n3 2\n7 4\n2 4\n6 1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Madoka decided to entrust the organization of a major computer game tournament "OSU"!

In this tournament, matches are held according to the "Olympic system". In other words, there are $2^n$ participants in the tournament, numbered with integers from $1$ to $2^n$. There are $n$ rounds in total in the tournament. In the $i$-th round there are $2^{n - i}$ matches between two players (one of whom is right, the other is left), after which the winners go further along the tournament grid, and the losing participants are eliminated from the tournament. Herewith, the relative order in the next round does not change. And the winner of the tournament — is the last remaining participant.

But the smaller the participant's number, the more he will pay Madoka if he wins, so Madoka wants the participant with the lowest number to win. To do this, she can arrange the participants in the first round as she likes, and also determine for each match who will win — the participant on the left or right.

But Madoka knows that tournament sponsors can change the winner in matches no more than $k$ times. (That is, if the participant on the left won before the change, then the participant on the right will win after the change, and if the participant on the right won, then the participant on the left will win after the change).

So, the first image shows the tournament grid that Madoka made, where the red lines denote who should win the match. And the second one shows the tournament grid, after one change in the outcome of the match by sponsors (a match between $1$ and $3$ players).

Print the minimum possible number of the winner in the tournament, which Madoka can get regardless of changes in sponsors. But since the answer can be very large, output it modulo $10^9 + 7$. Note that we need to minimize the answer, and only then take it modulo.


-----Input-----

The first and the only line contains two integers $n$ and $k$ ($1 \le n \le 10^5, 1 \le k \le \min(2^n - 1, 10^9)$) — the number of rounds in the tournament and the number of outcomes that sponsors can change.


-----Output-----

Print exactly one integer — the minimum number of the winner modulo $10^9 + 7$


-----Examples-----

Input
1 1
Output
2
Input
2 1
Output
3
Input
3 2
Output
7


-----Note-----

In the first example, there is only one match between players $1$ and $2$, so the sponsors can always make player $2$ wins.

The tournament grid from the second example is shown in the picture in the statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monocarp has arranged $n$ colored marbles in a row. The color of the $i$-th marble is $a_i$. Monocarp likes ordered things, so he wants to rearrange marbles in such a way that all marbles of the same color form a contiguos segment (and there is only one such segment for each color). 

In other words, Monocarp wants to rearrange marbles so that, for every color $j$, if the leftmost marble of color $j$ is $l$-th in the row, and the rightmost marble of this color has position $r$ in the row, then every marble from $l$ to $r$ has color $j$.

To achieve his goal, Monocarp can do the following operation any number of times: choose two neighbouring marbles, and swap them.

You have to calculate the minimum number of operations Monocarp has to perform to rearrange the marbles. Note that the order of segments of marbles having equal color does not matter, it is only required that, for every color, all the marbles of this color form exactly one contiguous segment.


-----Input-----

The first line contains one integer $n$ $(2 \le n \le 4 \cdot 10^5)$ — the number of marbles.

The second line contains an integer sequence $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 20)$, where $a_i$ is the color of the $i$-th marble.


-----Output-----

Print the minimum number of operations Monocarp has to perform to achieve his goal.


-----Examples-----
Input
7
3 4 2 3 4 2 2

Output
3

Input
5
20 1 14 10 2

Output
0

Input
13
5 5 4 4 3 5 7 6 5 4 4 6 5

Output
21



-----Note-----

In the first example three operations are enough. Firstly, Monocarp should swap the third and the fourth marbles, so the sequence of colors is $[3, 4, 3, 2, 4, 2, 2]$. Then Monocarp should swap the second and the third marbles, so the sequence is $[3, 3, 4, 2, 4, 2, 2]$. And finally, Monocarp should swap the fourth and the fifth marbles, so the sequence is $[3, 3, 4, 4, 2, 2, 2]$. 

In the second example there's no need to perform any operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers nums.
A pair (i,j) is called good if nums[i] == nums[j] and i < j.
Return the number of good pairs.
 
Example 1:
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:
Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.

Example 3:
Input: nums = [1,2,3]
Output: 0

 
Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given n words w[1..n], which originate from the same stem (e.g. grace, graceful, disgraceful, gracefully), we are interested in the original stem. To simplify the problem, we define the stem as the longest consecutive substring that occurs in all the n words. If there are ties, we will choose the smallest one in the alphabetical (lexicographic) order.

-----Input-----
The first line contains an integer T denoting the total number of test cases.
In each test cases, the first line contains an integer n denoting the number of words. In the second line, n words w[1..n] consisting of lower case characters are given as a single space-spearated list.

-----Output-----
For each test case, output the stem in a new line.

-----Constraints-----
- 1 <= T <= 10
- 1 <= n <= 10
- 1 <= |w[i]| <= 20

-----Example-----
Input:
1
4
grace graceful disgraceful gracefully
Output:
grace

-----Explanation-----
The stem is grace.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose you have two polynomials $A(x) = \sum_{k = 0}^{n} a_{k} x^{k}$ and $B(x) = \sum_{k = 0}^{m} b_{k} x^{k}$. Then polynomial $A(x)$ can be uniquely represented in the following way:$A(x) = B(x) \cdot D(x) + R(x), \operatorname{deg} R(x) < \operatorname{deg} B(x)$

This can be done using long division. Here, $\operatorname{deg} P(x)$ denotes the degree of polynomial P(x). $R(x)$ is called the remainder of division of polynomial $A(x)$ by polynomial $B(x)$, it is also denoted as $A \operatorname{mod} B$. 

Since there is a way to divide polynomials with remainder, we can define Euclid's algorithm of finding the greatest common divisor of two polynomials. The algorithm takes two polynomials $(A, B)$. If the polynomial $B(x)$ is zero, the result is $A(x)$, otherwise the result is the value the algorithm returns for pair $(B, A \operatorname{mod} B)$. On each step the degree of the second argument decreases, so the algorithm works in finite number of steps. But how large that number could be? You are to answer this question. 

You are given an integer n. You have to build two polynomials with degrees not greater than n, such that their coefficients are integers not exceeding 1 by their absolute value, the leading coefficients (ones with the greatest power of x) are equal to one, and the described Euclid's algorithm performs exactly n steps finding their greatest common divisor. Moreover, the degree of the first polynomial should be greater than the degree of the second. By a step of the algorithm we mean the transition from pair $(A, B)$ to pair $(B, A \operatorname{mod} B)$. 


-----Input-----

You are given a single integer n (1 ≤ n ≤ 150) — the number of steps of the algorithm you need to reach.


-----Output-----

Print two polynomials in the following format.

In the first line print a single integer m (0 ≤ m ≤ n) — the degree of the polynomial. 

In the second line print m + 1 integers between  - 1 and 1 — the coefficients of the polynomial, from constant to leading. 

The degree of the first polynomial should be greater than the degree of the second polynomial, the leading coefficients should be equal to 1. Euclid's algorithm should perform exactly n steps when called using these polynomials.

If there is no answer for the given n, print -1.

If there are multiple answer, print any of them.


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

Output
1
0 1
0
1

Input
2

Output
2
-1 0 1
1
0 1



-----Note-----

In the second example you can print polynomials x^2 - 1 and x. The sequence of transitions is(x^2 - 1, x) → (x,  - 1) → ( - 1, 0).

There are two steps in it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given the array a consisting of n elements and the integer k ≤ n.

You want to obtain at least k equal elements in the array a. In one move, you can make one of the following two operations:

  * Take one of the minimum elements of the array and increase its value by one (more formally, if the minimum value of a is mn then you choose such index i that a_i = mn and set a_i := a_i + 1); 
  * take one of the maximum elements of the array and decrease its value by one (more formally, if the maximum value of a is mx then you choose such index i that a_i = mx and set a_i := a_i - 1). 



Your task is to calculate the minimum number of moves required to obtain at least k equal elements in the array.

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 2 ⋅ 10^5) — the number of elements in a and the required number of equal elements.

The second line of the input contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9), where a_i is the i-th element of a.

Output

Print one integer — the minimum number of moves required to obtain at least k equal elements in the array.

Examples

Input


6 5
1 2 2 4 2 3


Output


3


Input


7 5
3 3 2 1 1 1 3


Output


4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are the head of a large enterprise. $n$ people work at you, and $n$ is odd (i. e. $n$ is not divisible by $2$).

You have to distribute salaries to your employees. Initially, you have $s$ dollars for it, and the $i$-th employee should get a salary from $l_i$ to $r_i$ dollars. You have to distribute salaries in such a way that the median salary is maximum possible.

To find the median of a sequence of odd length, you have to sort it and take the element in the middle position after sorting. For example:  the median of the sequence $[5, 1, 10, 17, 6]$ is $6$,  the median of the sequence $[1, 2, 1]$ is $1$. 

It is guaranteed that you have enough money to pay the minimum salary, i.e $l_1 + l_2 + \dots + l_n \le s$.

Note that you don't have to spend all your $s$ dollars on salaries.

You have to answer $t$ test cases.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 2 \cdot 10^5$) — the number of test cases.

The first line of each query contains two integers $n$ and $s$ ($1 \le n < 2 \cdot 10^5$, $1 \le s \le 2 \cdot 10^{14}$) — the number of employees and the amount of money you have. The value $n$ is not divisible by $2$.

The following $n$ lines of each query contain the information about employees. The $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le 10^9$).

It is guaranteed that the sum of all $n$ over all queries does not exceed $2 \cdot 10^5$.

It is also guaranteed that you have enough money to pay the minimum salary to each employee, i. e. $\sum\limits_{i=1}^{n} l_i \le s$.


-----Output-----

For each test case print one integer — the maximum median salary that you can obtain.


-----Example-----
Input
3
3 26
10 12
1 4
10 11
1 1337
1 1000000000
5 26
4 4
2 4
6 8
5 6
2 7

Output
11
1337
6



-----Note-----

In the first test case, you can distribute salaries as follows: $sal_1 = 12, sal_2 = 2, sal_3 = 11$ ($sal_i$ is the salary of the $i$-th employee). Then the median salary is $11$.

In the second test case, you have to pay $1337$ dollars to the only employee.

In the third test case, you can distribute salaries as follows: $sal_1 = 4, sal_2 = 3, sal_3 = 6, sal_4 = 6, sal_5 = 7$. Then the median salary is $6$.

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