vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
We define the "unfairness" of a list/array as the *minimal* difference between max(x1,x2,...xk) and min(x1,x2,...xk), for all possible combinations of k elements you can take from the list/array; both minimum and maximum of an empty list/array are considered to be 0.

**More info and constraints:**

* lists/arrays can contain values repeated more than once, plus there are usually more combinations that generate the required minimum;
* the list/array's length can be any value from 0 to 10^(6);
* the value of k will range from 0 to the length of the list/array,
* the minimum unfairness of an array/list with less than 2 elements is 0.

For example:

```python
min_unfairness([30,100,1000,150,60,250,10,120,20],3)==20 #from max(30,10,20)-min(30,10,20)==20, minimum unfairness in this sample
min_unfairness([30,100,1000,150,60,250,10,120,20],5)==90 #from max(30,100,60,10,20)-min(30,100,60,10,20)==90, minimum unfairness in this sample
min_unfairness([1,1,1,1,1,1,1,1,1,2,2,2,2,2,2],10)==1 #from max(1,1,1,1,1,1,1,1,1,2)-min(1,1,1,1,1,1,1,1,1,2)==1, minimum unfairness in this sample
min_unfairness([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],10)==0 #from max(1,1,1,1,1,1,1,1,1,1)-min(1,1,1,1,1,1,1,1,1,1)==0, minimum unfairness in this sample
min_unfairness([1,1,-1],2)==0 #from max(1,1)-min(1,1)==0, minimum unfairness in this sample
```

**Note:** shamelessly taken from [here](https://www.hackerrank.com/challenges/angry-children), where it was created and debatably categorized and ranked.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hmm, how long has it been since the last color revolution? 5 years?! It's totally the time to make a new one!

So the general idea is the following. Division 1 should have n_1 participants. Division 2 should have n_2 and be exactly k times bigger than division 1 (n_2 = k ⋅ n_1). Division 3 should have n_3 = k ⋅ n_2 participants. Finally, division 4 should have n_4 = k ⋅ n_3 participants.

There are n participants on Codeforces in total. So n_1 + n_2 + n_3 + n_4 should be exactly equal to n.

You know the values of n and k. You also know that n and k are chosen in such a way that there exist values n_1, n_2, n_3 and n_4 such that all the conditions are satisfied.

What will be the number of participants in each division (n_1, n_2, n_3 and n_4) after the revolution?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

Each of the next t lines contains two integers n and k (4 ≤ n ≤ 10^9; 1 ≤ k ≤ 500) — the total number of participants on Codeforces and the size multiplier for the corresponding testcase. In each testcase, n and k are chosen in such a way that the answer exists.

Output

For each testcase print four integers n_1, n_2, n_3 and n_4 such that n_2 = k ⋅ n_1, n_3 = k ⋅ n_2, n_4 = k ⋅ n_3 and n_1 + n_2 + n_3 + n_4 = n.

Example

Input


4
40 3
1200 7
320802005 400
4 1


Output


1 3 9 27
3 21 147 1029
5 2000 800000 320000000
1 1 1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan recently bought a detective book. The book is so interesting that each page of this book introduces some sort of a mystery, which will be explained later. The $i$-th page contains some mystery that will be explained on page $a_i$ ($a_i \ge i$).

Ivan wants to read the whole book. Each day, he reads the first page he didn't read earlier, and continues to read the following pages one by one, until all the mysteries he read about are explained and clear to him (Ivan stops if there does not exist any page $i$ such that Ivan already has read it, but hasn't read page $a_i$). After that, he closes the book and continues to read it on the following day from the next page.

How many days will it take to read the whole book?


-----Input-----

The first line contains single integer $n$ ($1 \le n \le 10^4$) — the number of pages in the book.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($i \le a_i \le n$), where $a_i$ is the number of page which contains the explanation of the mystery on page $i$.


-----Output-----

Print one integer — the number of days it will take to read the whole book.


-----Example-----
Input
9
1 3 3 6 7 6 8 8 9

Output
4



-----Note-----

Explanation of the example test:

During the first day Ivan will read only the first page. During the second day Ivan will read pages number $2$ and $3$. During the third day — pages $4$-$8$. During the fourth (and the last) day Ivan will read remaining page number $9$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little time is left before Berland annual football championship. Therefore the coach of team "Losewille Rangers" decided to resume the practice, that were indefinitely interrupted for uncertain reasons. Overall there are *n* players in "Losewille Rangers". Each player on the team has a number — a unique integer from 1 to *n*. To prepare for the championship, the coach Mr. Floppe decided to spend some number of practices.

Mr. Floppe spent some long nights of his holiday planning how to conduct the practices. He came to a very complex practice system. Each practice consists of one game, all *n* players of the team take part in the game. The players are sorted into two teams in some way. In this case, the teams may have different numbers of players, but each team must have at least one player.

The coach wants to be sure that after the series of the practice sessions each pair of players had at least one practice, when they played in different teams. As the players' energy is limited, the coach wants to achieve the goal in the least number of practices.

Help him to schedule the practices.

Input Specification:
A single input line contains integer *n* (2<=≤<=*n*<=≤<=1000).

Output Specification:
In the first line print *m* — the minimum number of practices the coach will have to schedule. Then print the descriptions of the practices in *m* lines.

In the *i*-th of those lines print *f**i* — the number of players in the first team during the *i*-th practice (1<=≤<=*f**i*<=&lt;<=*n*), and *f**i* numbers from 1 to *n* — the numbers of players in the first team. The rest of the players will play in the second team during this practice. Separate numbers on a line with spaces. Print the numbers of the players in any order. If there are multiple optimal solutions, print any of them.

Demo Input:
['2\n', '3\n']

Demo Output:
['1\n1 1\n', '2\n2 1 2\n1 1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A dishonest landowner is selling off plots of land. He’s selling it in large, rectangular plots, but many of the plots overlap, so he’s actually selling the same land multiple times! It’s not real estate, it’s unreal estate!

Given a description of the possibly overlapping rectangular plots of land that the dishonest landowner has sold, determine the total actual area of land covered by them.

-----Input-----
There will be a single test case in the input. Each test case will begin with a line with a single integer $n$ ($0 < n \le 5000$), indicating the number of plots of land sold. The next $n$ lines will each have a description of a rectangular plot of land, consisting of four real numbers with at most two decimals after the decimal point:

     x1 y1 x2 y2

where $(x_1,y_1)$ is the southwest corner, and $(x_2,y_2)$ is the northeast corner ($-1000 \le x_1 < x_2 \le 1000$, $-1000 \le y_1 < y_2 \le 1000$).

-----Output-----
Output a single real number, which represents the total actual area covered by all of the rectangular plots of land. Output this number with exactly two decimal places, rounded.

-----Examples-----
Sample Input:
2
0 0 100 100
30 30 60 60
Sample Output:
10000.00

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N towns in a coordinate plane. Town i is located at coordinates (x_i, y_i). The distance between Town i and Town j is \sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2}.
There are N! possible paths to visit all of these towns once. Let the length of a path be the distance covered when we start at the first town in the path, visit the second, third, \dots, towns, and arrive at the last town (assume that we travel in a straight line from a town to another). Compute the average length of these N! paths.

-----Constraints-----
 - 2 \leq N \leq 8
 - -1000 \leq x_i \leq 1000
 - -1000 \leq y_i \leq 1000
 - \left(x_i, y_i\right) \neq \left(x_j, y_j\right) (if i \neq j)
 - (Added 21:12 JST) All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
x_1 y_1
:
x_N y_N

-----Output-----
Print the average length of the paths.
Your output will be judges as correct when the absolute difference from the judge's output is at most 10^{-6}.

-----Sample Input-----
3
0 0
1 0
0 1

-----Sample Output-----
2.2761423749

There are six paths to visit the towns: 1 → 2 → 3, 1 → 3 → 2, 2 → 1 → 3, 2 → 3 → 1, 3 → 1 → 2, and 3 → 2 → 1.
The length of the path 1 → 2 → 3 is \sqrt{\left(0-1\right)^2+\left(0-0\right)^2} + \sqrt{\left(1-0\right)^2+\left(0-1\right)^2} = 1+\sqrt{2}.
By calculating the lengths of the other paths in this way, we see that the average length of all routes is:
\frac{\left(1+\sqrt{2}\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)}{6} = 2.276142...

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It’s well know fact among cats that digits 4 and 7 are lucky digits.

Today, N boxes of ice cream arrived. Each box has a unique integer label on it, ranged between 1 and N, inclusive. The boxes are going to be given away to the cats in increasing order of their labels. That is, the first box given away will be the box with label 1, and the last one will be the box with label N.

The cats are ordered in line for the ice cream. While there is any ice cream box left, it’s given away to the cat who is the first in line for it. This cat counts the total number of lucky digits among all box labels received by him. As soon as this number exceeds K, the cat becomes lucky and leaves the line, and the next cat occupies his place.

Your task is to find out the number of cats that are going to be lucky at the end of the described process.

Input format

The first line of the input contains the integer K. The second line contains the integer N, without leading zeros.

Output format

In the only line of the output print the number of lucky cats modulo 1,000,000,007.

Constraints

N is between 1 and 10^10000 and K is between 1 and 10, inclusive.

SAMPLE INPUT
3
74

SAMPLE OUTPUT
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During Quarantine Time Chef is at home and he was quite confused about what to cook so, he went to his son and asked about what would he prefer to have? He replied, cakes.
Now, chef cook $N$ number of cake and number of layers for every cake is different. After cakes are baked, Chef arranged them in a particular order and then generates a number by putting number of layers of cakes as digit in sequence (e.g., if chef arranges cakes with layers in sequence $2$, $3$ and $5$ then generated number is $235$).
Chef has to make his son powerful in mathematics, so he called his son and ask him to arrange the cakes in all the possible ways and every time when different sequence is generated he has to note down the number. At the end he has to find sum of all the generated numbers. So, help him to complete this task.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- The first line of each test case contains a single integer $N$ denoting number of cakes.
- The second line contains $N$ space-separated integers $L1$ $L2$ … $LN$ layers of the cake.

-----Output:-----
For each test case, print a single line containing sum of all the possible numbers which is generated by arranging cake in different sequence.

-----Constraints :-----
- $1 \leq T  \leq 2*10^5$
- $1 \leq N, L1, L2, L3,…, LN \leq 9$

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

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

-----Explanation:-----
Sum of all possibilities :
$235 + 532 + 253 + 352 + 523 + 325 = 2220 $

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
German mathematician Christian Goldbach (1690-1764) [conjectured](https://en.wikipedia.org/wiki/Goldbach%27s_conjecture) that every even number greater than 2 can be represented by the sum of two prime numbers. For example, `10` can be represented as `3+7` or `5+5`.

Your job is to make the function return a list containing all unique possible representations of `n` in an increasing order if `n` is an even integer; if `n` is odd, return an empty list. Hence, the first addend must always be less than or equal to the second to avoid duplicates.

Constraints : `2 < n < 32000` and `n` is even


## Examples
```
26  -->  ['3+23', '7+19', '13+13']

100 -->  ['3+97', '11+89', '17+83', '29+71', '41+59', '47+53']

7   -->  [] 
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once Vasya and Petya assembled a figure of m cubes, each of them is associated with a number between 0 and m - 1 (inclusive, each number appeared exactly once). Let's consider a coordinate system such that the OX is the ground, and the OY is directed upwards. Each cube is associated with the coordinates of its lower left corner, these coordinates are integers for each cube.

The figure turned out to be stable. This means that for any cube that is not on the ground, there is at least one cube under it such that those two cubes touch by a side or a corner. More formally, this means that for the cube with coordinates (x, y) either y = 0, or there is a cube with coordinates (x - 1, y - 1), (x, y - 1) or (x + 1, y - 1).

Now the boys want to disassemble the figure and put all the cubes in a row. In one step the cube is removed from the figure and being put to the right of the blocks that have already been laid. The guys remove the cubes in such order that the figure remains stable. To make the process more interesting, the guys decided to play the following game. The guys take out the cubes from the figure in turns. It is easy to see that after the figure is disassembled, the integers written on the cubes form a number, written in the m-ary positional numerical system (possibly, with a leading zero). Vasya wants the resulting number to be maximum possible, and Petya, on the contrary, tries to make it as small as possible. Vasya starts the game.

Your task is to determine what number is formed after the figure is disassembled, if the boys play optimally. Determine the remainder of the answer modulo 10^9 + 9.


-----Input-----

The first line contains number m (2 ≤ m ≤ 10^5).

The following m lines contain the coordinates of the cubes x_{i}, y_{i} ( - 10^9 ≤ x_{i} ≤ 10^9, 0 ≤ y_{i} ≤ 10^9) in ascending order of numbers written on them. It is guaranteed that the original figure is stable.

No two cubes occupy the same place.


-----Output-----

In the only line print the answer to the problem.


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

Output
19

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

Output
2930

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are K lemurs on Madagascar and Kevin has N bananas. He has to give away all his bananas to lemurs. Lemurs are happy if all of them get the same number of bananas (even if they don't get any). In one minute Kevin can do one of the following:
 Find one banana. 
 Discard one banana (eat). 
 Increase a population of lemurs on Madagascar by one. 
 If there are at least two lemurs remove one of them from Madagascar (don't ask how). 

Help Kevin and find the minimum number of minutes Kevin needs to satisfy all the lemurs.

Input format:

The only line of the input contains two space-separated integers N and K.

Output format:

Output the single integer -- the minimum number of minutes.

Constraints:
1 ≤ K,N ≤ 10^5
K, N ≤ 50 in test data worth 33% of all points

SAMPLE INPUT
47 17

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gautam Buddha University V.C. has planned a tour for GBU students. For the tour, V.C. decided to book cars. The students are ready to go on one condtition:
If two students are friends then they do not want to go in different cars.  

Due to this condition, V.C. cannot decide that how many cars will be needed for the tour. And for each car he also needs one leader in the car.  

As you are a programmer, so V.C. is giving you this task. Find the maximum number of cars he will need for the tour and the total number of ways of selecting leader in each car.

Input:
First line contains n, which denotes the number of students that will go for the tour.  
Second line contains m, which denotes the number of friendship relation between students.  
Next m lines will have two space separated integers a,b.  
Consider mutual friendship(a is a friend of b and vice versa).  

Output:
Output a single line containing two space separated integers - maximum number of cars he will be needed and the number of ways of selecting the leaders. Leaders will be modulo (10^6)+7.  

Note: Assume Capacity of a Car is unlimited.  

Constraints:
1 ≤ n ≤ 10^5
1 ≤ m ≤ 10^5
1 ≤ a,b ≤ 10^5

SAMPLE INPUT
6
3
1 2
3 4
5 6

SAMPLE OUTPUT
3 8

Explanation

In this sample we need three cars in which students are (1,2) ,(3,4),(5,6) and total number ways of selecting leaders in cars will be 8.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A remote island chain contains *n* islands, labeled 1 through *n*. Bidirectional bridges connect the islands to form a simple cycle — a bridge connects islands 1 and 2, islands 2 and 3, and so on, and additionally a bridge connects islands *n* and 1. The center of each island contains an identical pedestal, and all but one of the islands has a fragile, uniquely colored statue currently held on the pedestal. The remaining island holds only an empty pedestal.

The islanders want to rearrange the statues in a new order. To do this, they repeat the following process: First, they choose an island directly adjacent to the island containing an empty pedestal. Then, they painstakingly carry the statue on this island across the adjoining bridge and place it on the empty pedestal.

Determine if it is possible for the islanders to arrange the statues in the desired order.

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

The second line contains *n* space-separated integers *a**i* (0<=≤<=*a**i*<=≤<=*n*<=-<=1) — the statue currently placed on the *i*-th island. If *a**i*<==<=0, then the island has no statue. It is guaranteed that the *a**i* are distinct.

The third line contains *n* space-separated integers *b**i* (0<=≤<=*b**i*<=≤<=*n*<=-<=1) — the desired statues of the *i*th island. Once again, *b**i*<==<=0 indicates the island desires no statue. It is guaranteed that the *b**i* are distinct.

Output Specification:
Print "YES" (without quotes) if the rearrangement can be done in the existing network, and "NO" otherwise.

Demo Input:
['3\n1 0 2\n2 0 1\n', '2\n1 0\n0 1\n', '4\n1 2 3 0\n0 3 2 1\n']

Demo Output:
['YES\n', 'YES\n', 'NO\n']

Note:
In the first sample, the islanders can first move statue 1 from island 1 to island 2, then move statue 2 from island 3 to island 1, and finally move statue 1 from island 2 to island 3.

In the second sample, the islanders can simply move statue 1 from island 1 to island 2.

In the third sample, no sequence of movements results in the desired position.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Carol is currently curling.

She has *n* disks each with radius *r* on the 2D plane. 

Initially she has all these disks above the line *y*<==<=10100.

She then will slide the disks towards the line *y*<==<=0 one by one in order from 1 to *n*. 

When she slides the *i*-th disk, she will place its center at the point (*x**i*,<=10100). She will then push it so the disk’s *y* coordinate continuously decreases, and *x* coordinate stays constant. The disk stops once it touches the line *y*<==<=0 or it touches any previous disk. Note that once a disk stops moving, it will not move again, even if hit by another disk. 

Compute the *y*-coordinates of centers of all the disks after all disks have been pushed.

Input Specification:
The first line will contain two integers *n* and *r* (1<=≤<=*n*,<=*r*<=≤<=1<=000), the number of disks, and the radius of the disks, respectively.

The next line will contain *n* integers *x*1,<=*x*2,<=...,<=*x**n* (1<=≤<=*x**i*<=≤<=1<=000) — the *x*-coordinates of the disks.

Output Specification:
Print a single line with *n* numbers. The *i*-th number denotes the *y*-coordinate of the center of the *i*-th disk. The output will be accepted if it has absolute or relative error at most 10<=-<=6.

Namely, let's assume that your answer for a particular value of a coordinate is *a* and the answer of the jury is *b*. The checker program will consider your answer correct if  for all coordinates.

Demo Input:
['6 2\n5 5 6 8 3 12\n']

Demo Output:
['2 6.0 9.87298334621 13.3370849613 12.5187346573 13.3370849613\n']

Note:
The final positions of the disks will look as follows:

In particular, note the position of the last disk.

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