vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The R1 company wants to hold a web search championship. There were n computers given for the competition, each of them is connected to the Internet. The organizers believe that the data transfer speed directly affects the result. The higher the speed of the Internet is, the faster the participant will find the necessary information. Therefore, before the competition started, each computer had its maximum possible data transfer speed measured. On the i-th computer it was a_{i} kilobits per second.

There will be k participants competing in the championship, each should get a separate computer. The organizing company does not want any of the participants to have an advantage over the others, so they want to provide the same data transfer speed to each participant's computer. Also, the organizers want to create the most comfortable conditions for the participants, so the data transfer speed on the participants' computers should be as large as possible.

The network settings of the R1 company has a special option that lets you to cut the initial maximum data transfer speed of any computer to any lower speed. How should the R1 company configure the network using the described option so that at least k of n computers had the same data transfer speed and the data transfer speed on these computers was as large as possible?


-----Input-----

The first line contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 100) — the number of computers and the number of participants, respectively. In the second line you have a space-separated sequence consisting of n integers: a_1, a_2, ..., a_{n} (16 ≤ a_{i} ≤ 32768); number a_{i} denotes the maximum data transfer speed on the i-th computer.


-----Output-----

Print a single integer — the maximum Internet speed value. It is guaranteed that the answer to the problem is always an integer.


-----Examples-----
Input
3 2
40 20 30

Output
30

Input
6 4
100 20 40 20 50 50

Output
40



-----Note-----

In the first test case the organizers can cut the first computer's speed to 30 kilobits. Then two computers (the first and the third one) will have the same speed of 30 kilobits. They should be used as the participants' computers. This answer is optimal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Having solved a tedious assignment, Mirko decided to play a game with his good friend Slavko.

They have written a sequence of $N$ letters on a piece of paper. Each one of them is trying to put together a word using letters from the sequence. They alternate taking turns consisting of removing a single letter from the sequence and appending it to the end of their word. Mirko has the first turn. The game ends when no letters are remaining in the sequence.

We define a word to be more beautiful than another word if it comes first alphabetically. The player who has the more beautiful word at the end of the game wins. If both players have equal words, they both lose.

Mirko is a much better player than Slavko, so he has decided to make it easier for Slavko by always selecting the rightmost remaining letter in the sequence. Knowing this, Slavko wants to find out if it is possible for him to win and which is the most beautiful word he can end the game with.

-----Input-----
The first line of input contains an even positive integer $N$ ($2 \le N \le 100 000$).

The second line of input contains $N$ characters, the starting letter sequence. All characters are lower case letters from the English alphabet.

-----Output-----
The first line of output must contain “DA” if it is possible for Slavko to win, and “NE” otherwise.

The second line of output must contain the most beautiful word that Slavko can have at the end of the game.

-----Examples-----
Sample Input 1:
2
ne
Sample Output 1:
NE
n

Sample Input 2:
4
kava
Sample Output 2:
DA
ak

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a permutation p_1, p_2, ... p_n of integers from 1 to n. We call a sub-segment p_l, p_{l+1}, ..., p_{r-1}, p_{r} of the permutation an interval if it is a reordering of some set of consecutive integers. For example, the permutation (6,7,1,8,5,3,2,4) has the intervals (6,7), (5,3,2,4), (3,2), and others. 

Each permutation has some trivial intervals — the full permutation itself and every single element. We call a permutation interval-free if it does not have non-trivial intervals. In other words, interval-free permutation does not have intervals of length between 2 and n - 1 inclusive. 

Your task is to count the number of interval-free permutations of length n modulo prime number p. 

Input

In the first line of the input there are two integers t (1 ≤ t ≤ 400) and p (10^8 ≤ p ≤ 10^9) — the number of test cases to solve and the prime modulo. In each of the next t lines there is one integer n (1 ≤ n ≤ 400) — the length of the permutation. 

Output

For each of t test cases print a single integer — the number of interval-free permutations modulo p. 

Examples

Input


4 998244353
1
4
5
9


Output


1
2
6
28146


Input


1 437122297
20


Output


67777575

Note

For n = 1 the only permutation is interval-free. For n = 4 two interval-free permutations are (2,4,1,3) and (3,1,4,2). For n = 5 — (2,4,1,5,3), (2,5,3,1,4), (3,1,5,2,4), (3,5,1,4,2), (4,1,3,5,2), and (4,2,5,1,3). We will not list all 28146 for n = 9, but for example (4,7,9,5,1,8,2,6,3), (2,4,6,1,9,7,3,8,5), (3,6,9,4,1,5,8,2,7), and (8,4,9,1,3,6,2,7,5) are interval-free.

The exact value for n = 20 is 264111424634864638.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nathaniel collects rare gems and minerals, and has decided he has to protect his valuable collection from thieves. He is installing an electric eye system, in which he shines a laser into the room with his collection, and the laser will hit a sensor as long as no one steps in a spot that the laser crosses. Unfortunately, he spent most of his money on his collection, so he has only one laser and one sensor, and some mirrors. He has installed the mirrors at various locations in the room, at $45$ degree angles to the walls. At the point you have been called in to help, he has only one more mirror left to install, and he wants to know if there is any way to place it such that the laser will reach the sensor (as long as no one is in its way).

We will assume that the room is always square, the laser is always in the northern wall pointing south, and the sensor is mounted on the eastern wall, such that the laser must hit it from the west. We will also assume that the interior of the room can be represented by a grid, and that all mirrors (including the one to be added) are placed at the center of grid cells, at $45$ degrees with respect to the grid axis, and that the laser and sensor are at the center of their respective column/row of the grid.

-----Input-----
The first line of the input contains three integers: $n$, the size of the room, $c$, the column number of the laser ($1\leq c\leq n$), and $r$, the row number of the sensor ($1\leq r\leq n$). This is followed by $n$ lines, each containing $n$ characters separated by spaces. The character . represents an empty space, the character \ represents a mirror oriented NW/SE and the character / represents a mirror oriented NE/SW. You may assume $1\leq n\leq 2000$ and $1\leq r,c\leq n$.

-----Output-----
The output should consist of the string YES if the laser can be made to hit the sensor with the addition of at most one mirror, or the string NO otherwise.

-----Examples-----
Sample Input:
5 2 3
. . . . .
. . . . .
. . \ . .
. \ . . .
. . . . .
Sample Output:
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's say we have a number, `num`. Find the number of values of `n` such that: there exists `n` consecutive **positive** values that sum up to `num`. A positive number is `> 0`. `n` can also be 1.

```python
#Examples
num = 1
#1
return 1

num = 15
#15, (7, 8), (4, 5, 6), (1, 2, 3, 4, 5)
return 4

num = 48
#48, (15, 16, 17)
return 2

num = 97
#97, (48, 49)
return 2
```
The upper limit is `$10^8$`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Count the pairs of length-N sequences consisting of integers between 1 and M (inclusive), A_1, A_2, \cdots, A_{N} and B_1, B_2, \cdots, B_{N}, that satisfy all of the following conditions:
 - A_i \neq B_i, for every i such that 1\leq i\leq N.
 - A_i \neq A_j and B_i \neq B_j, for every (i, j) such that 1\leq i < j\leq N.
Since the count can be enormous, print it modulo (10^9+7).

-----Constraints-----
 - 1\leq N \leq M \leq 5\times10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M

-----Output-----
Print the count modulo (10^9+7).

-----Sample Input-----
2 2

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

A_1=1,A_2=2,B_1=2,B_2=1 and A_1=2,A_2=1,B_1=1,B_2=2 satisfy the conditions.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ved is a salesman. He needs to earn at least W rupees in N days for his livelihood. However, on a given day i (1 ≤ i ≤ N), he can only earn A_{i} rupees by working on that day. 

Ved, being a lazy salesman, wants to take as many holidays as possible. It is known that on a holiday, Ved does not work and thus does not earn anything. Help maximize the number of days on which Ved can take a holiday. 

It is guaranteed that Ved can always earn at least W rupees by working on all days.

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

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and W - the size of the array A and the money Ved has to earn in those N days.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the money which Ved can earn on each day.

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

For each test case, output the maximum number of holidays Ved can take.

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

$1 ≤T ≤100$
$1 ≤W ≤10000$
$1 ≤N ≤100$
$1 ≤A_{i} ≤100$
- It is guaranteed that Ved can always earn at least $W$ rupees by working on all days.

----- Sample Input 1 ------ 
3
5 10
3 2 6 1 3
4 15
3 2 4 6
6 8
9 12 6 5 2 2

----- Sample Output 1 ------ 
2
0
5

----- explanation 1 ------ 
Test case-1: Ved can work on $2$-nd, $3$-rd and $5$-th day earning $2 + 6 + 3 = 11$ rupees $≥ W$ rupees. Thus he can take $2$ holidays on the $1$-st and the $4$-th day.

Test case-2: Ved has to work on all days to earn $≥ W$ rupees. Thus he can not take any holidays.

Test case-3: Ved can work on $2$-nd day earning $12$ rupees $≥ W$ rupees. Thus he can take holiday on the remaining days.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Nick has *n* bottles of soda left after his birthday. Each bottle is described by two values: remaining amount of soda *a**i* and bottle volume *b**i* (*a**i*<=≤<=*b**i*).

Nick has decided to pour all remaining soda into minimal number of bottles, moreover he has to do it as soon as possible. Nick spends *x* seconds to pour *x* units of soda from one bottle to another.

Nick asks you to help him to determine *k* — the minimal number of bottles to store all remaining soda and *t* — the minimal time to pour soda into *k* bottles. A bottle can't store more soda than its volume. All remaining soda should be saved.

Input Specification:
The first line contains positive integer *n* (1<=≤<=*n*<=≤<=100) — the number of bottles.

The second line contains *n* positive integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=100), where *a**i* is the amount of soda remaining in the *i*-th bottle.

The third line contains *n* positive integers *b*1,<=*b*2,<=...,<=*b**n* (1<=≤<=*b**i*<=≤<=100), where *b**i* is the volume of the *i*-th bottle.

It is guaranteed that *a**i*<=≤<=*b**i* for any *i*.

Output Specification:
The only line should contain two integers *k* and *t*, where *k* is the minimal number of bottles that can store all the soda and *t* is the minimal time to pour the soda into *k* bottles.

Demo Input:
['4\n3 3 4 3\n4 7 6 5\n', '2\n1 1\n100 100\n', '5\n10 30 5 6 24\n10 41 7 8 24\n']

Demo Output:
['2 6\n', '1 1\n', '3 11\n']

Note:
In the first example Nick can pour soda from the first bottle to the second bottle. It will take 3 seconds. After it the second bottle will contain 3 + 3 = 6 units of soda. Then he can pour soda from the fourth bottle to the second bottle and to the third bottle: one unit to the second and two units to the third. It will take 1 + 2 = 3 seconds. So, all the soda will be in two bottles and he will spend 3 + 3 = 6 seconds to do it.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have a rectangular chocolate bar consisting of *n*<=×<=*m* single squares. You want to eat exactly *k* squares, so you may need to break the chocolate bar. 

In one move you can break any single rectangular piece of chocolate in two rectangular pieces. You can break only by lines between squares: horizontally or vertically. The cost of breaking is equal to square of the break length.

For example, if you have a chocolate bar consisting of 2<=×<=3 unit squares then you can break it horizontally and get two 1<=×<=3 pieces (the cost of such breaking is 32<==<=9), or you can break it vertically in two ways and get two pieces: 2<=×<=1 and 2<=×<=2 (the cost of such breaking is 22<==<=4).

For several given values *n*, *m* and *k* find the minimum total cost of breaking. You can eat exactly *k* squares of chocolate if after all operations of breaking there is a set of rectangular pieces of chocolate with the total size equal to *k* squares. The remaining *n*·*m*<=-<=*k* squares are not necessarily form a single rectangular piece.

Input Specification:
The first line of the input contains a single integer *t* (1<=≤<=*t*<=≤<=40910) — the number of values *n*, *m* and *k* to process.

Each of the next *t* lines contains three integers *n*, *m* and *k* (1<=≤<=*n*,<=*m*<=≤<=30,<=1<=≤<=*k*<=≤<=*min*(*n*·*m*,<=50)) — the dimensions of the chocolate bar and the number of squares you want to eat respectively.

Output Specification:
For each *n*, *m* and *k* print the minimum total cost needed to break the chocolate bar, in order to make it possible to eat exactly *k* squares.

Demo Input:
['4\n2 2 1\n2 2 3\n2 2 2\n2 2 4\n']

Demo Output:
['5\n5\n4\n0\n']

Note:
In the first query of the sample one needs to perform two breaks:
 -  to split 2 × 2 bar into two pieces of 2 × 1 (cost is 2<sup class="upper-index">2</sup> = 4), -  to split the resulting 2 × 1 into two 1 × 1 pieces (cost is 1<sup class="upper-index">2</sup> = 1). 
In the second query of the sample one wants to eat 3 unit squares. One can use exactly the same strategy as in the first query of the sample.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Less or Equal

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a sequence of integers of length $n$ and integer number $k$. You should print any integer number $x$ in the range of $[1; 10^9]$ (i.e. $1 \le x \le 10^9$) such that exactly $k$ elements of given sequence are less than or equal to $x$.

Note that the sequence can contain equal elements.

If there is no such $x$, print "-1" (without quotes).

Input Specification:
The first line of the input contains integer numbers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le n$). The second line of the input contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the sequence itself.

Output Specification:
Print any integer number $x$ from range $[1; 10^9]$ such that exactly $k$ elements of given sequence is less or equal to $x$.

If there is no such $x$, print "-1" (without quotes).

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

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

Note:
In the first example $5$ is also a valid answer because the elements with indices $[1, 3, 4, 6]$ is less than or equal to $5$ and obviously less than or equal to $6$.

In the second example you cannot choose any number that only $2$ elements of the given sequence will be less than or equal to this number because $3$ elements of the given sequence will be also less than or equal to this number.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andrey's favourite number is n. Andrey's friends gave him two identical numbers n as a New Year present. He hung them on a wall and watched them adoringly.

Then Andrey got bored from looking at the same number and he started to swap digits first in one, then in the other number, then again in the first number and so on (arbitrary number of changes could be made in each number). At some point it turned out that if we sum the resulting numbers, then the number of zeroes with which the sum will end would be maximum among the possible variants of digit permutations in those numbers.

Given number n, can you find the two digit permutations that have this property?

Input

The first line contains a positive integer n — the original number. The number of digits in this number does not exceed 105. The number is written without any leading zeroes.

Output

Print two permutations of digits of number n, such that the sum of these numbers ends with the maximum number of zeroes. The permutations can have leading zeroes (if they are present, they all should be printed). The permutations do not have to be different. If there are several answers, print any of them.

Examples

Input

198


Output

981
819


Input

500


Output

500
500

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer, if the length of it's digits is a perfect square, return a square block of sqroot(length) * sqroot(length). If not, simply return "Not a perfect square!".

Examples:

1212 returns:

>1212  

Note: 4 digits so 2 squared (2x2 perfect square). 2 digits on each line.

123123123 returns: 
>123123123

Note: 9 digits so 3 squared (3x3 perfect square). 3 digits on each line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Dima and Text Messages

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Seryozha has a very changeable character. This time he refused to leave the room to Dima and his girlfriend (her hame is Inna, by the way). However, the two lovebirds can always find a way to communicate. Today they are writing text messages to each other.

Dima and Inna are using a secret code in their text messages. When Dima wants to send Inna some sentence, he writes out all words, inserting a heart before each word and after the last word. A heart is a sequence of two characters: the "less" characters (&lt;) and the digit three (3). After applying the code, a test message looks like that: &lt;3*word*1&lt;3*word*2&lt;3 ... *word**n*&lt;3.

Encoding doesn't end here. Then Dima inserts a random number of small English characters, digits, signs "more" and "less" into any places of the message.

Inna knows Dima perfectly well, so she knows what phrase Dima is going to send her beforehand. Inna has just got a text message. Help her find out if Dima encoded the message correctly. In other words, find out if a text message could have been received by encoding in the manner that is described above.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) — the number of words in Dima's message. Next *n* lines contain non-empty words, one word per line. The words only consist of small English letters. The total length of all words doesn't exceed 105. 

The last line contains non-empty text message that Inna has got. The number of characters in the text message doesn't exceed 105. A text message can contain only small English letters, digits and signs more and less.

Output Specification:
In a single line, print "yes" (without the quotes), if Dima decoded the text message correctly, and "no" (without the quotes) otherwise.

Demo Input:
['3\ni\nlove\nyou\n&lt;3i&lt;3love&lt;23you&lt;3\n', '7\ni\nam\nnot\nmain\nin\nthe\nfamily\n&lt;3i&lt;&gt;3am&lt;3the&lt;3&lt;main&lt;3in&lt;3the&lt;3&gt;&lt;3family&lt;3\n']

Demo Output:
['yes\n', 'no\n']

Note:
Please note that Dima got a good old kick in the pants for the second sample from the statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yesterday, Chef found $K$ empty boxes in the cooler and decided to fill them with apples. He ordered $N$ apples, where $N$ is a multiple of $K$. Now, he just needs to hire someone who will distribute the apples into the boxes with professional passion. 
Only two candidates passed all the interviews for the box filling job. In one minute, each candidate can put $K$ apples into boxes, but they do it in different ways: the first candidate puts exactly one apple in each box, while the second one chooses a random box with the smallest number of apples and puts $K$ apples in it.
Chef is wondering if the final distribution of apples can even depend on which candidate he hires. Can you answer that question?
Note: The boxes are distinguishable (labeled), while the apples are not. Therefore, two distributions of apples are different if there is a box such that the number of apples in it when the first candidate finishes working can be different from the number of apples in it when the second candidate finishes working.

-----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 and only line of each test case contains two space-separated integers $N$ and $K$. 

-----Output-----
For each test case, print a single line containing the string "YES" if the final distributions of apples can be different or "NO" if they will be the same (without quotes).

-----Constraints-----
- $1 \le T \le 250$
- $1 \le N, K \le 10^{18}$
- $N$ is divisible by $K$

-----Subtasks-----
Subtask #1 (30 points): $1 \le N, K \le 10^5$
Subtask #2 (70 points): original constraints

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

-----Example Output-----
NO
NO
YES

-----Explanation-----
Example case 1: No matter who is hired, all apples will be in the only box at the end.
Example case 2: At the end, there will be two apples in each box.
Example case 3: If we hire the first candidate, there will be one apple in each box, but if we hire the second one, there will be $10$ apples in one box and none in all other boxes.

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