vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The problems is to find the count of numbers between A and B (inclusive) that have sum of digits equal to S.

Also print the smallest such number between A and B (inclusive).

Input:

Single line consisting of A,B,S.

Output:

Two lines.

In first line the number of integers between A and B having sum of digits equal to S.

In second line the smallest such number between A and B.

Constraints:

1 ≤ A ≤ B < 10^15

1 ≤ S ≤ 135

SAMPLE INPUT
5 17 5

SAMPLE OUTPUT
2
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the diameter of a convex polygon g. In other words, find a pair of points that have maximum distance between them.

Constraints

* 3 ≤ n ≤ 80000
* -100 ≤ xi, yi ≤ 100
* No point in the g will occur more than once.

Input


n
x1 y1
x2 y2
:
xn yn


The first integer n is the number of points in g.

In the following lines, the coordinate of the i-th point pi is given by two real numbers xi and yi. The coordinates of points are given in the order of counter-clockwise visit of them. Each value is a real number with at most 6 digits after the decimal point.

Output

Print the diameter of g in a line. The output values should be in a decimal fraction with an error less than 0.000001.

Examples

Input

3
0.0 0.0
4.0 0.0
2.0 2.0


Output

4.00


Input

4
0.0 0.0
1.0 0.0
1.0 1.0
0.0 1.0


Output

1.414213562373

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: HDD is Outdated Technology

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
HDD hard drives group data by sectors. All files are split to fragments and each of them are written in some sector of hard drive. Note the fragments can be written in sectors in arbitrary order.

One of the problems of HDD hard drives is the following: the magnetic head should move from one sector to another to read some file.

Find the time need to read file split to *n* fragments. The *i*-th sector contains the *f**i*-th fragment of the file (1<=≤<=*f**i*<=≤<=*n*). Note different sectors contains the different fragments. At the start the magnetic head is in the position that contains the first fragment. The file are reading in the following manner: at first the first fragment is read, then the magnetic head moves to the sector that contains the second fragment, then the second fragment is read and so on until the *n*-th fragment is read. The fragments are read in the order from the first to the *n*-th.

It takes |*a*<=-<=*b*| time units to move the magnetic head from the sector *a* to the sector *b*. Reading a fragment takes no time.

Input Specification:
The first line contains a positive integer *n* (1<=≤<=*n*<=≤<=2·105) — the number of fragments.

The second line contains *n* different integers *f**i* (1<=≤<=*f**i*<=≤<=*n*) — the number of the fragment written in the *i*-th sector.

Output Specification:
Print the only integer — the number of time units needed to read the file.

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

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

Note:
In the second example the head moves in the following way:
 -  1-&gt;2 means movement from the sector 1 to the sector 5, i.e. it takes 4 time units -  2-&gt;3 means movement from the sector 5 to the sector 2, i.e. it takes 3 time units -  3-&gt;4 means movement from the sector 2 to the sector 4, i.e. it takes 2 time units -  4-&gt;5 means movement from the sector 4 to the sector 3, i.e. it takes 1 time units 
So the answer to the second example is 4 + 3 + 2 + 1 = 10.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
This is an interactive problem. You should use flush operation after each printed line. For example, in C++ you should use fflush(stdout), in Java you should use System.out.flush(), and in Pascal — flush(output).

In this problem you should guess an array *a* which is unknown for you. The only information you have initially is the length *n* of the array *a*.

The only allowed action is to ask the sum of two elements by their indices. Formally, you can print two indices *i* and *j* (the indices should be distinct). Then your program should read the response: the single integer equals to *a**i*<=+<=*a**j*.

It is easy to prove that it is always possible to guess the array using at most *n* requests.

Write a program that will guess the array *a* by making at most *n* requests.

Input Specification:
none

Output Specification:
none

Demo Input:
['5\n\xa0\n9\n\xa0\n7\n\xa0\n9\n\xa0\n11\n\xa0\n6\n\xa0']

Demo Output:
['? 1 5\n\xa0\n? 2 3\n\xa0\n? 4 1\n\xa0\n? 5 2\n\xa0\n? 3 4\n\xa0\n! 4 6 1 5 5']

Note:
The format of a test to make a hack is:
 -  The first line contains an integer number *n* (3 ≤ *n* ≤ 5000) — the length of the array.-  The second line contains *n* numbers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>) — the elements of the array to guess.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Iceland is famous for its geothermal activity, which supplies the country with much of its electricity and heating. It is also a source of pleasure, in the form of hot springs. 

Kalle is visiting one of Iceland’s famous hot springs. It contains $n$ pools of water, where the $i$th one has temperature $t_ i$. Although staying in one of the warmer pools for a long time sure is relaxing, Kalle is on a very tight schedule and just wants a quick dip in each of the pools. As you may know, the nicest thing about hot baths is the contrast between hot and cold. Therefore, to get the most out of his stay, Kalle wants to find an ordering of the pools so that the difference in temperature between subsequent pools is increasing.

Given a sequence of pool temperatures $t_1, t_2, \dots , t_ n$, rearrange them into a new sequence $t’_1, t’_2, \dots , t’_ n$ such that for all $2 \leq i \leq n-1$ it holds that\[ |t’_{i-1} - t’_ i| \leq |t’_ i - t’_{i+1}|. \]

-----Input-----
The input consists of:
 - One line with an integer $n$ ($2 \le n \leq 10^5$), the number of pools.
 - One line with $n$ integers $t_1, \ldots , t_ n$ ($-10^5\leq t_ i \leq 10^5$ for each $i$), the temperatures in each of the $n$ pools.

-----Output-----
Output a rearrangement of the sequence satisfying the given requirement. If no solution exists, output “impossible”. If there are multiple valid solutions, you may output any one of them.

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

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Programmers' kids solve this riddle in 5-10 minutes. How fast can you do it?

Input Specification:
The input contains a single integer *n* (0<=≤<=*n*<=≤<=2000000000).

Output Specification:
Output a single integer.

Demo Input:
['11\n', '14\n', '61441\n', '571576\n', '2128506\n']

Demo Output:
['2\n', '0\n', '2\n', '10\n', '3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fox Ciel is playing a card game with her friend Fox Jiro. There are n piles of cards on the table. And there is a positive integer on each card.

The players take turns and Ciel takes the first turn. In Ciel's turn she takes a card from the top of any non-empty pile, and in Jiro's turn he takes a card from the bottom of any non-empty pile. Each player wants to maximize the total sum of the cards he took. The game ends when all piles become empty.

Suppose Ciel and Jiro play optimally, what is the score of the game?


-----Input-----

The first line contain an integer n (1 ≤ n ≤ 100). Each of the next n lines contains a description of the pile: the first integer in the line is s_{i} (1 ≤ s_{i} ≤ 100) — the number of cards in the i-th pile; then follow s_{i} positive integers c_1, c_2, ..., c_{k}, ..., c_{s}_{i} (1 ≤ c_{k} ≤ 1000) — the sequence of the numbers on the cards listed from top of the current pile to bottom of the pile.


-----Output-----

Print two integers: the sum of Ciel's cards and the sum of Jiro's cards if they play optimally.


-----Examples-----
Input
2
1 100
2 1 10

Output
101 10

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

Output
30 15

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

Output
18 18

Input
3
3 1000 1000 1000
6 1000 1000 1000 1000 1000 1000
5 1000 1000 1000 1000 1000

Output
7000 7000



-----Note-----

In the first example, Ciel will take the cards with number 100 and 1, Jiro will take the card with number 10.

In the second example, Ciel will take cards with numbers 2, 8, 6, 5, 9 and Jiro will take cards with numbers 4, 7, 1, 3.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Petya loves volleyball very much. One day he was running late for a volleyball match. Petya hasn't bought his own car yet, that's why he had to take a taxi. The city has *n* junctions, some of which are connected by two-way roads. The length of each road is defined by some positive integer number of meters; the roads can have different lengths.

Initially each junction has exactly one taxi standing there. The taxi driver from the *i*-th junction agrees to drive Petya (perhaps through several intermediate junctions) to some other junction if the travel distance is not more than *t**i* meters. Also, the cost of the ride doesn't depend on the distance and is equal to *c**i* bourles. Taxis can't stop in the middle of a road. Each taxi can be used no more than once. Petya can catch taxi only in the junction, where it stands initially.

At the moment Petya is located on the junction *x* and the volleyball stadium is on the junction *y*. Determine the minimum amount of money Petya will need to drive to the stadium.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*<=≤<=1000,<=0<=≤<=*m*<=≤<=1000). They are the number of junctions and roads in the city correspondingly. The junctions are numbered from 1 to *n*, inclusive. The next line contains two integers *x* and *y* (1<=≤<=*x*,<=*y*<=≤<=*n*). They are the numbers of the initial and final junctions correspondingly. Next *m* lines contain the roads' description. Each road is described by a group of three integers *u**i*, *v**i*, *w**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*,<=1<=≤<=*w**i*<=≤<=109) — they are the numbers of the junctions connected by the road and the length of the road, correspondingly. The next *n* lines contain *n* pairs of integers *t**i* and *c**i* (1<=≤<=*t**i*,<=*c**i*<=≤<=109), which describe the taxi driver that waits at the *i*-th junction — the maximum distance he can drive and the drive's cost. The road can't connect the junction with itself, but between a pair of junctions there can be more than one road. All consecutive numbers in each line are separated by exactly one space character.

Output Specification:
If taxis can't drive Petya to the destination point, print "-1" (without the quotes). Otherwise, print the drive's minimum cost.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

Demo Input:
['4 4\n1 3\n1 2 3\n1 4 1\n2 4 1\n2 3 5\n2 7\n7 2\n1 2\n7 7\n']

Demo Output:
['9\n']

Note:
An optimal way — ride from the junction 1 to 2 (via junction 4), then from 2 to 3. It costs 7+2=9 bourles.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today the kindergarten has a new group of n kids who need to be seated at the dinner table. The chairs at the table are numbered from 1 to 4n. Two kids can't sit on the same chair. It is known that two kids who sit on chairs with numbers a and b (a ≠ b) will indulge if: 

  1. gcd(a, b) = 1 or, 
  2. a divides b or b divides a. 



gcd(a, b) — the maximum number x such that a is divisible by x and b is divisible by x.

For example, if n=3 and the kids sit on chairs with numbers 2, 3, 4, then they will indulge since 4 is divided by 2 and gcd(2, 3) = 1. If kids sit on chairs with numbers 4, 6, 10, then they will not indulge.

The teacher really doesn't want the mess at the table, so she wants to seat the kids so there are no 2 of the kid that can indulge. More formally, she wants no pair of chairs a and b that the kids occupy to fulfill the condition above.

Since the teacher is very busy with the entertainment of the kids, she asked you to solve this problem.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

Each test case consists of one line containing an integer n (1 ≤ n ≤ 100) — the number of kids.

Output

Output t lines, which contain n distinct integers from 1 to 4n — the numbers of chairs that the kids should occupy in the corresponding test case. If there are multiple answers, print any of them. You can print n numbers in any order.

Example

Input


3
2
3
4


Output


6 4
4 6 10
14 10 12 8

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

My TV remote control has arrow buttons and an `OK` button.

I can use these to move a "cursor" on a logical screen keyboard to type words...

# Keyboard

The screen "keyboard" layout looks like this


  #tvkb {
    width : 400px;
    border: 5px solid gray; border-collapse: collapse;
  }
  #tvkb td {
    color : orange;
    background-color : black;
    text-align : center;
    border: 3px solid gray; border-collapse: collapse;
  }


abcde123
fghij456
klmno789
pqrst.@0
uvwxyz_/
aASP



* `aA` is the SHIFT key. Pressing this key toggles alpha characters between UPPERCASE and lowercase
* `SP` is the space character
* The other blank keys in the bottom row have no function

# Kata task

How many button presses on my remote are required to type the given `words`?

## Notes

* The cursor always starts on the letter `a` (top left)
* The alpha characters are initially lowercase (as shown above)
* Remember to also press `OK` to "accept" each letter
* Take a direct route from one letter to the next
* The cursor does not wrap (e.g. you cannot leave one edge and reappear on the opposite edge)
* Although the blank keys have no function, you may navigate through them if you want to
* Spaces may occur anywhere in the `words` string.
* Do not press the SHIFT key until you need to. For example, with the word `e.Z`, the SHIFT change happens **after** the `.` is pressed (not before)
 
# Example

words = `Code Wars`

* C => `a`-`f`-`k`-`p`-`u`-`aA`-OK-`U`-`P`-`K`-`F`-`A`-`B`-`C`-OK = 14
* o => `C`-`H`-`M`-`R`-`W`-`V`-`U`-`aA`-OK-`SP`-`v`-`q`-`l`-`m`-`n`-`o`-OK = 16
* d => `o`-`j`-`e`-`d`-OK = 4
* e => `d`-`e`-OK = 2
* space => `e`-`d`-`c`-`b`-`g`-`l`-`q`-`v`-`SP`-OK = 9
* W => `SP`-`aA`-OK-`SP`-`V`-`W`-OK = 6
* a => `W`-`V`-`U`-`aA`-OK-`u`-`p`-`k`-`f`-`a`-OK = 10
* r => `a`-`f`-`k`-`p`-`q`-`r`-OK = 6
* s => `r`-`s`-OK = 2

Answer = 14 + 16 + 4 + 2 + 9 + 6 + 10 + 6 + 2 = 69



*Good Luck!
DM.*



Series
* TV Remote
* TV Remote (shift and space)
* TV Remote (wrap)
* TV Remote (symbols)

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

In the field, two beggars A and B found some gold at the same time. They all wanted the gold, and they decided to use simple rules to distribute gold:
```
They divided gold into n piles and be in line. 
The amount of each pile and the order of piles all are randomly.

They took turns to take away a pile of gold from the 
far left or the far right.

They always choose the bigger pile. That is to say, 
if the left is 1, the right is 2, then choose to take 2.

If the both sides are equal, take the left pile.
```

Given an integer array `golds`, and assume that A always takes first. Please calculate the final amount of gold obtained by A and B. returns a two-element array `[amount of A, amount of B]`.

# Example

For `golds = [4,2,9,5,2,7]`, the output should be `[14,15]`.
```
The pile of most left is 4, 
The pile of most right is 7, 
A choose the largest one -- > take 7

The pile of most left is 4, 
The pile of most right is 2, 
B choose the largest one -- > take 4

The pile of most left is 2, 
The pile of most left is 2, 
A choose the most left one -- > take 2

The pile of most left is 9, 
The pile of most right is 2, 
B choose the largest one -- > take 9

The pile of most left is 5, 
The pile of most left is 2, 
A choose the largest one -- > take 5

Tehn, only 1 pile left, 
B  -- > take 2

A: 7 + 2 + 5 = 14
B: 4 + 9 + 2 = 15
```

For `golds = [10,1000,2,1]`, the output should be `[12,1001]`.
```
A take 10
B take 1000
A take 2
B take 1

A: 10 + 2 = 12
B: 1000 + 1 = 1001
```

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus has recently got interested in sequences of pseudorandom numbers. He learned that many programming languages generate such sequences in a similar way:  (for *i*<=≥<=1). Here *a*, *b*, *m* are constants, fixed for the given realization of the pseudorandom numbers generator, *r*0 is the so-called *randseed* (this value can be set from the program using functions like RandSeed(r) or srand(n)), and  denotes the operation of taking the remainder of division.

For example, if *a*<==<=2,<=*b*<==<=6,<=*m*<==<=12,<=*r*0<==<=11, the generated sequence will be: 4,<=2,<=10,<=2,<=10,<=2,<=10,<=2,<=10,<=2,<=10,<=....

Polycarpus realized that any such sequence will sooner or later form a cycle, but the cycle may occur not in the beginning, so there exist a preperiod and a period. The example above shows a preperiod equal to 1 and a period equal to 2.

Your task is to find the period of a sequence defined by the given values of *a*,<=*b*,<=*m* and *r*0. Formally, you have to find such minimum positive integer *t*, for which exists such positive integer *k*, that for any *i*<=≥<=*k*: *r**i*<==<=*r**i*<=+<=*t*.

Input Specification:
The single line of the input contains four integers *a*, *b*, *m* and *r*0 (1<=≤<=*m*<=≤<=105,<=0<=≤<=*a*,<=*b*<=≤<=1000,<=0<=≤<=*r*0<=&lt;<=*m*), separated by single spaces.

Output Specification:
Print a single integer — the period of the sequence.

Demo Input:
['2 6 12 11\n', '2 3 5 1\n', '3 6 81 9\n']

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

Note:
The first sample is described above. 

In the second sample the sequence is (starting from the first element): 0, 3, 4, 1, 0, 3, 4, 1, 0, ...

In the third sample the sequence is (starting from the first element): 33, 24, 78, 78, 78, 78, ...

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Garry is looking at the sky. Such a beautiful day! He notices that the clouds are particularly beautiful today, and wishes to record the current state of the sky. He has no camera, so he begins writing down coordinate points. Fortunately for Garry, the current cloud cover can be represented as the union of non-intersecting, non-degenerate triangles where each vertex is at a coordinate point on the $xy$-plane. Two triangles are considered non-intersecting if their intersection has area $0$. A triangle is degenerate if its area is $0$.

The next day, Garry’s friend Jerry goes to look at the sky. Jerry also wishes to record the current state of the sky. He follows the same protocol as Garry, and writes down the cloud cover as a set of non-intersecting triangles.

Garry and Jerry want to determine if they saw the same cloud cover. Unfortunately, there are multiple possible ways to represent the same cloud cover! Given Garry and Jerry’s notes, did they see the same cloud cover in the sky?

-----Input-----
The first line of input contains the integer $n$, $(0 \le n \le 100000)$, the number of triangles Garry wrote down. Each of the next $n$ lines contains $6$ space separated integers, $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, and $y_3$. These are Garry’s triangles. The next line contains the integer $m$, $(0 \le m \le 100000)$, the number of triangles Jerry wrote down. Each of the next $m$ lines contains $6$ space separated integers, $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, and $y_3$. These are Jerry’s triangles. The absolute value of the $x$ and $y$ coordinates are at most $10^9$. (That’s as far as Garry and Jerry can see.)

-----Output-----
Print “yes” if Garry and Jerry saw the same cloud cover, or “no” if they did not.

-----Examples-----
Sample Input 1:
1
10000 0 10000 10000 0 10000
3
10000 0 10000 10000 5000 5000
5000 5000 10000 10000 0 10000
0 0 0 1000 1000 0
Sample Output 1:
no

Sample Input 2:
2
9996 0 9997 0 0 1
9999 0 10000 0 0 1
2
9997 0 9998 0 0 1
9998 0 9999 0 0 1
Sample Output 2:
no

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Peter is bored during his operating systems class, so he draws doodles on a sheet of paper. He feels like drawing abstract art using his ruler: he draws line segments by choosing two points in the plane and connecting them. Lots of them.

Can you write a program that counts the number of distinct points at which the line segments he drew intersect or touch?

-----Input-----
The first line in the input contains an integer $n$ ($1 \le n \le 1000$) which is the number of lines. The following $n$ lines contain four integers $x_0 \ \ y_0 \ \ x_1 \ \ y_1$ ($-1000000 \le x_0, \ y_0, \ x_1, \ y_1 \le 1000000$). Lines have non-zero length, i.e., the two points will be distinct: $x_0 \ne x_1$ or $y_0 \ne y_1$ or both.

-----Output-----
Output the number of distinct points for which there is at least one pair of line segments that intersects or touches at this point. If there are infinitely many such points, output -1.

-----Examples-----
Sample Input 1:
3
1 3 9 5
2 2 6 8
4 8 9 3
Sample Output 1:
3

Sample Input 2:
3
5 2 7 10
7 4 4 10
2 4 10 8
Sample Output 2:
1

Sample Input 3:
3
2 1 6 5
2 5 5 4
5 1 7 7
Sample Output 3:
1

Sample Input 4:
2
-1 -2 -1 -1
-1 2 -1 -1
Sample Output 4:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
My grandfather always predicted how old people would get, and right before he passed away he revealed his secret!

In honor of my grandfather's memory we will write a function using his formula!

* Take a list of ages when each of your great-grandparent died.  
* Multiply each number by itself.  
* Add them all together.  
* Take the square root of the result.  
* Divide by two.

## Example

```R
predict_age(65, 60, 75, 55, 60, 63, 64, 45) == 86
```
```python
predict_age(65, 60, 75, 55, 60, 63, 64, 45) == 86
```

Note: the result should be rounded down to the nearest integer.

Some random tests might fail due to a bug in the JavaScript implementation. Simply resubmit if that happens to you.

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