vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Vasya and Socks

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya has *n* pairs of socks. In the morning of each day Vasya has to put on a pair of socks before he goes to school. When he comes home in the evening, Vasya takes off the used socks and throws them away. Every *m*-th day (at days with numbers *m*,<=2*m*,<=3*m*,<=...) mom buys a pair of socks to Vasya. She does it late in the evening, so that Vasya cannot put on a new pair of socks before the next day. How many consecutive days pass until Vasya runs out of socks?

Input Specification:
The single line contains two integers *n* and *m* (1<=≤<=*n*<=≤<=100; 2<=≤<=*m*<=≤<=100), separated by a space.

Output Specification:
Print a single integer — the answer to the problem.

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

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

Note:
In the first sample Vasya spends the first two days wearing the socks that he had initially. Then on day three he puts on the socks that were bought on day two.

In the second sample Vasya spends the first nine days wearing the socks that he had initially. Then he spends three days wearing the socks that were bought on the third, sixth and ninth days. Than he spends another day wearing the socks that were bought on the twelfth day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Phoenix has n blocks of height h_1, h_2, ..., h_n, and all h_i don't exceed some value x. He plans to stack all n blocks into m separate towers. The height of a tower is simply the sum of the heights of its blocks. For the towers to look beautiful, no two towers may have a height difference of strictly more than x. 

Please help Phoenix build m towers that look beautiful. Each tower must have at least one block and all blocks must be used.

Input

The input consists of multiple test cases. The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains three integers n, m, and x (1 ≤ m ≤ n ≤ 10^5; 1 ≤ x ≤ 10^4) — the number of blocks, the number of towers to build, and the maximum acceptable height difference of any two towers, respectively. 

The second line of each test case contains n space-separated integers (1 ≤ h_i ≤ x) — the heights of the blocks. 

It is guaranteed that the sum of n over all the test cases will not exceed 10^5.

Output

For each test case, if Phoenix cannot build m towers that look beautiful, print NO. Otherwise, print YES, followed by n integers y_1, y_2, ..., y_n, where y_i (1 ≤ y_i ≤ m) is the index of the tower that the i-th block is placed in.

If there are multiple solutions, print any of them.

Example

Input


2
5 2 3
1 2 3 1 2
4 3 3
1 1 2 3


Output


YES
1 1 1 2 2
YES
1 2 2 3

Note

In the first test case, the first tower has height 1+2+3=6 and the second tower has height 1+2=3. Their difference is 6-3=3 which doesn't exceed x=3, so the towers are beautiful.

In the second test case, the first tower has height 1, the second tower has height 1+2=3, and the third tower has height 3. The maximum height difference of any two towers is 3-1=2 which doesn't exceed x=3, so the towers are beautiful.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In some other world, today is Christmas Eve.

There are N trees planted in Mr. Takaha's garden. The height of the i-th tree (1 \leq i \leq N) is h_i meters.

He decides to choose K trees from these trees and decorate them with electric lights. To make the scenery more beautiful, the heights of the decorated trees should be as close to each other as possible.

More specifically, let the height of the tallest decorated tree be h_{max} meters, and the height of the shortest decorated tree be h_{min} meters. The smaller the value h_{max} - h_{min} is, the better. What is the minimum possible value of h_{max} - h_{min}?

Constraints

* 2 \leq K < N \leq 10^5
* 1 \leq h_i \leq 10^9
* h_i is an integer.

Input

Input is given from Standard Input in the following format:


N K
h_1
h_2
:
h_N


Output

Print the minimum possible value of h_{max} - h_{min}.

Examples

Input

5 3
10
15
11
14
12


Output

2


Input

5 3
5
7
5
7
7


Output

0

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

Time Limit: 5 seconds

Memory Limit: 256 megabytes

Problem Description:
Professor Phunsuk Wangdu has performed some experiments on rays. The setup for *n* rays is as follows.

There is a rectangular box having exactly *n* holes on the opposite faces. All rays enter from the holes of the first side and exit from the holes of the other side of the box. Exactly one ray can enter or exit from each hole. The holes are in a straight line.

Professor Wangdu is showing his experiment to his students. He shows that there are cases, when all the rays are intersected by every other ray. A curious student asked the professor: "Sir, there are some groups of rays such that all rays in that group intersect every other ray in that group. Can we determine the number of rays in the largest of such groups?".

Professor Wangdu now is in trouble and knowing your intellect he asks you to help him.

Input Specification:
The first line contains *n* (1<=≤<=*n*<=≤<=106), the number of rays. The second line contains *n* distinct integers. The *i*-th integer *x**i* (1<=≤<=*x**i*<=≤<=*n*) shows that the *x**i*-th ray enters from the *i*-th hole. Similarly, third line contains *n* distinct integers. The *i*-th integer *y**i* (1<=≤<=*y**i*<=≤<=*n*) shows that the *y**i*-th ray exits from the *i*-th hole. All rays are numbered from 1 to *n*.

Output Specification:
Output contains the only integer which is the number of rays in the largest group of rays all of which intersect each other.

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

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

Note:
For the first test case, the figure is shown above. The output of the first test case is 3, since the rays number 1, 4 and 3 are the ones which are intersected by each other one i.e. 1 is intersected by 4 and 3, 3 is intersected by 4 and 1, and 4 is intersected by 1 and 3. Hence every ray in this group is intersected by each other one. There does not exist any group containing more than 3 rays satisfying the above-mentioned constraint.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Moscow is hosting a major international conference, which is attended by n scientists from different countries. Each of the scientists knows exactly one language. For convenience, we enumerate all languages of the world with integers from 1 to 10^9.

In the evening after the conference, all n scientists decided to go to the cinema. There are m movies in the cinema they came to. Each of the movies is characterized by two distinct numbers — the index of audio language and the index of subtitles language. The scientist, who came to the movie, will be very pleased if he knows the audio language of the movie, will be almost satisfied if he knows the language of subtitles and will be not satisfied if he does not know neither one nor the other (note that the audio language and the subtitles language for each movie are always different). 

Scientists decided to go together to the same movie. You have to help them choose the movie, such that the number of very pleased scientists is maximum possible. If there are several such movies, select among them one that will maximize the number of almost satisfied scientists.


-----Input-----

The first line of the input contains a positive integer n (1 ≤ n ≤ 200 000) — the number of scientists.

The second line contains n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is the index of a language, which the i-th scientist knows.

The third line contains a positive integer m (1 ≤ m ≤ 200 000) — the number of movies in the cinema. 

The fourth line contains m positive integers b_1, b_2, ..., b_{m} (1 ≤ b_{j} ≤ 10^9), where b_{j} is the index of the audio language of the j-th movie.

The fifth line contains m positive integers c_1, c_2, ..., c_{m} (1 ≤ c_{j} ≤ 10^9), where c_{j} is the index of subtitles language of the j-th movie.

It is guaranteed that audio languages and subtitles language are different for each movie, that is b_{j} ≠ c_{j}. 


-----Output-----

Print the single integer — the index of a movie to which scientists should go. After viewing this movie the number of very pleased scientists should be maximum possible. If in the cinema there are several such movies, you need to choose among them one, after viewing which there will be the maximum possible number of almost satisfied scientists. 

If there are several possible answers print any of them.


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

Output
2

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

Output
1



-----Note-----

In the first sample, scientists must go to the movie with the index 2, as in such case the 1-th and the 3-rd scientists will be very pleased and the 2-nd scientist will be almost satisfied.

In the second test case scientists can go either to the movie with the index 1 or the index 3. After viewing any of these movies exactly two scientists will be very pleased and all the others will be not satisfied.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice bought a Congo Prime Video subscription and was watching a documentary on the archaeological findings from Factor's Island on Loch Katrine in Scotland. The archaeologists found a book whose age and origin are unknown. Perhaps Alice can make some sense of it?

The book contains a single string of characters "a", "b" and "c". It has been pointed out that no two consecutive characters are the same. It has also been conjectured that the string contains an unusually long subsequence that reads the same from both sides. 

Help Alice verify this by finding such subsequence that contains at least half of the characters of the original string, rounded down. Note that you don't have to maximise the length of it.

A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero or all) characters.

Input

The input consists of a single string s (2 ≤ |s| ≤ 10^6). The string s consists only of characters "a", "b", "c". It is guaranteed that no two consecutive characters are equal.

Output

Output a palindrome t that is a subsequence of s and |t| ≥ ⌊ (|s|)/(2) ⌋.

If there are multiple solutions, you may print any of them. You don't have to maximise the length of t.

If there are no solutions, output a string "IMPOSSIBLE" (quotes for clarity).

Examples

Input


cacbac


Output


aba


Input


abc


Output


a


Input


cbacacacbcbababacbcb


Output


cbaaacbcaaabc

Note

In the first example, other valid answers include "cacac", "caac", "aca" and "ccc". 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nikolay has a lemons, b apples and c pears. He decided to cook a compote. According to the recipe the fruits should be in the ratio 1: 2: 4. It means that for each lemon in the compote should be exactly 2 apples and exactly 4 pears. You can't crumble up, break up or cut these fruits into pieces. These fruits — lemons, apples and pears — should be put in the compote as whole fruits.

Your task is to determine the maximum total number of lemons, apples and pears from which Nikolay can cook the compote. It is possible that Nikolay can't use any fruits, in this case print 0. 


-----Input-----

The first line contains the positive integer a (1 ≤ a ≤ 1000) — the number of lemons Nikolay has. 

The second line contains the positive integer b (1 ≤ b ≤ 1000) — the number of apples Nikolay has. 

The third line contains the positive integer c (1 ≤ c ≤ 1000) — the number of pears Nikolay has.


-----Output-----

Print the maximum total number of lemons, apples and pears from which Nikolay can cook the compote.


-----Examples-----
Input
2
5
7

Output
7

Input
4
7
13

Output
21

Input
2
3
2

Output
0



-----Note-----

In the first example Nikolay can use 1 lemon, 2 apples and 4 pears, so the answer is 1 + 2 + 4 = 7.

In the second example Nikolay can use 3 lemons, 6 apples and 12 pears, so the answer is 3 + 6 + 12 = 21.

In the third example Nikolay don't have enough pears to cook any compote, so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a binary string of length $n$ (i. e. a string consisting of $n$ characters '0' and '1').

In one move you can swap two adjacent characters of the string. What is the lexicographically minimum possible string you can obtain from the given one if you can perform no more than $k$ moves? It is possible that you do not perform any moves at all.

Note that you can swap the same pair of adjacent characters with indices $i$ and $i+1$ arbitrary (possibly, zero) number of times. Each such swap is considered a separate move.

You have to answer $q$ independent test cases.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 10^4$) — the number of test cases.

The first line of the test case contains two integers $n$ and $k$ ($1 \le n \le 10^6, 1 \le k \le n^2$) — the length of the string and the number of moves you can perform.

The second line of the test case contains one string consisting of $n$ characters '0' and '1'.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$ ($\sum n \le 10^6$).


-----Output-----

For each test case, print the answer on it: the lexicographically minimum possible string of length $n$ you can obtain from the given one if you can perform no more than $k$ moves.


-----Example-----
Input
3
8 5
11011010
7 9
1111100
7 11
1111100

Output
01011110
0101111
0011111



-----Note-----

In the first example, you can change the string as follows: $1\underline{10}11010 \rightarrow \underline{10}111010 \rightarrow 0111\underline{10}10 \rightarrow 011\underline{10}110 \rightarrow 01\underline{10}1110 \rightarrow 01011110$. 

In the third example, there are enough operations to make the string sorted.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A monster is chasing after Rick and Morty on another planet. They're so frightened that sometimes they scream. More accurately, Rick screams at times *b*,<=*b*<=+<=*a*,<=*b*<=+<=2*a*,<=*b*<=+<=3*a*,<=... and Morty screams at times *d*,<=*d*<=+<=*c*,<=*d*<=+<=2*c*,<=*d*<=+<=3*c*,<=.... 

The Monster will catch them if at any point they scream at the same time, so it wants to know when it will catch them (the first time they scream at the same time) or that they will never scream at the same time.

Input Specification:
The first line of input contains two integers *a* and *b* (1<=≤<=*a*,<=*b*<=≤<=100). 

The second line contains two integers *c* and *d* (1<=≤<=*c*,<=*d*<=≤<=100).

Output Specification:
Print the first time Rick and Morty will scream at the same time, or <=-<=1 if they will never scream at the same time.

Demo Input:
['20 2\n9 19\n', '2 1\n16 12\n']

Demo Output:
['82\n', '-1\n']

Note:
In the first sample testcase, Rick's 5th scream and Morty's 8th time are at time 82. 

In the second sample testcase, all Rick's screams will be at odd times and Morty's will be at even times, so they will never scream at the same time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The aliens living in outer space are very advanced in technology, 
intelligence and everything, except one, and that is Cooking. 
Each year they spend millions of dollars in research, to crack famous recipes prepared by humans.

Recently they came to know about Khana-Academy, 
a non-profit organization streaming free cooking lesson videos on earth. 
There are N recipes, 
numbered 1 to N, and the video of the i^{th} recipe is live in the time interval [S_{i}, E_{i}]. 
An alien can visit earth but can not survive for more than just a small moment (earth is so advanced in pollution). 
An alien visits the earth at an integer time t and instantly downloads the complete video of all the lessons 
that are live at that moment of time t and leaves earth immediately. 
You are given the visiting times of a small group of K aliens. 
Find the number of different recipes aliens can learn by watching the downloaded videos. 
Not just one group of aliens, there are Q such groups, 
so you have to find the answer for each of these Q groups.

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

The first line has an integer N. 
Each of the following N lines has two integers S_{i} E_{i}. 
The next line has an integer Q, the number of groups. 
Each of the following Q lines has information of a group of aliens. 
The first integer is K, the number of aliens in that group, followed by K integers in the same line, 
the integer visiting times t of the aliens.

1 ≤ N ≤ 100000 (10^{5})

1 ≤ Q ≤ 5000 (5 · 10^{3})

1 ≤ K ≤ 20

1 ≤ S_{i}, E_{i}, t ≤ 1000000000 (10^{9})

S_{i} < E_{i}

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

For each of the Q groups, output the number of different recipes that group of aliens can learn by watching the downloaded videos.

------ Example ------ 

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

Output:
3
4
2

Explanation:

Given videos of 4 recipes in the following closed intervals.

1. [ 1 , 4 ]

2. [ 3 , 10 ]

3. [ 2 , 6 ]

4. [ 5 , 8 ]

In the first query, only one alien arrives at t = 5 and can download 3 recipes 2, 3, 4.

In the second query, two aliens arrive at t = 2 and 6. They can learn all the 4 recipes.

In the third query, three aliens arrive at t = 1, 10 and 9. They can learn only two recipes, 1 and 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Infinity has a string S consisting of digits from 1 to 9. Each time the date changes, this string changes as follows:
 - Each occurrence of 2 in S is replaced with 22. Similarly, each 3 becomes 333, 4 becomes 4444, 5 becomes 55555, 6 becomes 666666, 7 becomes 7777777, 8 becomes 88888888 and 9 becomes 999999999. 1 remains as 1.
For example, if S is 1324, it becomes 1333224444 the next day, and it becomes 133333333322224444444444444444 the day after next.
You are interested in what the string looks like after 5 \times 10^{15} days. What is the K-th character from the left in the string after 5 \times 10^{15} days?

-----Constraints-----
 - S is a string of length between 1 and 100 (inclusive).
 - K is an integer between 1 and 10^{18} (inclusive).
 - The length of the string after 5 \times 10^{15} days is at least K.

-----Input-----
Input is given from Standard Input in the following format:
S
K

-----Output-----
Print the K-th character from the left in Mr. Infinity's string after 5 \times 10^{15} days.

-----Sample Input-----
1214
4

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

The string S changes as follows:  
 - Now: 1214
 - After one day: 12214444
 - After two days: 1222214444444444444444
 - After three days: 12222222214444444444444444444444444444444444444444444444444444444444444444
The first five characters in the string after 5 \times 10^{15} days is 12222. As K=4, we should print the fourth character, 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 You are given an array of integers `a` and a non-negative number of operations `k`, applied to the array. Each operation consists of two parts:
```
find the maximum element value of the array;
replace each element a[i] with (maximum element value - a[i]).```
How will the array look like after `k` such operations?

# Example

 For `a = [-4, 0, -1, 0]` and `k = 2`, the output should be `[0, 4, 3, 4]`.
 ```
 initial array: [-4, 0, -1, 0]
 1st operation: 
 find the maximum value --> 0
 replace each element:  --> [(0 - -4), (0 - 0), (0 - -1), (0 - 0)]
                        --> [4, 0, 1, 0]
 2nd operation: 
 find the maximum value --> 4
 replace each element:  --> [(4 - 4), (4 - 0), (4 - 1), (4 - 0)]
                        --> [0, 4, 3, 4]
 
 ```
 For `a = [0, -1, 0, 0, -1, -1, -1, -1, 1, -1]` and `k = 1`, 
 
 the output should be `[1, 2, 1, 1, 2, 2, 2, 2, 0, 2]`.
 ```
 initial array: [0, -1, 0, 0, -1, -1, -1, -1, 1, -1]
 1st operation: 
 find the maximum value --> 1
 replace each element:  -->
 [(1-0),(1- -1),(1-0),(1-0),(1- -1),(1- -1),(1- -1),(1- -1),(1-1),(1- -1)]
--> [1, 2, 1, 1, 2, 2, 2, 2, 0, 2]
 ```

# Input/Output


 - `[input]` integer array a

    The initial array.

    Constraints: 

    `1 <= a.length <= 100`
    
    `-100 <= a[i] <= 100`


 - `[input]` integer `k`

    non-negative number of operations.

    Constraints: `0 <= k <= 100000`


 - [output] an integer array

    The array after `k` operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
If Give an integer N . Write a program to obtain the sum of the first and last digits of this number.

-----Input-----

The first line contains an integer T, the total number of test cases. Then follow T lines, each line contains an integer N. 

-----Output-----
For each test case, display the sum of first and last digits of N in a new line.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 1000000

-----Example-----
Input
3 
1234
124894
242323

Output
5
5
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a country containing _N _cities. Each day we choose 2 cities such that there is no road between them and build a road between them. We choose each pair of nonadjacent cities with equal probability. Let X be the number of days before we obtain a connected country. What is the expected value of X? Output the integer part of answer.

Input Format

First line of input as an integer N. 

Constraints

$N<=30$

Output Format

Print an integer being the result of the test.

Sample Input 0
3

Sample Output 0
2

Explanation 0

In the first example, first two roads are sufficient for connecting the cities so the answer would be 2.

Sample Input 1
4

Sample Output 1
3

Explanation 1

In the second example if the first three roads of the country are edges of a triangle, then we need a fourth road to make the country connected, otherwise the country would be connected with first three roads. The probability of the former situation is 4/20 (number of triple of roads that make a triangle divided by number of ways we can choose 3 different roads), and the probability of later situation is 16/20. So the result would be 4/20*4 + 16/20*3 = 3.2 and since you have to print only the integer part as output, print 3

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