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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya has got many devices that work on electricity. He's got *n* supply-line filters to plug the devices, the *i*-th supply-line filter has *a**i* sockets.

Overall Vasya has got *m* devices and *k* electrical sockets in his flat, he can plug the devices or supply-line filters directly. Of course, he can plug the supply-line filter to any other supply-line filter. The device (or the supply-line filter) is considered plugged to electricity if it is either plugged to one of *k* electrical sockets, or if it is plugged to some supply-line filter that is in turn plugged to electricity. 

What minimum number of supply-line filters from the given set will Vasya need to plug all the devices he has to electricity? Note that all devices and supply-line filters take one socket for plugging and that he can use one socket to plug either one device or one supply-line filter.

Input Specification:
The first line contains three integers *n*, *m*, *k* (1<=≤<=*n*,<=*m*,<=*k*<=≤<=50) — the number of supply-line filters, the number of devices and the number of sockets that he can plug to directly, correspondingly. The second line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=50) — number *a**i* stands for the number of sockets on the *i*-th supply-line filter.

Output Specification:
Print a single number — the minimum number of supply-line filters that is needed to plug all the devices to electricity. If it is impossible to plug all the devices even using all the supply-line filters, print -1.

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

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

Note:
In the first test case he can plug the first supply-line filter directly to electricity. After he plug it, he get 5 (3 on the supply-line filter and 2 remaining sockets for direct plugging) available sockets to plug. Thus, one filter is enough to plug 5 devices.

One of the optimal ways in the second test sample is to plug the second supply-line filter directly and plug the fourth supply-line filter to one of the sockets in the second supply-line filter. Thus, he gets exactly 7 sockets, available to plug: one to plug to the electricity directly, 2 on the second supply-line filter, 4 on the fourth supply-line filter. There's no way he can plug 7 devices if he use one supply-line filter.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have n super washing machines on a line. Initially, each washing machine has some dresses or is empty. 


For each move, you could choose any m (1 ≤ m ≤ n) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines  at the same time .  

Given an integer array representing the number of dresses in each washing machine from left to right on the line, you should find the minimum number of moves to make all the washing machines have the same number of dresses. If it is not possible to do it, return -1.

Example1

Input: [1,0,5]

Output: 3

Explanation: 
1st move:    1     0     1     1     4
2nd move:    1     2     1     3    
3rd move:    2     1     2     2     2   


Example2

Input: [0,3,0]

Output: 2

Explanation: 
1st move:    0     1     2     0    
2nd move:    1     2 --> 0    =>    1     1     1     


Example3

Input: [0,2,0]

Output: -1

Explanation: 
It's impossible to make all the three washing machines have the same number of dresses. 




Note:

The range of n is [1, 10000].
The range of dresses number in a super washing machine is [0, 1e5].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two strings str1 and str2. The task is to remove or insert the minimum number of characters from/in str1 so as to transform it into str2. It could be possible that the same character needs to be removed/deleted from one point of str1 and inserted to some another point.
Example 1:
Input: str1 = "heap", str2 = "pea"
Output: 3
Explanation: 2 deletions and 1 insertion
p and h deleted from heap. Then, p is 
inserted at the beginning One thing to 
note, though p was required yet it was 
removed/deleted first from its position 
and then it is inserted to some other 
position. Thus, p contributes one to the 
deletion_count and one to the 
insertion_count.
Example 2:
Input : str1 = "geeksforgeeks"
str2 = "geeks"
Output: 8
Explanation: 8 deletions
 
Your Task:
You don't need to read or print anything. Your task is to complete the function minOperations() which takes both strings as input parameter and returns the minimum number of operation required.
Expected Time Complexity: O(|str1|*|str2|)
Expected Space Complexity: O(|str1|*|str2|)
Constraints:
1 ≤ |str1|, |str2| ≤ 1000
All the characters are lower case English alphabets

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ayush and Ashish play a game on an unrooted tree consisting of $n$ nodes numbered $1$ to $n$. Players make the following move in turns:   Select any leaf node in the tree and remove it together with any edge which has this node as one of its endpoints. A leaf node is a node with degree less than or equal to $1$. 

A tree is a connected undirected graph without cycles.

There is a special node numbered $x$. The player who removes this node wins the game. 

Ayush moves first. Determine the winner of the game if each player plays optimally.


-----Input-----

The first line of the input contains a single integer $t$ $(1 \leq t \leq 10)$ — the number of testcases. The description of the test cases follows.

The first line of each testcase contains two integers $n$ and $x$ $(1\leq n \leq 1000, 1 \leq x \leq n)$ — the number of nodes in the tree and the special node respectively.

Each of the next $n-1$ lines contain two integers $u$, $v$ $(1 \leq u, v \leq n, \text{ } u \ne v)$, meaning that there is an edge between nodes $u$ and $v$ in the tree.


-----Output-----

For every test case, if Ayush wins the game, print "Ayush", otherwise print "Ashish" (without quotes).


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

Output
Ashish

Input
1
3 2
1 2
1 3

Output
Ayush



-----Note-----

For the $1$st test case, Ayush can only remove node $2$ or $3$, after which node $1$ becomes a leaf node and Ashish can remove it in his turn.

For the $2$nd test case, Ayush can remove node $2$ in the first move itself.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the following game. There are k pairs of n cards with numbers from 1 to n written one by one. Shuffle these kn cards well to make piles of k cards and arrange them in a horizontal row. The i-th (k-card) pile from the left of the n piles created in this way is called "mountain i".

<image>


The game starts at mountain 1. Draw the top card of the pile (the drawn card is not returned to the original pile), and if the number written on that card is i, draw the top card of the pile i Pull. In this way, draw the top card of the pile numbered by the number written on the drawn card repeatedly, and if all the piles have no cards, it is successful. If there are still piles of cards left, but there are no more piles to draw next, it is a failure.

If it fails in the middle, it ends with a failure, or the remaining card pile is left as it is (the pile number is also kept as it is) and the game is restarted. When restarting the game, the first card to draw is from the leftmost pile of the remaining piles (the top card of that pile is the first card to be drawn). After resuming, proceed with the game in the same way as before resuming, and if there are no cards in all the piles, it is a success. It is a failure.

<image>


Such a game shall be restarted up to m times. However, m is 0 or 1. In other words, it either does not restart once or restarts only once. The initial placement of cards differs depending on how you shuffle before the game starts. Of course, depending on the initial placement of the card, it may succeed without resuming, it may resume and succeed, or it may resume and fail. Since it is shuffled enough, we assume that all initial arrangements appear with the same probability, and we want to find the probability p that the restart will succeed within m times. Express this probability p as a decimal number, and create a program that finds and outputs to the decimal place r. However, output so that the following conditions are met.

* If p × 10K becomes an integer when a sufficiently large positive integer K is taken, 0 continues from the middle of the decimal part, but that 0 should also be output. For example, if p = 3/8 = 0.375, then 0.37500 is output if r = 5, and 0.37 is output if r = 2. Similarly, when p = 1.0, for example, if r = 3, output 1.000.
* For example, 0.150000 ... can be expressed as a recurring decimal 0.1499999 ..., but in such a case, the former expression is used.



On the first line of the input file, the integers n, k, m, and r are written in this order with a blank as the delimiter. 1 ≤ n ≤ 10000, 1 ≤ k ≤ 100, m = 0 or m = 1, 1 ≤ r ≤ 10000.

Input example 1 | Input example 2 | Input example 3
--- | --- | ---
|
2 1 0 5 | 3 1 1 3 | 2 2 1 3 |
Output example 1 | Output example 2 | Output example 3
0.50000 | 0.833 | 1.000 |

input

The input consists of multiple datasets. Input ends when n, k, m, and r are all 0. The number of datasets does not exceed 5.

output

For each dataset, p is output on one line as specified.





Example

Input

2 1 0 5
3 1 1 3
2 2 1 3
0 0 0 0


Output

0.50000
0.833
1.000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has $N$ small boxes arranged on a line from $1$ to $N$. For each valid $i$, the weight of the $i$-th box is $W_i$. Chef wants to bring them to his home, which is at the position $0$. He can hold any number of boxes at the same time; however, the total weight of the boxes he's holding must not exceed K at any time, and he can only pick the ith box if all the boxes between Chef's home and the ith box have been either moved or picked up in this trip.
Therefore, Chef will pick up boxes and carry them home in one or more round trips. Find the smallest number of round trips he needs or determine that he cannot bring all boxes home.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated integers $W_1, W_2, \ldots, W_N$.

-----Output-----
For each test case, print a single line containing one integer ― the smallest number of round trips or $-1$ if it is impossible for Chef to bring all boxes home.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N, K \le 10^3$
- $1 \le W_i \le 10^3$ for each valid $i$

-----Example Input-----
4
1 1 
2
2 4
1 1
3 6
3 4 2
3 6
3 4 3

-----Example Output-----
-1
1
2
3

-----Explanation-----
Example case 1: Since the weight of the box higher than $K$, Chef can not carry that box home in any number of the round trip.
Example case 2: Since the sum of weights of both boxes is less than $K$, Chef can carry them home in one round trip.
Example case 3: In the first round trip, Chef can only pick up the box at position $1$. In the second round trip, he can pick up both remaining boxes at positions $2$ and $3$.
Example case 4: Chef can only carry one box at a time, so three round trips are required.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In 17th century our Chef was a Wizard. He asked his small son "Anshu" to bring him the secret of the Magical Mountain. The boy after travelling a lot reached the Mountain.

The description of the Mountain was as follows:
- Mountain contains N magical stones. Each of them has a unique number.
- Mountain was divided into many levels, where at ith level atmost 2^i stones can be found.
- Between stones there exist a magical path containing lava.
- A stone can be connected with maximum of three stones.
- Peak of the mountain contains stone with number 1.
- If Stone 1 is first connected to stone 2 and then to 3. Assume 2 is to the left of 3.

Now, to get the secret of the mountain, Anshu started climbing from the left. On the way he used his magical wand to protect him from lava. But, while climbing he came to know that he is able to see only the one stone at each level. After reaching the peak he slided down and did the the same process. These stones that he saw shows the secret of the mountain, if they are placed in a non decreasing order on a sunny day. Anshu doesn't remember the stones number that he saw. Help him in recollecting them and getting the secret to his father.

The mountain looks like this

-----Input-----
- First line contains T the number of test cases.
- First line of each test test case contains N.
- Next N-1 lines contains X and Y the stones which are connected.

-----Output-----
- Output the required non decreasing sequence.

-----Constraints and Subtasks-----
- 1 <= T <= 10
- 1 <= X, Y <= N
Subtask 1: 20 points
- 3<=N<=100
Subtask 2: 30 points
- 3<=N<=10000
Subtask 3: 50 points
- 3<=N<=100000

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

Output:
1 2 3 4 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has just invented a new binary protocol for data transmission. He is encoding positive integer decimal number to binary string using following algorithm:

  Each digit is represented with number of '1' characters equal to the value of that digit (for 0 it is zero ones).  Digits are written one by one in order corresponding to number and separated by single '0' character. 

Though Polycarp learnt how to encode the numbers, he has no idea how to decode them back. Help him calculate the decoded number.


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 89) — length of the string s.

The second line contains string s — sequence of '0' and '1' characters, number in its encoded format. It is guaranteed that the number corresponding to the string is positive and doesn't exceed 10^9. The string always starts with '1'.


-----Output-----

Print the decoded number.


-----Examples-----
Input
3
111

Output
3

Input
9
110011101

Output
2031

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alex is attending a Halloween party with his girlfriend, Silvia. At the party, Silvia spots the corner of an infinite chocolate bar (two dimensional, infinitely long in width and length).  

If the chocolate can be served only as 1 x 1 sized pieces and Alex can cut the chocolate bar exactly ${K}$ times, what is the maximum number of chocolate pieces Alex can cut and give Silvia?

Input Format 

The first line contains an integer ${T}$, the number of test cases. ${T}$ lines follow.

Each line contains an integer ${K}$.  

Output Format

${T}$ lines; each line should contain an integer that denotes the maximum number of pieces that can be obtained for each test case.

Constraints

$1\leq T\leq10$

$2\leq K\leq10^{7}$

Note: Chocolate must be served in 1 x 1 sized pieces. Alex can't relocate any of the pieces, nor can he place any piece on top of another.

Sample Input #00  

4
5
6
7
8

Sample Output #00  

6
9
12
16

Explanation

The explanation below is for the first two test cases. The rest of them follow a similar logic.

For the first test-case where $K=5$, you need $3$ horizontal and $2$ vertical cuts.
 
For the second test case, where $K=6$, you need $3$ horizontal and $3$ vertical cuts.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Akshat has X rupees to spend in the current month. His daily expenditure is Y rupees, i.e., he spends Y rupees each day. 

Given that the current month has 30 days, find out if Akshat has enough money to meet his daily expenditures for this month.

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

- The first line will contain T - the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two integers X, Y - the amount of money Akshat has for the current month and his daily expenditure respectively.

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

For each test case, output YES if Akshat has enough money to meet his daily expenditure for 30 days of the month, otherwise output NO.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

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

$1 ≤ T ≤ 100$
$1 ≤ X, Y ≤ 10^{5}$

----- Sample Input 1 ------ 
3
1000 10
250 50
1500 50

----- Sample Output 1 ------ 
YES
NO
YES

----- explanation 1 ------ 
Test Case $1$: Akshat has $1000$ rupees and he wants to spend $30 \times 10 = 300$ rupees in the entire month. Therefore, he has enough money for the entire month.

Test Case $2$: Akshat has $250$ rupees and he wants to spend $30 \times 50 = 1500$ rupees in the entire month. Therefore, he does not have enough money for the entire month.

Test Case $3$: Akshat has $1500$ rupees and he wants to spend $30 \times 50 = 1500$ rupees in the entire month. Therefore, he has enough money for the entire month.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a linked list sorted in ascending order and an integer called data, insert data in the linked list such that the list remains sorted.
Example 1:
Input:
LinkedList: 25->36->47->58->69->80
data: 19
Output: 19 25 36 47 58 69 80
Example 2:
Input:
LinkedList: 50->100
data: 75
Output: 50 75 100
Your Task:
The task is to complete the function sortedInsert() which should insert the element in sorted Linked List and return the head of the linked list
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^{4}
-99999 <= A[i] <= 99999, for each valid i

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mahesh got a beautiful array named A as a birthday gift from his beautiful girlfriend Namratha. There are N positive integers in that array. Mahesh loved the array so much that he started to spend a lot of time on it everyday. One day, he wrote down all possible subsets of the array. Then for each subset, he calculated the sum of elements in that subset and wrote it down on a paper. Unfortunately, Mahesh lost the beautiful array :(. He still has the paper on which he wrote all subset sums. Your task is to rebuild beautiful array A and help the couple stay happy :)


Input
The first line of the input contains an integer T denoting the number of test cases.
First line of each test case contains one integer N, the number of elements in A.
Second line of each test case contains 2^N integers, the values written on paper

Output
For each test case, output one line with N space separated integers in non-decreasing order.

Constraints

1 ≤ T ≤ 50
1 ≤ N ≤ 15
0 ≤ Values on paper ≤ 10^9
All input values are valid. A solution always exists


Example
Input
2
1
0 10
2
0 1 1 2

Output
10
1 1

Explanation
Test case #2
For the array [1,1], possible subsets are {}, {1}, {1}, {1,1}, respective sums are 0, 1, 1, 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kolya has a string s of length n consisting of lowercase and uppercase Latin letters and digits.

He wants to rearrange the symbols in s and cut it into the minimum number of parts so that each part is a palindrome and all parts have the same lengths. A palindrome is a string which reads the same backward as forward, such as madam or racecar.

Your task is to help Kolya and determine the minimum number of palindromes of equal lengths to cut s into, if it is allowed to rearrange letters in s before cuttings.

Input

The first line contains an integer n (1 ≤ n ≤ 4·105) — the length of string s.

The second line contains a string s of length n consisting of lowercase and uppercase Latin letters and digits.

Output

Print to the first line an integer k — minimum number of palindromes into which you can cut a given string.

Print to the second line k strings — the palindromes themselves. Separate them by a space. You are allowed to print palindromes in arbitrary order. All of them should have the same length.

Examples

Input

6
aabaac


Output

2
aba aca 

Input

8
0rTrT022


Output

1
02TrrT20 

Input

2
aA


Output

2
a A 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an interactive problem.

We hid from you a permutation p of length n, consisting of the elements from 1 to n. You want to guess it. To do that, you can give us 2 different indices i and j, and we will reply with p_{i} mod p_{j} (remainder of division p_{i} by p_{j}).

We have enough patience to answer at most 2 ⋅ n queries, so you should fit in this constraint. Can you do it?

As a reminder, a permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Input

The only line of the input contains a single integer n (1 ≤ n ≤ 10^4) — length of the permutation.

Interaction

The interaction starts with reading n. 

Then you are allowed to make at most 2 ⋅ n queries in the following way: 

  * "? x y" (1 ≤ x, y ≤ n, x ≠ y). 



After each one, you should read an integer k, that equals p_x mod p_y. 

When you have guessed the permutation, print a single line "! " (without quotes), followed by array p and quit.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



Exit immediately after receiving "-1" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Hack format

In the first line output n (1 ≤ n ≤ 10^4). In the second line print the permutation of n integers p_1, p_2, …, p_n.

Example

Input


3

1

2

1

0

Output


? 1 2

? 3 2

? 1 3

? 2 1

! 1 3 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Having two standards for a keypad layout is inconvenient!  
Computer keypad's layout:  


 
Cell phone keypad's layout:  


Solve the horror of unstandartized keypads by providing a function that converts computer input to a number as if it was typed by a phone.

Example:  
"789" -> "123"

Notes:  
You get a string with numbers only

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A string a of length m is called antipalindromic iff m is even, and for each i (1 ≤ i ≤ m) a_{i} ≠ a_{m} - i + 1.

Ivan has a string s consisting of n lowercase Latin letters; n is even. He wants to form some string t that will be an antipalindromic permutation of s. Also Ivan has denoted the beauty of index i as b_{i}, and the beauty of t as the sum of b_{i} among all indices i such that s_{i} = t_{i}.

Help Ivan to determine maximum possible beauty of t he can get.


-----Input-----

The first line contains one integer n (2 ≤ n ≤ 100, n is even) — the number of characters in s.

The second line contains the string s itself. It consists of only lowercase Latin letters, and it is guaranteed that its letters can be reordered to form an antipalindromic string.

The third line contains n integer numbers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 100), where b_{i} is the beauty of index i.


-----Output-----

Print one number — the maximum possible beauty of t.


-----Examples-----
Input
8
abacabac
1 1 1 1 1 1 1 1

Output
8

Input
8
abaccaba
1 2 3 4 5 6 7 8

Output
26

Input
8
abacabca
1 2 3 4 4 3 2 1

Output
17

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