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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Everybody knows what an arithmetic progression is. Let us remind you just in case that an arithmetic progression is such sequence of numbers *a*1,<=*a*2,<=...,<=*a**n* of length *n*, that the following condition fulfills: 

For example, sequences [1, 5], [10], [5, 4, 3] are arithmetic progressions and sequences [1, 3, 2], [1, 2, 4] are not.

Alexander has *n* cards containing integers. Arthur wants to give Alexander exactly one more card with a number so that he could use the resulting *n*<=+<=1 cards to make an arithmetic progression (Alexander has to use all of his cards).

Arthur has already bought a card but he hasn't written a number on it. Help him, print all integers that you can write on a card so that the described condition fulfilled.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) — the number of cards. The next line contains the sequence of integers — the numbers on Alexander's cards. The numbers are positive integers, each of them doesn't exceed 108.

Output Specification:
If Arthur can write infinitely many distinct integers on the card, print on a single line -1.

Otherwise, print on the first line the number of integers that suit you. In the second line, print the numbers in the increasing order. Note that the numbers in the answer can exceed 108 or even be negative (see test samples).

Demo Input:
['3\n4 1 7\n', '1\n10\n', '4\n1 3 5 9\n', '4\n4 3 4 5\n', '2\n2 4\n']

Demo Output:
['2\n-2 10\n', '-1\n', '1\n7\n', '0\n', '3\n0 3 6\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alexander is learning how to convert numbers from the decimal system to any other, however, he doesn't know English letters, so he writes any number only as a decimal number, it means that instead of the letter A he will write the number 10. Thus, by converting the number 475 from decimal to hexadecimal system, he gets 11311 (475 = 1·16^2 + 13·16^1 + 11·16^0). Alexander lived calmly until he tried to convert the number back to the decimal number system.

Alexander remembers that he worked with little numbers so he asks to find the minimum decimal number so that by converting it to the system with the base n he will get the number k.


-----Input-----

The first line contains the integer n (2 ≤ n ≤ 10^9). The second line contains the integer k (0 ≤ k < 10^60), it is guaranteed that the number k contains no more than 60 symbols. All digits in the second line are strictly less than n.

Alexander guarantees that the answer exists and does not exceed 10^18.

The number k doesn't contain leading zeros.


-----Output-----

Print the number x (0 ≤ x ≤ 10^18) — the answer to the problem.


-----Examples-----
Input
13
12

Output
12
Input
16
11311

Output
475
Input
20
999

Output
3789
Input
17
2016

Output
594


-----Note-----

In the first example 12 could be obtained by converting two numbers to the system with base 13: 12 = 12·13^0 or 15 = 1·13^1 + 2·13^0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A terrible monster is rampaging through Neo Tokyo 5! The Earth Defense Force (EDF) has sent a mech unit1 to defeat the monster. Because there is only a single mech unit available after previous monster rampages, the EDF has decided to simulate the upcoming battle between the mech and the monster before launching an assault. The EDF noted that the monster’s attack pattern can be simulated by a series of moves that it performs in succession. When denoting each of its moves with a single letter, the attack pattern can be simulated as a single string, which should be read from left to right. The monster has the following moves:
 - Rake, denoted by the letter ‘R’;
 - Bite, denoted by the letter ‘B’;
 - Laser breath, denoted by the letter ‘L’.

In order to defeat the monster, the mech must perform a counter move per move that the monster makes:
 - Slice, denoted by the letter ‘S’, counters the monster’s rake;
 - Kick, denoted by the letter ‘K’, counters the monster’s bite;
 - Shield, denoted by the letter ‘H’, counters the monster’s laser breath;

However, there is one catch. When the monster performs a subsequent combination of the three moves Rake, Bite and Laser breath, in any order, it becomes a very powerful attack for which the mech must perform a single counter move called Combo breaker, denoted by the letter ‘C’. A single Combo breaker absorbs the entire combination of three moves. Any following moves from the monster will have to be countered separately or as part of a new combination. A move of the monster can never be part of more than one combination.

Through extensive analysis of the monster’s past behaviour, the EDF is now able to reliably predict the actions of the monster ahead of time. You are given a string representing the moves that the monster will use when battling the mech. The EDF needs you to write a program that outputs the sequence of moves that the mech must perform in order to defeat the monster.

-----Input-----
A single line containing a string of at least $1$ and at most $1000000$ characters, consisting of the letters ‘R’, ‘B’ and ‘L’.

-----Output-----
Output a single string consisting of the letters denoting the moves that are to be made in succession by the mech in order to defeat the monster.

-----Examples-----
Sample Input 1:
RRBBBLLR
Sample Output 1:
SSKKKHHS

Sample Input 2:
RBLLLBRR
Sample Output 2:
CHCS

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a permutation of integers from 1 to N (very unusual :D). The only thing you should do is to process M queries. Each query has 2 parameters: number X from 1 to N and lowercase latin letter Y (either 'l' or 'r'). You do the following:
Calculate distances from the position of the number X to the left end and to the right end of the permutation. Let's call minimum of them accessibleness.
Erase number X from it's current position. If parameter Y is 'l' then insert X the very beginning of the permutation. Otherwise insert X after the last element of the permutation. 

Please find sum of accessibleness over all queries.

Input 
The first line contains two space-separated integers: N and M. The second line contains N space-separated integers: the initial permutation. After this M lines follow containing 2 space-separated parameters each in the way it's described in the statement above.

Output 
Output one number - answer for the question.

Constraints 
 0 < N, M  ≤ 500 000
 0 < N, M  ≤ 2 000 in 35 % of the test data.
 0 < N, M  ≤ 70 000 in 70 % of the test data.

SAMPLE INPUT
4 3
3 1 4 2
3 r
2 r
1 l

SAMPLE OUTPUT
1

Explanation

Permutation before the 1st query: 3 1 4 2. 3 has accessibleness  0. 
Permutation before the 2nd query: 1 4 2 3. 2 has accessibleness  1. 
Permutation before the 3rd query: 1 4 3 2. 1 has accessibleness  0. 
So the sum over all queries is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a programmer working for your local city hall. The town you live in has a thriving tourism industry, especially the beaches on the shores of remote islands. The area around this island is composed of sandy beaches, but in recent years the area of ​​the sandy beaches has decreased due to coastal erosion. The Tourism Division, which took the situation seriously, asked you to simulate the shape change of the beach.

In the simulation, the shape of the beach after a certain period of time is obtained based on the current shape of the beach. For simplicity, the shape of the island's coastline is considered polygonal (not necessarily convex). During the period, it is assumed that the beach is eroded by R at a distance from the current coastline in Manhattan and sinks into the sea. Here, the Manhattan distance is the sum of the difference between the x-coordinates and the difference between the y-coordinates. That is, the Manhattan distance between (x1, y1) and (x2, y2) is given by | x1 --x2 | + | y1 --y2 |.

Your job is to write a program to find the length of the shoreline obtained as a result of the simulation from the shoreline of the sandy beach given as input. If an island is divided into two or more due to coastal erosion, find the length of the coastline for each divided island and output the sum of them.

It should be noted that the two line segments included in the coastline are parallel and the Manhattan distance is not exactly 2R.

Input

The input consists of multiple datasets. Each dataset is given in the following format.

> N R
> x1 y1
> x2 y2
> ...
> xN yN

The first line gives two non-negative integers N (3 ≤ N ≤ 100) and R (0 <R ≤ 100). These integers represent the number of vertices on the coastline and the distance eroded, respectively. In the following N lines, vertex information is given to each line, one for each line. Vertex information is given by two integers xi, yi (-10000 ≤ xi, yi ≤ 10000). The coordinates (xi, yi) represent the coordinates of the i-th vertex of the coastline, respectively. The coordinates of the vertices of the island are always given counterclockwise.

The end of the input is indicated by a single line containing two zeros separated by blanks.

Output

Output the length of the eroded coastline for each dataset. If the island is completely eroded and disappears, the length of the coastline should be treated as 0.0. The output value may contain an error of 0.01 or less. In addition, the value may be displayed in any number of digits after the decimal point.

Sample Input


3 1
0 0
10 0
5 10
3 1
0 0
10 0
0 10
4 1
0 0
10 0
10 10
0 10
0 0


Output for the Sample Input


22.6524758425
23.8994949366
32.0000000000






Example

Input

3 1
0 0
10 0
5 10
3 1
0 0
10 0
0 10
4 1
0 0
10 0
10 10
0 10
0 0


Output

22.6524758425
23.8994949366
32.0000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A pronic number is a number which is the product of two consecutive integers. Find all Pronic Numbers less than  or equal to the given integer N.
The first few Pronic numbers are: 0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132 and so on.
Example 1:
Input:
N = 6
Output:
0 2 6
Explanation:
0 is the product of 0 and 1.
2 is the product of 1 and 2.
6 is the product of 2 and 3.
Example 2:
Input:
N = 56
Output:
0 2 6 12 20 30 42 56
Explanation:
0 is the product of 0 and 1.
2 is the product of 1 and 2.
6 is the product of 2 and 3.
12 is the product of 3 and 4.
and so on.
Your Task:  
You don't need to read input. Your task is to complete the function pronicNumbers() which takes an integer N as input parameter and returns a list of integers. 
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints: 
1 <= N <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
**This Kata is intended as a small challenge for my students**

All Star Code Challenge #23

There is a certain multiplayer game where players are assessed at the end of the game for merit. Players are ranked according to an internal scoring system that players don't see.

You've discovered the formula for the scoring system!

Create a function called `scoring()` that takes an array of Player objects and returns an array of player names, in order of descending score (highest score is index 0, 2nd highest is index 1, etc.).

Each player's score is calculated as follows:

1. Each normal kill is worth 100 points
2. Each assist is worth 50 points
3. Each point of damage done is worth .5 points
4. Each point of healing done is worth 1 point
5. The longest kill streak is worth 2^N, where N is the number of kills of the streak
6. Environmental kills are worth 500 points (These are counted separately from normal kills)

For each of the above statistic, a Player object contains a respective "key:value" pairing. All values except the 'name' are integers.

Note:  
Assume the input array will ALWAYS have a properly constructed Player object (no missing keys or values)  
Names will not contain unusual characters nor repeat (names are unique)  
Players with the same score should be sorted by the order they appear in the array  
For simplicity, for a kill streak of 0 the kill streak calculation will yield 1 (or 2^(0)) points

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Pasha has many hamsters and he makes them work out. Today, *n* hamsters (*n* is even) came to work out. The hamsters lined up and each hamster either sat down or stood up.

For another exercise, Pasha needs exactly  hamsters to stand up and the other hamsters to sit down. In one minute, Pasha can make some hamster ether sit down or stand up. How many minutes will he need to get what he wants if he acts optimally well?

Input Specification:
The first line contains integer *n* (2<=≤<=*n*<=≤<=200; *n* is even). The next line contains *n* characters without spaces. These characters describe the hamsters' position: the *i*-th character equals 'X', if the *i*-th hamster in the row is standing, and 'x', if he is sitting.

Output Specification:
In the first line, print a single integer — the minimum required number of minutes. In the second line, print a string that describes the hamsters' position after Pasha makes the required changes. If there are multiple optimal positions, print any of them.

Demo Input:
['4\nxxXx\n', '2\nXX\n', '6\nxXXxXx\n']

Demo Output:
['1\nXxXx\n', '1\nxX\n', '0\nxXXxXx\n']

Note:
none

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
In a strategic computer game "Settlers II" one has to build defense structures to expand and protect the territory. Let's take one of these buildings. At the moment the defense structure accommodates exactly *n* soldiers. Within this task we can assume that the number of soldiers in the defense structure won't either increase or decrease.

Every soldier has a rank — some natural number from 1 to *k*. 1 stands for a private and *k* stands for a general. The higher the rank of the soldier is, the better he fights. Therefore, the player profits from having the soldiers of the highest possible rank.

To increase the ranks of soldiers they need to train. But the soldiers won't train for free, and each training session requires one golden coin. On each training session all the *n* soldiers are present.

At the end of each training session the soldiers' ranks increase as follows. First all the soldiers are divided into groups with the same rank, so that the least possible number of groups is formed. Then, within each of the groups where the soldiers below the rank *k* are present, exactly one soldier increases his rank by one.

You know the ranks of all *n* soldiers at the moment. Determine the number of golden coins that are needed to increase the ranks of all the soldiers to the rank *k*.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*,<=*k*<=≤<=100). They represent the number of soldiers and the number of different ranks correspondingly. The second line contains *n* numbers in the non-decreasing order. The *i*-th of them, *a**i*, represents the rank of the *i*-th soldier in the defense building (1<=≤<=*i*<=≤<=*n*, 1<=≤<=*a**i*<=≤<=*k*).

Output Specification:
Print a single integer — the number of golden coins needed to raise all the soldiers to the maximal rank.

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

Demo Output:
['4', '5']

Note:
In the first example the ranks will be raised in the following manner:

1 2 2 3  →  2 2 3 4  →  2 3 4 4  →  3 4 4 4  →  4 4 4 4

Thus totals to 4 training sessions that require 4 golden coins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of $n$ integers $a_1, a_2, \dots, a_n$. You are also given $x$ integers $1, 2, \dots, x$.

You are asked to insert each of the extra integers into the sequence $a$. Each integer can be inserted at the beginning of the sequence, at the end of the sequence, or between any elements of the sequence.

The score of the resulting sequence $a'$ is the sum of absolute differences of adjacent elements in it $\left(\sum \limits_{i=1}^{n+x-1} |a'_i - a'_{i+1}|\right)$.

What is the smallest possible score of the resulting sequence $a'$?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $x$ ($1 \le n, x \le 2 \cdot 10^5$) — the length of the sequence and the number of extra integers.

The second line of each testcase contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$).

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase, print a single integer — the smallest sum of absolute differences of adjacent elements of the sequence after you insert the extra integers into it.


-----Examples-----

Input
4
1 5
10
3 8
7 2 10
10 2
6 1 5 7 3 3 9 10 10 1
4 10
1 3 1 2
Output
9
15
31
13


-----Note-----

Here are the sequences with the smallest scores for the example. The underlined elements are the extra integers. Note that there exist other sequences with this smallest score.

$\underline{1}, \underline{2}, \underline{3}, \underline{4}, \underline{5}, 10$

$\underline{7}, 7, \underline{6}, \underline{4}, 2, \underline{2}, \underline{1}, \underline{3}, \underline{5}, \underline{8}, 10$

$6, \underline{1}, 1, \underline{2}, 5, 7, 3, 3, 9, 10, 10, 1$

$1, 3, \underline{1}, 1, 2, \underline{2}, \underline{3}, \underline{4}, \underline{5}, \underline{6}, \underline{7}, \underline{8}, \underline{9}, \underline{10}$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected unweighted tree consisting of $n$ vertices.

An undirected tree is a connected undirected graph with $n - 1$ edges.

Your task is to choose two pairs of vertices of this tree (all the chosen vertices should be distinct) $(x_1, y_1)$ and $(x_2, y_2)$ in such a way that neither $x_1$ nor $y_1$ belong to the simple path from $x_2$ to $y_2$ and vice versa (neither $x_2$ nor $y_2$ should not belong to the simple path from $x_1$ to $y_1$).

It is guaranteed that it is possible to choose such pairs for the given tree.

Among all possible ways to choose such pairs you have to choose one with the maximum number of common vertices between paths from $x_1$ to $y_1$ and from $x_2$ to $y_2$. And among all such pairs you have to choose one with the maximum total length of these two paths.

It is guaranteed that the answer with at least two common vertices exists for the given tree.

The length of the path is the number of edges in it.

The simple path is the path that visits each vertex at most once.


-----Input-----

The first line contains an integer $n$ — the number of vertices in the tree ($6 \le n \le 2 \cdot 10^5$).

Each of the next $n - 1$ lines describes the edges of the tree.

Edge $i$ is denoted by two integers $u_i$ and $v_i$, the labels of vertices it connects ($1 \le u_i, v_i \le n$, $u_i \ne v_i$).

It is guaranteed that the given edges form a tree.

It is guaranteed that the answer with at least two common vertices exists for the given tree.


-----Output-----

Print any two pairs of vertices satisfying the conditions described in the problem statement.

It is guaranteed that it is possible to choose such pairs for the given tree.


-----Examples-----
Input
7
1 4
1 5
1 6
2 3
2 4
4 7

Output
3 6
7 5

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

Output
2 9
6 8

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

Output
10 6
4 5

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

Output
9 11
8 10



-----Note-----

The picture corresponding to the first example: [Image]

The intersection of two paths is $2$ (vertices $1$ and $4$) and the total length is $4 + 3 = 7$.

The picture corresponding to the second example: [Image]

The intersection of two paths is $2$ (vertices $3$ and $4$) and the total length is $5 + 3 = 8$.

The picture corresponding to the third example: $88^{\circ}$

The intersection of two paths is $3$ (vertices $2$, $7$ and $8$) and the total length is $5 + 5 = 10$.

The picture corresponding to the fourth example: $\$ 8$

The intersection of two paths is $5$ (vertices $1$, $2$, $3$, $4$ and $5$) and the total length is $6 + 6 = 12$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A positive integer $a$ is given. Baron Munchausen claims that he knows such a positive integer $n$ that if one multiplies $n$ by $a$, the sum of its digits decreases $a$ times. In other words, $S(an) = S(n)/a$, where $S(x)$ denotes the sum of digits of the number $x$. 

Find out if what Baron told can be true.


-----Input-----

The only line contains a single integer $a$ ($2 \le a \le 10^3$).


-----Output-----

If there is no such number $n$, print $-1$.

Otherwise print any appropriate positive integer $n$. Your number must not consist of more than $5\cdot10^5$ digits. We can show that under given constraints either there is no answer, or there is an answer no longer than $5\cdot10^5$ digits.


-----Examples-----
Input
2

Output
6

Input
3

Output
6669

Input
10

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Abhinav and Manav both being one of the best coders of SVNIT went onto participate in ACM ICPC Regional Contest. Apparently Manav’s team the 3Horsemen stood ahead of Abhinav’s team akatsuki11 in the contest though both solved the same number of questions .Manav is Abhinav’s greatest rival and Abhinav being adamant about him being The Best gives Manav a challenge described below:

For each positive number N consider the number mirror(N) which is obtained from N by replacing every digit d in the decimal notation(base 10) of N with the digit (9-d). We can now say that mirror(N) is the mirror image of N. For example, reflection of 325 equals 674. Note that leading zeros (if any) should be omitted. So the mirror image of 9 equals 0, so mirror(91) equals 8.
Let us define weight as the product of the number and its mirror image i.e. N * mirror(N). Thus, the weight of the number 20 is equal to 20 ·79 = 1580.

Manav is very weak in mathematics and also he doesn’t want to lose this challenge. So now it’s your job to save Manav from Abhinav’s arrogance. Your task is to find the maximum weight of the numbers in the given range [L,R] (including boundaries).

Input:

First line of input contains number of test cases T. Next T lines contain two positive numbers L and R.

Output:

Find the maximum weight of the numbers in the given range [L, R] for each test case.

Constraints:

1 ≤ T ≤ 24

1 ≤ L ≤ R ≤ 10^9

SAMPLE INPUT
3
3 7
1 1
8 10

SAMPLE OUTPUT
20
8
890

Explanation

For test case 3 

8 * mirror(8) = 8 * 1 = 1

9 * mirror(9) = 9 * 0 = 0

10 * mirror(10) = 10 * 89 = 890

So max(1,0,890) = 890

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