vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Li and Lu have $n$ integers, $a_1,a_2,\ldots,a_n$, that they want to divide fairly between the two of them. They decide that if Li gets integers with indices $I=\{i_1,i_2,\ldots,i_k\}$ (which implies that Lu gets integers with indices $J=\{1,\ldots,n\}\setminus I$), then the measure of unfairness of this division is: 
$f(I)=\sum_{i\in I}\sum_{j\in J}|a_i-a_j|$

Find the minimum measure of unfairness that can be obtained with some division of the set of integers where Li gets exactly $\boldsymbol{\mbox{k}}$ integers. 

Note $A\setminus B$ means Set complement

Input Format

The first line contains two space-separated integers denoting the respective values of $n$ (the number of integers Li and Lu have) and $\boldsymbol{\mbox{k}}$ (the number of integers Li wants). 

The second line contains $n$ space-separated integers describing the respective values of $a_1,a_2,\ldots,a_n$.

Constraints

$1\leq k<n\leq3000$
$1\leq a_i\leq10^9$
For $15\%$ of the test cases, $n\leq20$.
For $45\%$ of the test cases, $n\leq40$.

Output Format

Print a single integer denoting the minimum measure of unfairness of some division where Li gets $\boldsymbol{\mbox{k}}$ integers.

Sample Input 0

4 2
4 3 1 2

Sample Output 0

 6

Explanation 0 

One possible solution for this input is $I=\{\text{{2,4}\}};\:J=\{\text{{1,3}\}}$. $|a_2-a_1|+|a_2-a_3|+|a_4-a_1|+|a_4-a_3|=1+2+2+1=6$

Sample Input 1   

4 1
3 3 3 1

Sample Output 1

2

Explanation 1 

The following division of numbers is optimal for this input: $I=\{1\};\:J=\{2,3,4\}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice became interested in periods of integer numbers. We say positive $X$ integer number is periodic with length $L$ if there exists positive integer number $P$ with $L$ digits such that $X$ can be written as $PPPP…P$. For example:

$X = 123123123$ is periodic number with length $L = 3$ and $L = 9$

$X = 42424242$ is periodic number with length $L = 2,L = 4$ and $L = 8$

$X = 12345$ is periodic number with length $L = 5$

For given positive period length $L$ and positive integer number $A$, Alice wants to find smallest integer number $X$ strictly greater than $A$ that is periodic with length L.


-----Input-----

First line contains one positive integer number $L \ (1 \leq L \leq 10^5)$ representing length of the period. Second line contains one positive integer number $A \ (1 \leq A \leq 10^{100 000})$.


-----Output-----

One positive integer number representing smallest positive number that is periodic with length $L$ and is greater than $A$.


-----Examples-----
Input
3
123456

Output
124124

Input
3
12345

Output
100100



-----Note-----

In first example 124124 is the smallest number greater than 123456 that can be written with period L = 3 (P = 124).

In the second example 100100 is the smallest number greater than 12345 with period L = 3 (P=100)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Aterp is the head nurse at a city hospital. City hospital contains R*C number of wards and the structure of a hospital is in the form of a 2-D matrix.
Given a matrix of dimension R*C where each cell in the matrix can have values 0, 1, or 2 which has the following meaning:
0: Empty ward
1: Cells have uninfected patients
2: Cells have infected patients
An infected patient at ward [i,j] can infect other uninfected patient at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right) in unit time. Help Aterp determine the minimum units of time after which there won't remain any uninfected patient i.e all patients would be infected. If all patients are not infected after infinite units of time then simply return -1.
 
Example 1:
Input:
3 5
2 1 0 2 1
1 0 1 2 1
1 0 0 2 1 
Output:
2
Explanation:
Patients at positions {0,0}, {0, 3}, {1, 3}
and {2, 3} will infect patient at {0, 1}, 
{1, 0},{0, 4}, {1, 2}, {1, 4}, {2, 4} during 1st 
unit time. And, during 2nd unit time, patient at 
{1, 0} will get infected and will infect patient 
at {2, 0}. Hence, total 2 unit of time is
required to infect all patients.
Example 2:
Input:
3 5
2 1 0 2 1
0 0 1 2 1
1 0 0 2 1
Output:
-1
Explanation:
All patients will not be infected.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function helpaterp() which takes a 2-D Matrix hospital as input parameter and returns the minimum units of time in which all patients will be infected or -1 if it is impossible.
Constraints:
1 ≤ R,C ≤ 1000
0 ≤ mat[i][j] ≤ 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today at the lesson of mathematics, Petya learns about the digital root.

The digital root of a non-negative integer is the single digit value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached. 

Let's denote the digital root of $x$ as $S(x)$. Then $S(5)=5$, $S(38)=S(3+8=11)=S(1+1=2)=2$, $S(10)=S(1+0=1)=1$.

As a homework Petya got $n$ tasks of the form: find $k$-th positive number whose digital root is $x$.

Petya has already solved all the problems, but he doesn't know if it's right. Your task is to solve all $n$ tasks from Petya's homework.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^3$) — the number of tasks in Petya's homework. The next $n$ lines contain two integers $k_i$ ($1 \le k_i \le 10^{12}$) and $x_i$ ($1 \le x_i \le 9$) — $i$-th Petya's task in which you need to find a $k_i$-th positive number, the digital root of which is $x_i$.


-----Output-----

Output $n$ lines, $i$-th line should contain a single integer — the answer to the $i$-th problem.


-----Example-----
Input
3
1 5
5 2
3 1

Output
5
38
19

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the volume of a cone whose radius and height are provided as parameters to the function `volume`. Use the value of PI provided by your language (for example: `Math.PI` in JS, `math.pi` in Python or `Math::PI` in Ruby) and round down the volume to an Interger.

If you complete this kata and there are no issues, please remember to give it a ready vote and a difficulty rating. :)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given four points in space (i.e. $\mathbb {R}^3$). The points are not coplanar. In other words, there is no plane in space that contains all four points.

It is guaranteed that under such assumption, there exists a (unique) sphere whose surface touches all four points. Find the coordinates of the centre of the sphere.

-----Input-----
The input consists of four lines. Line $i$ consists of three integers $x_ i$, $y_ i$, $z_ i$, representing the coordinates $(x_ i, y_ i, z_ i)$ of point $i$.

For all test cases, $-100 \leq x_ i, y_ i, z_ i \leq 100$.

-----Output-----
Output three numbers (not necessarily integers) $x_ c$, $y_ c$, $z_ c$, representing the coordinates $(x_ c, y_ c, z_ c)$ of the centre of the sphere that touches all four points.

Let the jury’s answer be $(x_ j, y_ j, z_ j)$. Your answer will be considered as correct if and only if\[ \sqrt {(x_ j - x_ c)^2 + (y_ j - y_ c)^2 + (z_ j - z_ c)^2} < 10^{-4}. \]

-----Examples-----
Sample Input 1:
0 0 0
1 0 0
0 1 0
0 0 1
Sample Output 1:
0.5 0.5 0.5

Sample Input 2:
-1 0 0
1 0 0
0 1 0
0 0 1
Sample Output 2:
0.0 0.0 -0.0

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

The input contains two integers N, M (1 ≤ N ≤ 1024, 2 ≤ M ≤ 16), separated by a single space.

Output

Output "YES" or "NO".

Examples

Input


2 3


Output


YES


Input


3 2


Output


NO


Input


33 16


Output


YES


Input


26 5


Output


NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a square-shaped chart paper with the side length equal to N. He wants to cut out K \times K squares from this chart paper. 

Find the maximum number of K \times K squares he can cut from the entire chart paper.

Note that, some part of the chart paper might not be a included in any K \times K cutout square.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space-separated integers N and K — the side length of the entire chart paper and the side length of the cutout squares.

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

For each test case, output on a new line the maximum number of K \times K squares Chef can cut from the entire chart paper.

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

$1 ≤ T ≤ 1000$
$1 ≤ K ≤N ≤ 1000$

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

----- Sample Output 1 ------ 
25
1
4

----- explanation 1 ------ 
Test case 1: Chef can cut out $25$ squares of size $1 \times 1$ from the entire $5 \times 5$ chart paper.

Test case 2: Chef can cut out $1$ square of size $2 \times 2$ from the entire $2 \times 2$ chart paper.

Test case 3: Chef can cut out $4$ squares of size $2 \times 2$ from the entire $5 \times 5$ chart paper.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Steve and Josh are bored and want to play something. They don't want to think too much, so they come up with a really simple game. Write a function called winner and figure out who is going to win.

They are dealt the same number of cards. They both flip the card on the top of their deck. Whoever has a card with higher value wins the round and gets one point (if the cards are of the same value, neither of them gets a point). After this, the two cards are discarded and they flip another card from the top of their deck. They do this until they have no cards left.

`deckSteve` and `deckJosh` are arrays representing their decks. They are filled with *cards*, represented by a single character. The card rank is as follows (from lowest to highest):
```
'2','3','4','5','6','7','8','9','T','J','Q','K','A'
```

Every card may appear in the deck more than once. Figure out who is going to win and return who wins and with what score:
* `"Steve wins x to y"` if Steve wins; where `x` is Steve's score, `y` is Josh's score;
* `"Josh wins x to y"` if Josh wins; where `x` is Josh's score, `y` is Steve's score;
* `"Tie"` if the score is tied at the end of the game.


## Example

* Steve is dealt: `['A','7','8']`
* Josh is dealt: `['K','5','9']`

1. In the first round, ace beats king and Steve gets one point.
2. In the second round, 7 beats 5 and Steve gets his second point.
3. In the third round, 9 beats 8 and Josh gets one point.

So you should return: `"Steve wins 2 to 1"`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In some village, there are 999 towers that are 1,(1+2),(1+2+3),...,(1+2+3+...+999) meters high from west to east, at intervals of 1 meter.
It had been snowing for a while before it finally stopped. For some two adjacent towers located 1 meter apart, we measured the lengths of the parts of those towers that are not covered with snow, and the results are a meters for the west tower, and b meters for the east tower.
Assuming that the depth of snow cover and the altitude are the same everywhere in the village, find the amount of the snow cover.
Assume also that the depth of the snow cover is always at least 1 meter.

-----Constraints-----
 - 1 \leq a < b < 499500(=1+2+3+...+999)
 - All values in input are integers.
 - There is no input that contradicts the assumption.

-----Input-----
Input is given from Standard Input in the following format:
a b

-----Output-----
If the depth of the snow cover is x meters, print x as an integer.

-----Sample Input-----
8 13

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

The heights of the two towers are 10 meters and 15 meters, respectively.
Thus, we can see that the depth of the snow cover is 2 meters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your favorite uncle has passed away, leaving you a large estate. Bank account numbers, locations of safe deposit boxes, and GPS coordinates to buried treasures are all locked in an electronic safe in your uncle’s office behind a picture of dogs playing poker. One day he showed you the safe with its $9$ digit keypad (digits $1$ through $9$). He told you he wasn’t worried about anyone breaking into his safe because it’s equipped with a self-destruct mechanism that will destroy the contents if anyone attempts a forced entry.

The combination is a sequence of six decimal digits. If an incorrect combination is entered the safe enforces a thirty-second delay before accepting another combination. So a brute-force effort to try all six-digit combinations could take months.

Your uncle had planned to give you, his sole heir, the combination one day, but due to an unfortunate hang-gliding accident in Kansas, you now must rely on your deductive and programming skills to access the key to your inheritance.

Here’s what you know:
 - The combination $c$ is a sequence of six non-zero decimal digits.
 - Your mother recalls that she heard your uncle mention that all the digits are different.
 - You remember that your uncle once said that the six digit number was divisible by each of its individual digits.

An example satisfying these conditions is $123864$: all six digits differ, and you can check that $123864$ is divisible by each of $1$, $2$, $3$, $8$, $6$ and $4$.

Even with the helpful data, it could take a while to get to open the safe, so the task is likely to be split into several sessions with separate ranges being tested. How many combinations are there to try in the range given?

-----Input-----
The input is a line with two space-separated integers $L$ and $H$, where $123456 \leq L < H \leq 987654$

-----Output-----
Print one integer, the total number of possible combinations to the safe, where each combination $c$ must satisfy the three constraints above, and lie in the range $L \leq c \leq H$.

-----Examples-----
Sample Input 1:
123864 123865
Sample Output 1:
1

Sample Input 2:
198765 198769
Sample Output 2:
0

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
This year, as in previous years, MemSQL is inviting the top 25 competitors from the Start[c]up qualification round to compete onsite for the final round. Not everyone who is eligible to compete onsite can afford to travel to the office, though. Initially the top 25 contestants are invited to come onsite. Each eligible contestant must either accept or decline the invitation. Whenever a contestant declines, the highest ranked contestant not yet invited is invited to take the place of the one that declined. This continues until 25 contestants have accepted invitations.

After the qualifying round completes, you know *K* of the onsite finalists, as well as their qualifying ranks (which start at 1, there are no ties). Determine the minimum possible number of contestants that declined the invitation to compete onsite in the final round.

Input Specification:
The first line of input contains *K* (1<=≤<=*K*<=≤<=25), the number of onsite finalists you know. The second line of input contains *r*1,<=*r*2,<=...,<=*r**K* (1<=≤<=*r**i*<=≤<=106), the qualifying ranks of the finalists you know. All these ranks are distinct.

Output Specification:
Print the minimum possible number of contestants that declined the invitation to compete onsite.

Demo Input:
['25\n2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 22 23 24 25 26 28\n', '5\n16 23 8 15 4\n', '3\n14 15 92\n']

Demo Output:
['3\n', '0\n', '67\n']

Note:
In the first example, you know all 25 onsite finalists. The contestants who ranked 1-st, 13-th, and 27-th must have declined, so the answer is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in mandarin chinese, russian and vietnamese as well. 

This year CodeChef is organizing the SnackUp cooking contest. The favorite to win is of course our beautiful Chef Ada.

There are n judges in the contest, and for simplicity let's enumerate judges from 1 to n. 

Ada has an uncountable repertoire of delicious recipes, but for the contest she choose only n of them. Let's also enumerate the recipes from 1 to n.

Ada is going to show off her cooking skills in many rounds, and we are going to help her organizing them! One round is structured as follows:
We will choose k distinct recipes and Ada will prepare two identical dishes for each of them.
We will choose k distinct judges for the round.
We will send k invitation letters (one for each of the chosen judges). Each letter must contain the number of the judge, and two distinct integers denoting the ids of the recipes that he is going to taste. 
Two different judges can taste the same recipe, but it must be from different dishes. 
Ada does not like to waste food, so the letters must be designed in such a way that every prepared dish is tasted.

You can arbitrarily decide the number of rounds and the number of invited judges in each round, but as a rule of the contest at the end of all rounds each judge must have tasted every recipe exactly twice.

------ Input ------ 

The first line of input contains one number T, the number of test cases.
Each test case consist of one line containing an integer n, the number of judges.

------ Output ------ 

For each testcase, in the first line, print r the number of rounds, then describe each round as follows.

In the first line of each round, print k, the number of invited judges.
In the next k lines, print the invitation letters as three space separated integers: j, x, y denoting the id of the judge, and the ids of the recipe that he is going to taste. Note that x should not be equal to y.

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

1 ≤ T ≤ 100
2 ≤ n ≤ 100

----- Sample Input 1 ------ 
1
2
----- Sample Output 1 ------ 
2
2
1 1 2
2 1 2
2
1 1 2
2 1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imp is really pleased that you helped him. But it you solve the last problem, his gladness would raise even more.

<image> Let's define <image> for some set of integers <image> as the number of pairs a, b in <image>, such that:

  * a is strictly less than b; 
  * a divides b without a remainder. 



You are to find such a set <image>, which is a subset of {1, 2, ..., n} (the set that contains all positive integers not greater than n), that <image>. 

Input

The only line contains two integers n and k <image>.

Output

If there is no answer, print "No".

Otherwise, in the first line print "Yes", in the second — an integer m that denotes the size of the set <image> you have found, in the second line print m integers — the elements of the set <image>, in any order.

If there are multiple answers, print any of them.

Examples

Input

3 3


Output

No


Input

6 6


Output

Yes
5
1 2 4 5 6 

Input

8 3


Output

Yes
4
2 4 5 8

Note

In the second sample, the valid pairs in the output set are (1, 2), (1, 4), (1, 5), (1, 6), (2, 4), (2, 6). Thus, <image>.

In the third example, the valid pairs in the output set are (2, 4), (4, 8), (2, 8). Thus, <image>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to sort a given string. Each word in the string will contain a single number. This number is the position the word should have in the result.

Note: Numbers can be from 1 to 9. So 1 will be the first word (not 0).

If the input string is empty, return an empty string.
The words in the input String will only contain valid consecutive numbers.


## Examples

```
"is2 Thi1s T4est 3a"  -->  "Thi1s is2 3a T4est"
"4of Fo1r pe6ople g3ood th5e the2"  -->  "Fo1r the2 g3ood 4of th5e pe6ople"
""  -->  ""
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a directed graph with N vertices and N edges. The vertices are numbered 1, 2, ..., N.
The graph has the following N edges: (p_1, 1), (p_2, 2), ..., (p_N, N), and the graph is weakly connected. Here, an edge from Vertex u to Vertex v is denoted by (u, v), and a weakly connected graph is a graph which would be connected if each edge was bidirectional.
We would like to assign a value to each of the vertices in this graph so that the following conditions are satisfied. Here, a_i is the value assigned to Vertex i.
 - Each a_i is a non-negative integer.
 - For each edge (i, j), a_i \neq a_j holds.
 - For each i and each integer x(0 ≤ x < a_i), there exists a vertex j such that the edge (i, j) exists and x = a_j holds.
Determine whether there exists such an assignment.

-----Constraints-----
 - 2 ≤ N ≤ 200 000
 - 1 ≤ p_i ≤ N
 - p_i \neq i
 - The graph is weakly connected.

-----Input-----
Input is given from Standard Input in the following format:
N
p_1 p_2 ... p_N

-----Output-----
If the assignment is possible, print POSSIBLE; otherwise, print IMPOSSIBLE.

-----Sample Input-----
4
2 3 4 1

-----Sample Output-----
POSSIBLE

The assignment is possible: {a_i} = {0, 1, 0, 1} or {a_i} = {1, 0, 1, 0}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your job is to create a calculator which evaluates expressions in [Reverse Polish notation](http://en.wikipedia.org/wiki/Reverse_Polish_notation).

For example expression `5 1 2 + 4 * + 3 -` (which is equivalent to `5 + ((1 + 2) * 4) - 3` in normal notation) should evaluate to `14`.

For your convenience, the input is formatted such that a space is provided between every token.

Empty expression should evaluate to `0`.

Valid operations are `+`, `-`, `*`, `/`.

You may assume that there won't be exceptional situations (like stack underflow or division by zero).

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