vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Ralph And His Tour in Binary Country

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ralph is in the Binary Country. The Binary Country consists of *n* cities and (*n*<=-<=1) bidirectional roads connecting the cities. The roads are numbered from 1 to (*n*<=-<=1), the *i*-th road connects the city labeled  (here ⌊ *x*⌋ denotes the *x* rounded down to the nearest integer) and the city labeled (*i*<=+<=1), and the length of the *i*-th road is *L**i*.

Now Ralph gives you *m* queries. In each query he tells you some city *A**i* and an integer *H**i*. He wants to make some tours starting from this city. He can choose any city in the Binary Country (including *A**i*) as the terminal city for a tour. He gains happiness (*H**i*<=-<=*L*) during a tour, where *L* is the distance between the city *A**i* and the terminal city.

Ralph is interested in tours from *A**i* in which he can gain positive happiness. For each query, compute the sum of happiness gains for all such tours.

Ralph will never take the same tour twice or more (in one query), he will never pass the same city twice or more in one tour.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*<=≤<=106, 1<=≤<=*m*<=≤<=105).

(*n*<=-<=1) lines follow, each line contains one integer *L**i* (1<=≤<=*L**i*<=≤<=105), which denotes the length of the *i*-th road.

*m* lines follow, each line contains two integers *A**i* and *H**i* (1<=≤<=*A**i*<=≤<=*n*, 0<=≤<=*H**i*<=≤<=107).

Output Specification:
Print *m* lines, on the *i*-th line print one integer — the answer for the *i*-th query.

Demo Input:
['2 2\n5\n1 8\n2 4\n', '6 4\n2\n1\n1\n3\n2\n2 4\n1 3\n3 2\n1 7\n']

Demo Output:
['11\n4\n', '11\n6\n3\n28\n']

Note:
Here is the explanation for the second sample.

Ralph's first query is to start tours from city 2 and *H*<sub class="lower-index">*i*</sub> equals to 4. Here are the options:
 -  He can choose city 5 as his terminal city. Since the distance between city 5 and city 2 is 3, he can gain happiness 4 - 3 = 1. -  He can choose city 4 as his terminal city and gain happiness 3. -  He can choose city 1 as his terminal city and gain happiness 2. -  He can choose city 3 as his terminal city and gain happiness 1. -  Note that Ralph can choose city 2 as his terminal city and gain happiness 4. -  Ralph won't choose city 6 as his terminal city because the distance between city 6 and city 2 is 5, which leads to negative happiness for Ralph. 
So the answer for the first query is 1 + 3 + 2 + 1 + 4 = 11.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary string $s$ (recall that a string is binary if each character is either $0$ or $1$).

Let $f(t)$ be the decimal representation of integer $t$ written in binary form (possibly with leading zeroes). For example $f(011) = 3, f(00101) = 5, f(00001) = 1, f(10) = 2, f(000) = 0$ and $f(000100) = 4$.

The substring $s_{l}, s_{l+1}, \dots , s_{r}$ is good if $r - l + 1 = f(s_l \dots s_r)$.

For example string $s = 1011$ has $5$ good substrings: $s_1 \dots s_1 = 1$, $s_3 \dots s_3 = 1$, $s_4 \dots s_4 = 1$, $s_1 \dots s_2 = 10$ and $s_2 \dots s_4 = 011$. 

Your task is to calculate the number of good substrings of string $s$.

You have to answer $t$ independent queries.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of queries.

The only line of each query contains string $s$ ($1 \le |s| \le 2 \cdot 10^5$), consisting of only digits $0$ and $1$.

It is guaranteed that $\sum\limits_{i=1}^{t} |s_i| \le 2 \cdot 10^5$.


-----Output-----

For each query print one integer — the number of good substrings of string $s$.


-----Example-----
Input
4
0110
0101
00001000
0001000

Output
4
3
4
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Final kata of the series (highly recommended to compute [layers](https://www.codewars.com/kata/progressive-spiral-number-position/) and [branch](https://www.codewars.com/kata/progressive-spiral-number-branch/) first to get a good idea), this is a blatant ripoff of [the one offered on AoC](http://adventofcode.com/2017/day/3).

Given a number, return the Manhattan distance considering the core of the spiral (the `1` cell) as 0 and counting each step up, right, down or left to reach a given cell.

For example, using our beloved 5x5 square:

```
17 16 15 14 13    4 3 2 3 4
18 05 04 03 12    3 2 1 2 3
19 06 01 02 11 => 2 1 0 1 2
20 07 08 09 10    3 2 1 2 3
21 22 23 24 25    4 3 2 3 4
```

And thus your code should behave like this:

```python
distance(1) == 0
distance(5) == 2
distance(25) == 4
distance(30) == 5
distance(50) == 7
```

Just be ready for larger numbers, as usual always positive.

*[Dedicated to [swiftest learner I met in a long while](https://www.codewars.com/users/irbekrm/)]*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alexey, a merry Berland entrant, got sick of the gray reality and he zealously wants to go to university. There are a lot of universities nowadays, so Alexey is getting lost in the diversity — he has not yet decided what profession he wants to get. At school, he had bad grades in all subjects, and it's only thanks to wealthy parents that he was able to obtain the graduation certificate.

The situation is complicated by the fact that each high education institution has the determined amount of voluntary donations, paid by the new students for admission — n_{i} berubleys. He cannot pay more than n_{i}, because then the difference between the paid amount and n_{i} can be regarded as a bribe!

Each rector is wearing the distinctive uniform of his university. Therefore, the uniform's pockets cannot contain coins of denomination more than r_{i}. The rector also does not carry coins of denomination less than l_{i} in his pocket — because if everyone pays him with so small coins, they gather a lot of weight and the pocket tears. Therefore, a donation can be paid only by coins of denomination x berubleys, where l_{i} ≤ x ≤ r_{i} (Berland uses coins of any positive integer denomination). Alexey can use the coins of different denominations and he can use the coins of the same denomination any number of times. When Alexey was first confronted with such orders, he was puzzled because it turned out that not all universities can accept him! Alexey is very afraid of going into the army (even though he had long wanted to get the green uniform, but his dad says that the army bullies will beat his son and he cannot pay to ensure the boy's safety). So, Alexey wants to know for sure which universities he can enter so that he could quickly choose his alma mater.

Thanks to the parents, Alexey is not limited in money and we can assume that he has an unlimited number of coins of each type.

In other words, you are given t requests, each of them contains numbers n_{i}, l_{i}, r_{i}. For each query you need to answer, whether it is possible to gather the sum of exactly n_{i} berubleys using only coins with an integer denomination from l_{i} to r_{i} berubleys. You can use coins of different denominations. Coins of each denomination can be used any number of times.


-----Input-----

The first line contains the number of universities t, (1 ≤ t ≤ 1000) Each of the next t lines contain three space-separated integers: n_{i}, l_{i}, r_{i} (1 ≤ n_{i}, l_{i}, r_{i} ≤ 10^9; l_{i} ≤ r_{i}).


-----Output-----

For each query print on a single line: either "Yes", if Alexey can enter the university, or "No" otherwise.


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

Output
Yes
No



-----Note-----

You can pay the donation to the first university with two coins: one of denomination 2 and one of denomination 3 berubleys. The donation to the second university cannot be paid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A telephone number is a sequence of exactly $11$ digits such that its first digit is 8.

Vasya and Petya are playing a game. Initially they have a string $s$ of length $n$ ($n$ is odd) consisting of digits. Vasya makes the first move, then players alternate turns. In one move the player must choose a character and erase it from the current string. For example, if the current string 1121, after the player's move it may be 112, 111 or 121. The game ends when the length of string $s$ becomes 11. If the resulting string is a telephone number, Vasya wins, otherwise Petya wins.

You have to determine if Vasya has a winning strategy (that is, if Vasya can win the game no matter which characters Petya chooses during his moves).


-----Input-----

The first line contains one integer $n$ ($13 \le n < 10^5$, $n$ is odd) — the length of string $s$.

The second line contains the string $s$ ($|s| = n$) consisting only of decimal digits.


-----Output-----

If Vasya has a strategy that guarantees him victory, print YES.

Otherwise print NO.


-----Examples-----
Input
13
8380011223344

Output
YES

Input
15
807345619350641

Output
NO



-----Note-----

In the first example Vasya needs to erase the second character. Then Petya cannot erase a character from the remaining string 880011223344 so that it does not become a telephone number.

In the second example after Vasya's turn Petya can erase one character character 8. The resulting string can't be a telephone number, because there is no digit 8 at all.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little girl Tanya climbs the stairs inside a multi-storey building. Every time Tanya climbs a stairway, she starts counting steps from $1$ to the number of steps in this stairway. She speaks every number aloud. For example, if she climbs two stairways, the first of which contains $3$ steps, and the second contains $4$ steps, she will pronounce the numbers $1, 2, 3, 1, 2, 3, 4$.

You are given all the numbers pronounced by Tanya. How many stairways did she climb? Also, output the number of steps in each stairway.

The given sequence will be a valid sequence that Tanya could have pronounced when climbing one or more stairways.

Input Specification:
The first line contains $n$ ($1 \le n \le 1000$) — the total number of numbers pronounced by Tanya.

The second line contains integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000$) — all the numbers Tanya pronounced while climbing the stairs, in order from the first to the last pronounced number. Passing a stairway with $x$ steps, she will pronounce the numbers $1, 2, \dots, x$ in that order.

The given sequence will be a valid sequence that Tanya could have pronounced when climbing one or more stairways.

Output Specification:
In the first line, output $t$ — the number of stairways that Tanya climbed. In the second line, output $t$ numbers — the number of steps in each stairway she climbed. Write the numbers in the correct order of passage of the stairways.

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

Demo Output:
['2\n3 4 ', '4\n1 1 1 1 ', '1\n5 ', '3\n2 2 1 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two large companies "Cecsi" and "Poca Pola" are fighting against each other for a long time. In order to overcome their competitor, "Poca Pola" started a super secret project, for which it has total n vacancies in all of their offices. After many tests and interviews n candidates were selected and the only thing left was their employment.

Because all candidates have the same skills, it doesn't matter where each of them will work. That is why the company decided to distribute candidates between workplaces so that the total distance between home and workplace over all candidates is minimal.

It is well known that Earth is round, so it can be described as a circle, and all m cities on Earth can be described as points on this circle. All cities are enumerated from 1 to m so that for each i (1 ≤ i ≤ m - 1) cities with indexes i and i + 1 are neighbors and cities with indexes 1 and m are neighbors as well. People can move only along the circle. The distance between any two cities equals to minimal number of transitions between neighboring cities you have to perform to get from one city to another. In particular, the distance between the city and itself equals 0.

The "Poca Pola" vacancies are located at offices in cities a_1, a_2, …, a_n. The candidates live in cities b_1, b_2, …, b_n. It is possible that some vacancies are located in the same cities and some candidates live in the same cities. 

The "Poca Pola" managers are too busy with super secret project, so you were asked to help "Poca Pola" to distribute candidates between workplaces, so that the sum of the distance between home and workplace over all candidates is minimum possible.

Input

The first line contains two integers m and n (1 ≤ m ≤ 10^9, 1 ≤ n ≤ 200 000) — the number of cities on Earth and the number of vacancies.

The second line contains n integers a_1, a_2, a_3, …, a_n (1 ≤ a_i ≤ m) — the cities where vacancies are located.

The third line contains n integers b_1, b_2, b_3, …, b_n (1 ≤ b_i ≤ m) — the cities where the candidates live.

Output

The first line should contain the minimum total distance between home and workplace over all candidates.

The second line should contain n different integers from 1 to n. The i-th of them should be the index of candidate that should work at i-th workplace.

Examples

Input


10 3
1 5 5
10 4 6


Output


3
1 2 3 

Input


10 3
1 4 8
8 3 6


Output


4
2 3 1 

Note

In the first example, the distance between each candidate and his workplace equals to 1 (from 1 to 10, from 4 to 5 and from 6 to 5).

In the second example:

  * The second candidate works at first workplace, the distance between cities 3 and 1 equals to 2. 
  * The third candidate works at second workplace, the distance between cities 6 and 4 equals to 2. 
  * The first candidate works at third workplace, the distance between cities 8 and 8 equals to 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You drop a ball from a given height. After each bounce, the ball returns to some fixed proportion of its previous height. If the ball bounces to height 1 or less, we consider it to have stopped bouncing. Return the number of bounces it takes for the ball to stop moving.

```
bouncingBall(initialHeight, bouncingProportion)

boucingBall(4, 0.5)
After first bounce, ball bounces to height 2
After second bounce, ball bounces to height 1
Therefore answer is 2 bounces

boucingBall(30, 0.3)
After first bounce, ball bounces to height 9
After second bounce, ball bounces to height 2.7
After third bounce, ball bounces to height 0.81
Therefore answer is 3 bounces


```

Initial height is an integer in range [2,1000]

Bouncing Proportion is a decimal in range [0, 1)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have n dices each one having s sides numbered from 1 to s.
How many outcomes add up to a specified number k?

For example if we roll four normal six-sided dices we
have four outcomes that add up to 5. 

(1, 1, 1, 2)
(1, 1, 2, 1)
(1, 2, 1, 1)
(2, 1, 1, 1)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ students in a school class, the rating of the $i$-th student on Codehorses is $a_i$. You have to form a team consisting of $k$ students ($1 \le k \le n$) such that the ratings of all team members are distinct.

If it is impossible to form a suitable team, print "NO" (without quotes). Otherwise print "YES", and then print $k$ distinct numbers which should be the indices of students in the team you form. If there are multiple answers, print any of them.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 100$) — the number of students and the size of the team you have to form.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$), where $a_i$ is the rating of $i$-th student.


-----Output-----

If it is impossible to form a suitable team, print "NO" (without quotes). Otherwise print "YES", and then print $k$ distinct integers from $1$ to $n$ which should be the indices of students in the team you form. All the ratings of the students in the team should be distinct. You may print the indices in any order. If there are multiple answers, print any of them.

Assume that the students are numbered from $1$ to $n$.


-----Examples-----
Input
5 3
15 13 15 15 12

Output
YES
1 2 5 

Input
5 4
15 13 15 15 12

Output
NO

Input
4 4
20 10 40 30

Output
YES
1 2 3 4 



-----Note-----

All possible answers for the first example:   {1 2 5}  {2 3 5}  {2 4 5} 

Note that the order does not matter.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Send the Fool Further! (easy)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Heidi's friend Jenny is asking Heidi to deliver an important letter to one of their common friends. Since Jenny is Irish, Heidi thinks that this might be a prank. More precisely, she suspects that the message she is asked to deliver states: "Send the fool further!", and upon reading it the recipient will ask Heidi to deliver the same message to yet another friend (that the recipient has in common with Heidi), and so on.

Heidi believes that her friends want to avoid awkward situations, so she will not be made to visit the same person (including Jenny) twice. She also knows how much it costs to travel between any two of her friends who know each other. She wants to know: what is the maximal amount of money she will waste on travel if it really is a prank?

Heidi's *n* friends are labeled 0 through *n*<=-<=1, and their network of connections forms a tree. In other words, every two of her friends *a*, *b* know each other, possibly indirectly (there is a sequence of friends starting from *a* and ending on *b* and such that each two consecutive friends in the sequence know each other directly), and there are exactly *n*<=-<=1 pairs of friends who know each other directly.

Jenny is given the number 0.

Input Specification:
The first line of the input contains the number of friends *n* (3<=≤<=*n*<=≤<=100). The next *n*<=-<=1 lines each contain three space-separated integers *u*, *v* and *c* (0<=≤<=*u*,<=*v*<=≤<=*n*<=-<=1, 1<=≤<=*c*<=≤<=104), meaning that *u* and *v* are friends (know each other directly) and the cost for travelling between *u* and *v* is *c*.

It is guaranteed that the social network of the input forms a tree.

Output Specification:
Output a single integer – the maximum sum of costs.

Demo Input:
['4\n0 1 4\n0 2 2\n2 3 3\n', '6\n1 2 3\n0 2 100\n1 4 2\n0 3 7\n3 5 10\n', '11\n1 0 1664\n2 0 881\n3 2 4670\n4 2 1555\n5 1 1870\n6 2 1265\n7 2 288\n8 7 2266\n9 2 1536\n10 6 3378\n']

Demo Output:
['5\n', '105\n', '5551\n']

Note:
In the second example, the worst-case scenario goes like this: Jenny sends Heidi to the friend labeled by number 2 (incurring a cost of 100), then friend 2 sends her to friend 1 (costing Heidi 3), and finally friend 1 relays her to friend 4 (incurring an additional cost of 2).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
All our characters have hobbies. The same is true for Fedor. He enjoys shopping in the neighboring supermarket. 

The goods in the supermarket have unique integer ids. Also, for every integer there is a product with id equal to this integer. Fedor has n discount coupons, the i-th of them can be used with products with ids ranging from li to ri, inclusive. Today Fedor wants to take exactly k coupons with him.

Fedor wants to choose the k coupons in such a way that the number of such products x that all coupons can be used with this product x is as large as possible (for better understanding, see examples). Fedor wants to save his time as well, so he asks you to choose coupons for him. Help Fedor!

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 3·105) — the number of coupons Fedor has, and the number of coupons he wants to choose.

Each of the next n lines contains two integers li and ri ( - 109 ≤ li ≤ ri ≤ 109) — the description of the i-th coupon. The coupons can be equal.

Output

In the first line print single integer — the maximum number of products with which all the chosen coupons can be used. The products with which at least one coupon cannot be used shouldn't be counted.

In the second line print k distinct integers p1, p2, ..., pk (1 ≤ pi ≤ n) — the ids of the coupons which Fedor should choose.

If there are multiple answers, print any of them.

Examples

Input

4 2
1 100
40 70
120 130
125 180


Output

31
1 2 


Input

3 2
1 12
15 20
25 30


Output

0
1 2 


Input

5 2
1 10
5 15
14 50
30 70
99 100


Output

21
3 4 

Note

In the first example if we take the first two coupons then all the products with ids in range [40, 70] can be bought with both coupons. There are 31 products in total.

In the second example, no product can be bought with two coupons, that is why the answer is 0. Fedor can choose any two coupons in this example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Magic Powder - 2

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The term of this problem is the same as the previous one, the only exception — increased restrictions.

Input Specification:
The first line contains two positive integers *n* and *k* (1<=≤<=*n*<=≤<=100<=000,<=1<=≤<=*k*<=≤<=109) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109), where the *i*-th number is equal to the number of grams of the *i*-th ingredient, needed to bake one cookie.

The third line contains the sequence *b*1,<=*b*2,<=...,<=*b**n* (1<=≤<=*b**i*<=≤<=109), where the *i*-th number is equal to the number of grams of the *i*-th ingredient, which Apollinaria has.

Output Specification:
Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.

Demo Input:
['1 1000000000\n1\n1000000000\n', '10 1\n1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000\n1 1 1 1 1 1 1 1 1 1\n', '3 1\n2 1 4\n11 3 16\n', '4 3\n4 3 5 6\n11 12 14 20\n']

Demo Output:
['2000000000\n', '0\n', '4\n', '3\n']

Note:
none

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