vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Dreamoon likes coloring cells very much.

There is a row of $n$ cells. Initially, all cells are empty (don't contain any color). Cells are numbered from $1$ to $n$.

You are given an integer $m$ and $m$ integers $l_1, l_2, \ldots, l_m$ ($1 \le l_i \le n$)

Dreamoon will perform $m$ operations.

In $i$-th operation, Dreamoon will choose a number $p_i$ from range $[1, n-l_i+1]$ (inclusive) and will paint all cells from $p_i$ to $p_i+l_i-1$ (inclusive) in $i$-th color. Note that cells may be colored more one than once, in this case, cell will have the color from the latest operation.

Dreamoon hopes that after these $m$ operations, all colors will appear at least once and all cells will be colored. Please help Dreamoon to choose $p_i$ in each operation to satisfy all constraints.


-----Input-----

The first line contains two integers $n,m$ ($1 \leq m \leq n \leq 100\,000$).

The second line contains $m$ integers $l_1, l_2, \ldots, l_m$ ($1 \leq l_i \leq n$).


-----Output-----

If it's impossible to perform $m$ operations to satisfy all constraints, print "'-1" (without quotes).

Otherwise, print $m$ integers $p_1, p_2, \ldots, p_m$ ($1 \leq p_i \leq n - l_i + 1$), after these $m$ operations, all colors should appear at least once and all cells should be colored.

If there are several possible solutions, you can print any.


-----Examples-----
Input
5 3
3 2 2

Output
2 4 1

Input
10 1
1

Output
-1

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya recently learned to determine whether a string of lowercase Latin letters is lucky. For each individual letter all its positions in the string are written out in the increasing order. This results in 26 lists of numbers; some of them can be empty. A string is considered lucky if and only if in each list the absolute difference of any two adjacent numbers is a lucky number. 

For example, let's consider string "zbcdzefdzc". The lists of positions of equal letters are:
-  b: 2-  c: 3,<=10-  d: 4,<=8-  e: 6-  f: 7-  z: 1,<=5,<=9-  Lists of positions of letters a, g, h, ..., y are empty.
This string is lucky as all differences are lucky numbers. For letters z: 5<=-<=1<==<=4, 9<=-<=5<==<=4, for letters c: 10<=-<=3<==<=7, for letters d: 8<=-<=4<==<=4. 

Note that if some letter occurs only once in a string, it doesn't influence the string's luckiness after building the lists of positions of equal letters. The string where all the letters are distinct is considered lucky.

Find the lexicographically minimal lucky string whose length equals *n*.

Input Specification:
The single line contains a positive integer *n* (1<=≤<=*n*<=≤<=105) — the length of the sought string.

Output Specification:
Print on the single line the lexicographically minimal lucky string whose length equals *n*.

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

Demo Output:
['abcda\n', 'abc\n']

Note:
The lexical comparison of strings is performed by the &lt; operator in modern programming languages. String *a* is lexicographically less than string *b* if exists such *i* (1 ≤ *i* ≤ *n*), that *a*<sub class="lower-index">*i*</sub> &lt; *b*<sub class="lower-index">*i*</sub>, and for any *j* (1 ≤ *j* &lt; *i*) *a*<sub class="lower-index">*j*</sub> = *b*<sub class="lower-index">*j*</sub>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke and Raccoon have a heap of N cards. The i-th card from the top has the integer a_i written on it.
They will share these cards.
First, Snuke will take some number of cards from the top of the heap, then Raccoon will take all the remaining cards.
Here, both Snuke and Raccoon have to take at least one card.
Let the sum of the integers on Snuke's cards and Raccoon's cards be x and y, respectively.
They would like to minimize |x-y|.
Find the minimum possible value of |x-y|.

-----Constraints-----
 - 2 \leq N \leq 2 \times 10^5
 - -10^{9} \leq a_i \leq 10^{9}
 - a_i is an integer.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 a_2 ... a_{N}

-----Output-----
Print the answer.

-----Sample Input-----
6
1 2 3 4 5 6

-----Sample Output-----
1

If Snuke takes four cards from the top, and Raccoon takes the remaining two cards, x=10, y=11, and thus |x-y|=1. This is the minimum possible value.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n piles of pebbles on the table, the i-th pile contains ai pebbles. Your task is to paint each pebble using one of the k given colors so that for each color c and any two piles i and j the difference between the number of pebbles of color c in pile i and number of pebbles of color c in pile j is at most one.

In other words, let's say that bi, c is the number of pebbles of color c in the i-th pile. Then for any 1 ≤ c ≤ k, 1 ≤ i, j ≤ n the following condition must be satisfied |bi, c - bj, c| ≤ 1. It isn't necessary to use all k colors: if color c hasn't been used in pile i, then bi, c is considered to be zero.

Input

The first line of the input contains positive integers n and k (1 ≤ n, k ≤ 100), separated by a space — the number of piles and the number of colors respectively.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 100) denoting number of pebbles in each of the piles.

Output

If there is no way to paint the pebbles satisfying the given condition, output "NO" (without quotes) .

Otherwise in the first line output "YES" (without quotes). Then n lines should follow, the i-th of them should contain ai space-separated integers. j-th (1 ≤ j ≤ ai) of these integers should be equal to the color of the j-th pebble in the i-th pile. If there are several possible answers, you may output any of them.

Examples

Input

4 4
1 2 3 4


Output

YES
1
1 4
1 2 4
1 2 3 4


Input

5 2
3 2 4 1 3


Output

NO


Input

5 4
3 2 4 3 5


Output

YES
1 2 3
1 3
1 2 3 4
1 3 4
1 1 2 3 4

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Andrewid the Android is a galaxy-famous detective. He is now chasing a criminal hiding on the planet Oxa-5, the planet almost fully covered with water.

The only dry land there is an archipelago of *n* narrow islands located in a row. For more comfort let's represent them as non-intersecting segments on a straight line: island *i* has coordinates [*l**i*,<=*r**i*], besides, *r**i*<=&lt;<=*l**i*<=+<=1 for 1<=≤<=*i*<=≤<=*n*<=-<=1.

To reach the goal, Andrewid needs to place a bridge between each pair of adjacent islands. A bridge of length *a* can be placed between the *i*-th and the (*i*<=+<=1)-th islads, if there are such coordinates of *x* and *y*, that *l**i*<=≤<=*x*<=≤<=*r**i*, *l**i*<=+<=1<=≤<=*y*<=≤<=*r**i*<=+<=1 and *y*<=-<=*x*<==<=*a*. 

The detective was supplied with *m* bridges, each bridge can be used at most once. Help him determine whether the bridges he got are enough to connect each pair of adjacent islands.

Input Specification:
The first line contains integers *n* (2<=≤<=*n*<=≤<=2·105) and *m* (1<=≤<=*m*<=≤<=2·105) — the number of islands and bridges.

Next *n* lines each contain two integers *l**i* and *r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=1018) — the coordinates of the island endpoints.

The last line contains *m* integer numbers *a*1,<=*a*2,<=...,<=*a**m* (1<=≤<=*a**i*<=≤<=1018) — the lengths of the bridges that Andrewid got.

Output Specification:
If it is impossible to place a bridge between each pair of adjacent islands in the required manner, print on a single line "No" (without the quotes), otherwise print in the first line "Yes" (without the quotes), and in the second line print *n*<=-<=1 numbers *b*1,<=*b*2,<=...,<=*b**n*<=-<=1, which mean that between islands *i* and *i*<=+<=1 there must be used a bridge number *b**i*. 

If there are multiple correct answers, print any of them. Note that in this problem it is necessary to print "Yes" and "No" in correct case.

Demo Input:
['4 4\n1 4\n7 8\n9 10\n12 14\n4 5 3 8\n', '2 2\n11 14\n17 18\n2 9\n', '2 1\n1 1\n1000000000000000000 1000000000000000000\n999999999999999999\n']

Demo Output:
['Yes\n2 3 1 \n', 'No\n', 'Yes\n1 \n']

Note:
In the first sample test you can, for example, place the second bridge between points 3 and 8, place the third bridge between points 7 and 10 and place the first bridge between points 10 and 14.

In the second sample test the first bridge is too short and the second bridge is too long, so the solution doesn't exist.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem, we will deal with binary strings. Each character of a binary string is either a 0 or a 1. We will also deal with substrings; recall that a substring is a contiguous subsequence of a string. We denote the substring of string $s$ starting from the $l$-th character and ending with the $r$-th character as $s[l \dots r]$. The characters of each string are numbered from $1$.

We can perform several operations on the strings we consider. Each operation is to choose a substring of our string and replace it with another string. There are two possible types of operations: replace 011 with 110, or replace 110 with 011. For example, if we apply exactly one operation to the string 110011110, it can be transformed into 011011110, 110110110, or 110011011.

Binary string $a$ is considered reachable from binary string $b$ if there exists a sequence $s_1$, $s_2$, ..., $s_k$ such that $s_1 = a$, $s_k = b$, and for every $i \in [1, k - 1]$, $s_i$ can be transformed into $s_{i + 1}$ using exactly one operation. Note that $k$ can be equal to $1$, i. e., every string is reachable from itself.

You are given a string $t$ and $q$ queries to it. Each query consists of three integers $l_1$, $l_2$ and $len$. To answer each query, you have to determine whether $t[l_1 \dots l_1 + len - 1]$ is reachable from $t[l_2 \dots l_2 + len - 1]$.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of string $t$.

The second line contains one string $t$ ($|t| = n$). Each character of $t$ is either 0 or 1.

The third line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

Then $q$ lines follow, each line represents a query. The $i$-th line contains three integers $l_1$, $l_2$ and $len$ ($1 \le l_1, l_2 \le |t|$, $1 \le len \le |t| - \max(l_1, l_2) + 1$) for the $i$-th query.


-----Output-----

For each query, print either YES if $t[l_1 \dots l_1 + len - 1]$ is reachable from $t[l_2 \dots l_2 + len - 1]$, or NO otherwise. You may print each letter in any register.


-----Example-----
Input
5
11011
3
1 3 3
1 4 2
1 2 3

Output
Yes
Yes
No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ beautiful skyscrapers in New York, the height of the $i$-th one is $h_i$. Today some villains have set on fire first $n - 1$ of them, and now the only safety building is $n$-th skyscraper.

Let's call a jump from $i$-th skyscraper to $j$-th ($i < j$) discrete, if all skyscrapers between are strictly lower or higher than both of them. Formally, jump is discrete, if $i < j$ and one of the following conditions satisfied:   $i + 1 = j$  $\max(h_{i + 1}, \ldots, h_{j - 1}) < \min(h_i, h_j)$  $\max(h_i, h_j) < \min(h_{i + 1}, \ldots, h_{j - 1})$. 

At the moment, Vasya is staying on the first skyscraper and wants to live a little longer, so his goal is to reach $n$-th skyscraper with minimal count of discrete jumps. Help him with calcualting this number.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$) — total amount of skyscrapers.

The second line contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$) — heights of skyscrapers.


-----Output-----

Print single number $k$ — minimal amount of discrete jumps. We can show that an answer always exists.


-----Examples-----
Input
5
1 3 1 4 5

Output
3
Input
4
4 2 2 4

Output
1
Input
2
1 1

Output
1
Input
5
100 1 100 1 100

Output
2


-----Note-----

In the first testcase, Vasya can jump in the following way: $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$.

In the second and third testcases, we can reach last skyscraper in one jump.

Sequence of jumps in the fourth testcase: $1 \rightarrow 3 \rightarrow 5$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Galya is playing one-dimensional Sea Battle on a 1<=×<=*n* grid. In this game *a* ships are placed on the grid. Each of the ships consists of *b* consecutive cells. No cell can be part of two ships, however, the ships can touch each other.

Galya doesn't know the ships location. She can shoot to some cells and after each shot she is told if that cell was a part of some ship (this case is called "hit") or not (this case is called "miss").

Galya has already made *k* shots, all of them were misses.

Your task is to calculate the minimum number of cells such that if Galya shoot at all of them, she would hit at least one ship.

It is guaranteed that there is at least one valid ships placement.

Input Specification:
The first line contains four positive integers *n*, *a*, *b*, *k* (1<=≤<=*n*<=≤<=2·105, 1<=≤<=*a*,<=*b*<=≤<=*n*, 0<=≤<=*k*<=≤<=*n*<=-<=1) — the length of the grid, the number of ships on the grid, the length of each ship and the number of shots Galya has already made.

The second line contains a string of length *n*, consisting of zeros and ones. If the *i*-th character is one, Galya has already made a shot to this cell. Otherwise, she hasn't. It is guaranteed that there are exactly *k* ones in this string.

Output Specification:
In the first line print the minimum number of cells such that if Galya shoot at all of them, she would hit at least one ship.

In the second line print the cells Galya should shoot at.

Each cell should be printed exactly once. You can print the cells in arbitrary order. The cells are numbered from 1 to *n*, starting from the left.

If there are multiple answers, you can print any of them.

Demo Input:
['5 1 2 1\n00100\n', '13 3 2 3\n1000000010001\n']

Demo Output:
['2\n4 2\n', '2\n7 11\n']

Note:
There is one ship in the first sample. It can be either to the left or to the right from the shot Galya has already made (the "1" character). So, it is necessary to make two shots: one at the left part, and one at the right part.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vanya wants to pass n exams and get the academic scholarship. He will get the scholarship if the average grade mark for all the exams is at least avg. The exam grade cannot exceed r. Vanya has passed the exams and got grade a_{i} for the i-th exam. To increase the grade for the i-th exam by 1 point, Vanya must write b_{i} essays. He can raise the exam grade multiple times.

What is the minimum number of essays that Vanya needs to write to get scholarship?


-----Input-----

The first line contains three integers n, r, avg (1 ≤ n ≤ 10^5, 1 ≤ r ≤ 10^9, 1 ≤ avg ≤ min(r, 10^6)) — the number of exams, the maximum grade and the required grade point average, respectively.

Each of the following n lines contains space-separated integers a_{i} and b_{i} (1 ≤ a_{i} ≤ r, 1 ≤ b_{i} ≤ 10^6).


-----Output-----

In the first line print the minimum number of essays.


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

Output
4

Input
2 5 4
5 2
5 2

Output
0



-----Note-----

In the first sample Vanya can write 2 essays for the 3rd exam to raise his grade by 2 points and 2 essays for the 4th exam to raise his grade by 1 point.

In the second sample, Vanya doesn't need to write any essays as his general point average already is above average.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When you want to get the square of a binomial of two variables x and y, you will have:

`$(x+y)^2 = x^2 + 2xy + y ^2$`

And the cube:

`$(x+y)^3 = x^3 + 3x^2y + 3xy^2 +y^3$`

It is known from many centuries ago that for an exponent n, the result of a binomial x + y raised to the n-th power is:

Or using the sumation notation:

Each coefficient of a term has the following value:

Each coefficient value coincides with the amount of combinations without replacements of a set of n elements using only k different ones of that set.

Let's see the total sum of the coefficients of the different powers for the binomial:

`$(x+y)^0(1)$`

`$(x+y)^1 = x+y(2)$`

`$(x+y)^2 = x^2 + 2xy + y ^2(4)$`

`$(x+y)^3 = x^3 + 3x^2y + 3xy^2 +y^3(8)$`

We need a function that may generate an array with the values of all the coefficients sums from 0 to the value of n included and has the addition of all the sum values as last element.

We add some examples below:
``` 
f(0) = [1, 1]
f(1) = [1, 2, 3]
f(2) = [1, 2, 4, 7]
f(3) = [1, 2, 4, 8, 15]
``` 

Features of the test
``` 
Low Performance Tests
Number of tests = 50
9 < n < 101

High Performance Tests
Number of Tests = 50
99 < n < 5001
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Eugeny and Play List

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Eugeny loves listening to music. He has *n* songs in his play list. We know that song number *i* has the duration of *t**i* minutes. Eugeny listens to each song, perhaps more than once. He listens to song number *i* *c**i* times. Eugeny's play list is organized as follows: first song number 1 plays *c*1 times, then song number 2 plays *c*2 times, ..., in the end the song number *n* plays *c**n* times.

Eugeny took a piece of paper and wrote out *m* moments of time when he liked a song. Now for each such moment he wants to know the number of the song that played at that moment. The moment *x* means that Eugeny wants to know which song was playing during the *x*-th minute of his listening to the play list.

Help Eugeny and calculate the required numbers of songs.

Input Specification:
The first line contains two integers *n*, *m* (1<=≤<=*n*,<=*m*<=≤<=105). The next *n* lines contain pairs of integers. The *i*-th line contains integers *c**i*,<=*t**i* (1<=≤<=*c**i*,<=*t**i*<=≤<=109) — the description of the play list. It is guaranteed that the play list's total duration doesn't exceed 109 .

The next line contains *m* positive integers *v*1,<=*v*2,<=...,<=*v**m*, that describe the moments Eugeny has written out. It is guaranteed that there isn't such moment of time *v**i*, when the music doesn't play any longer. It is guaranteed that *v**i*<=&lt;<=*v**i*<=+<=1 (*i*<=&lt;<=*m*).

The moment of time *v**i* means that Eugeny wants to know which song was playing during the *v**i*-th munite from the start of listening to the playlist.

Output Specification:
Print *m* integers — the *i*-th number must equal the number of the song that was playing during the *v**i*-th minute after Eugeny started listening to the play list.

Demo Input:
['1 2\n2 8\n1 16\n', '4 9\n1 2\n2 1\n1 1\n2 2\n1 2 3 4 5 6 7 8 9\n']

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

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Robbers, who attacked the Gerda's cab, are very successful in covering from the kingdom police. To make the goal of catching them even harder, they use their own watches.

First, as they know that kingdom police is bad at math, robbers use the positional numeral system with base 7. Second, they divide one day in *n* hours, and each hour in *m* minutes. Personal watches of each robber are divided in two parts: first of them has the smallest possible number of places that is necessary to display any integer from 0 to *n*<=-<=1, while the second has the smallest possible number of places that is necessary to display any integer from 0 to *m*<=-<=1. Finally, if some value of hours or minutes can be displayed using less number of places in base 7 than this watches have, the required number of zeroes is added at the beginning of notation.

Note that to display number 0 section of the watches is required to have at least one place.

Little robber wants to know the number of moments of time (particular values of hours and minutes), such that all digits displayed on the watches are distinct. Help her calculate this number.

Input Specification:
The first line of the input contains two integers, given in the decimal notation, *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=109) — the number of hours in one day and the number of minutes in one hour, respectively.

Output Specification:
Print one integer in decimal notation — the number of different pairs of hour and minute, such that all digits displayed on the watches are distinct.

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

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

Note:
In the first sample, possible pairs are: (0: 1), (0: 2), (1: 0), (1: 2).

In the second sample, possible pairs are: (02: 1), (03: 1), (04: 1), (05: 1), (06: 1).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kuroni is very angry at the other setters for using him as a theme! As a punishment, he forced them to solve the following problem:

You have an array $a$ consisting of $n$ positive integers. An operation consists of choosing an element and either adding $1$ to it or subtracting $1$ from it, such that the element remains positive. We say the array is good if the greatest common divisor of all its elements is not $1$. Find the minimum number of operations needed to make the array good.

Unable to match Kuroni's intellect, the setters failed to solve the problem. Help them escape from Kuroni's punishment!


-----Input-----

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

The second line contains $n$ integers $a_1, a_2, \dots, a_n$. ($1 \le a_i \le 10^{12}$)  — the elements of the array.


-----Output-----

Print a single integer  — the minimum number of operations required to make the array good.


-----Examples-----
Input
3
6 2 4

Output
0

Input
5
9 8 7 3 1

Output
4



-----Note-----

In the first example, the first array is already good, since the greatest common divisor of all the elements is $2$.

In the second example, we may apply the following operations:

  Add $1$ to the second element, making it equal to $9$.  Subtract $1$ from the third element, making it equal to $6$.  Add $1$ to the fifth element, making it equal to $2$.  Add $1$ to the fifth element again, making it equal to $3$. 

The greatest common divisor of all elements will then be equal to $3$, so the array will be good. It can be shown that no sequence of three or less operations can make the array good.

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