vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an array A of size N.

In one operation, you can do the following:

Choose any two adjacent elements A_{i} and A_{i+1} (1 ≤ i < N).
Let X = gcd(A_{i},A_{i+1}) and Y = lcm(A_{i},A_{i+1}). Here gcd denotes the [greatest common divisor] and lcm denotes the [least common multiple] respectively.
Replace A_{i} with X and A_{i+1} with Y.

Find the maximum value of \Sigma^{N}_{i=1}A_{i} you can achieve, after performing the above operation any (possibly zero) number of times.  
Since the result may be very large, you need to output the result modulo 10^{9}+7.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the size of A.
- The next line contains N space-separated integers A_{1},A_{2},\ldots,A_{N}, the elements of the array.

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

For each test case, output the maximum value of \Sigma^{N}_{i=1}A_{i} you can achieve, after performing the above operation any (possibly zero) number of times, modulo 10^{9}+7.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$
- The sum of $N$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
3
4
4 4 6 1
3
108 24 18
10
93179 93187 93199 93229 93239 93241 93251 93253 93257 93263

----- Sample Output 1 ------ 
19
258
392286903

----- explanation 1 ------ 
Test case $1$: Initially, $A=[4,4,6,1]$.
- Operation $1$: Choose $A_{2},A_{3}$. Thus, $X = gcd(4, 6) = 2$ and $Y = lcm(4, 6) = 12$. Thus $A$ becomes $[4,2,12,1]$.

The sum of the array is $4+2+12+1 = 19$. It can be shown that this is the maximum sum of array we can achieve after applying any number of operations.

Test case $2$: Initially, $A=[108,24,18]$.
- Operation $1$: Choose $A_{1},A_{2}$. Thus, $X = gcd(108, 24) = 12$ and $Y = lcm(108, 24) = 216$. Thus $A$ becomes $[12, 216, 18]$.
- Operation $2$: Choose $A_{2},A_{3}$. Thus, $X = gcd(216, 18) = 18$ and $Y = lcm(216, 18) = 216$. Thus $A$ becomes $[12, 18, 216]$.
- Operation $3$: Choose $A_{1},A_{2}$. Thus, $X = gcd(12, 18) = 6$ and $Y = lcm(12, 18) = 36$. Thus $A$ becomes $[6, 36, 216]$.

The sum of the array is $6+36+216 = 258$. It can be shown that this is the maximum sum of array we can achieve after applying any number of operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A Duck number is a positive number which has zeroes present in it, For example, 3210, 8050896, 70709 are all Duck numbers. A number with only leading 0s is not considered as Duck Number. For example, numbers like 035 or 0012 are not considered as Duck Numbers. A number like 01203 is considered as Duck because there is a non-leading 0 present in it.
The task is to check whether the given number N is a Duck number or not.
 
Example 1:
Input: 707069
Output: YES
Explanation: 707069 contains a non-leading 0.
 
Example 2:
Input: 02364
Output: NO
Explanation: contains only leading 0.
 
Your Task:
Your task is to complete the function check_duck() which takes a single argument(string N) and returns true if N is a Duck number else false. You need not take input or print anything. The driver code will itself print "YES" if the returned value is true and "NO" if the returned value is false.
Expected Time Complexity: O(|N|).
Expected Auxiliary Space: O(1).
 
Constraints :
1 ≤ Length of N ≤ 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Legends who were born in 90s remember Mario very well. As we all are aware of that fabulous video game our little Mario tackling with all the problems and barriers coming his way , he finally saves his Queen from the giant monster Dragon.

In this problem we let you play the game but with a little twist. The aim is same though. You have to help out our Mario to save the Queen.

Twist is that you will be given a Matrix for current stage with characters including M (Position of Mario), Q (Position of Queen), $ (Position(s) of Dragon(s)) and .(dot) (Empty Positions).

Our Mario is asking you to tell him how many different and Unique moves he can make to save the Queen and then he will request you to tell him the very Optimized move (if there any).

So if you are really a big Mario Video Game fan then help out little Mario.

Input : First line will contains integer T indicating number of Test Cases. Each Test Case will have an integer N indicating the NxN matrix. Next N lines will be having the NxN matrix.

Output : For each Test Case produce the output as follows,
Case x: y < a1 a2 ... an > where x : Test Case Number, y : Optimized Step and < a1 a2 ... an > array in increasing order of all possible steps he can play.

Note : If there is no move to save the Queen just print -1.

Constraints

1 ≤ T ≤ 10

3 ≤ N ≤ 10

Note :- To be Eligible for Prizes you have to register and create your home address maptag.

Click here to create your Maptag

SAMPLE INPUT
2
3
. . Q
. . $
M $ .
3
M . .
$ $ .
Q $ .

SAMPLE OUTPUT
Case 1: 2 < 2 3 4 5 >
Case 2: -1

Explanation

Case 1 : Mario can save the Queen with steps < 2 3 4 5 > and the best answer will be 2

Case 2 : Mario can not save the Queen so answer is -1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array with $N$ integers: $A[1], A[2], \ldots, A[N]$ (where $N$ is even). You are allowed to permute the elements however you want. Say, after permuting the elements, you end up with the array $A'[1], A'[2], \ldots, A'[N]$. Your goal is to maximize the following sum:
|A′[1]−A′[2]| + |A′[3]−A′[4]| + ... + |A′[N−1]−A′[N]||A′[1]−A′[2]| + |A′[3]−A′[4]| + ... + |A′[N−1]−A′[N]|
|A'[1] - A'[2]| \ + \ |A'[3] - A'[4]| \ + \ ... \ + \ |A'[N - 1] - A'[N]|

Here, $|x|$ denotes the absolute value of $x$.
You have to print the maximum sum achievable.

-----Input-----
- The first line contains $T$, the number of test cases.
- Each test case starts with an integer $N$ in the first line.
- The second line of each test case contains $N$ space separated integers, denoting the values of array $A$.

-----Output-----
For each test case, output the maximum sum achievable in a new line.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le N \le 10^5$
- $N$ is even
- $|A[i]| \le 10^9$
- Sum of $N$ over all test cases $\le 2 * 10^5$

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

-----Example Output 1-----
9

-----Explanation 1-----
The original array is {$1, -3, 2, -3$}. Suppose you permute it and get the array {$2, 1, -3, -3$}. Then the corresponding sum would be $|2 - 1| \ + \ |-3 - (-3)| = 1 + 0 = 1$.
But suppose you permute it differently and get the array {$-3, 2, 1, -3$}. Then the corresponding sum would be $|-3 - 2| \ + \ |1 - (-3)| = 5 + 4 = 9$. You can check that you cannot do any better, and hence the answer is 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Wet Shark and Blocks

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *b* blocks of digits. Each one consisting of the same *n* digits, which are given to you in the input. Wet Shark must choose exactly one digit from each block and concatenate all of those digits together to form one large integer. For example, if he chooses digit 1 from the first block and digit 2 from the second block, he gets the integer 12. 

Wet Shark then takes this number modulo *x*. Please, tell him how many ways he can choose one digit from each block so that he gets exactly *k* as the final result. As this number may be too large, print it modulo 109<=+<=7.

Note, that the number of ways to choose some digit in the block is equal to the number of it's occurrences. For example, there are 3 ways to choose digit 5 from block 3 5 6 7 8 9 5 1 1 1 1 5.

Input Specification:
The first line of the input contains four space-separated integers, *n*, *b*, *k* and *x* (2<=≤<=*n*<=≤<=50<=000,<=1<=≤<=*b*<=≤<=109,<=0<=≤<=*k*<=&lt;<=*x*<=≤<=100,<=*x*<=≥<=2) — the number of digits in one block, the number of blocks, interesting remainder modulo *x* and modulo *x* itself.

The next line contains *n* space separated integers *a**i* (1<=≤<=*a**i*<=≤<=9), that give the digits contained in each block.

Output Specification:
Print the number of ways to pick exactly one digit from each blocks, such that the resulting integer equals *k* modulo *x*.

Demo Input:
['12 1 5 10\n3 5 6 7 8 9 5 1 1 1 1 5\n', '3 2 1 2\n6 2 2\n', '3 2 1 2\n3 1 2\n']

Demo Output:
['3\n', '0\n', '6\n']

Note:
In the second sample possible integers are 22, 26, 62 and 66. None of them gives the remainder 1 modulo 2.

In the third sample integers 11, 13, 21, 23, 31 and 33 have remainder 1 modulo 2. There is exactly one way to obtain each of these integers, so the total answer is 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a connected undirected simple graph, which has N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects vertices A_i and B_i. Your task is to find a path that satisfies the following conditions:

* The path traverses two or more vertices.
* The path does not traverse the same vertex more than once.
* A vertex directly connected to at least one of the endpoints of the path, is always contained in the path.



It can be proved that such a path always exists. Also, if there are more than one solution, any of them will be accepted.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq M \leq 10^5
* 1 \leq A_i < B_i \leq N
* The given graph is connected and simple (that is, for every pair of vertices, there is at most one edge that directly connects them).

Input

Input is given from Standard Input in the following format:


N M
A_1 B_1
A_2 B_2
:
A_M B_M


Output

Find one path that satisfies the conditions, and print it in the following format. In the first line, print the count of the vertices contained in the path. In the second line, print a space-separated list of the indices of the vertices, in order of appearance in the path.

Examples

Input

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


Output

4
2 3 1 4


Input

7 8
1 2
2 3
3 4
4 5
5 6
6 7
3 5
2 6


Output

7
1 2 3 4 5 6 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will turn on the air conditioner if, and only if, the temperature of the room is 30 degrees Celsius or above.
The current temperature of the room is X degrees Celsius. Will you turn on the air conditioner?

-----Constraints-----
 - -40 \leq X \leq 40
 - X is an integer.

-----Input-----
Input is given from Standard Input in the following format:
X

-----Output-----
Print Yes if you will turn on the air conditioner; print No otherwise.

-----Sample Input-----
25

-----Sample Output-----
No


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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Inna and Dima bought a table of size *n*<=×<=*m* in the shop. Each cell of the table contains a single letter: "D", "I", "M", "A".

Inna loves Dima, so she wants to go through his name as many times as possible as she moves through the table. For that, Inna acts as follows:
 1.  initially, Inna chooses some cell of the table where letter "D" is written; 1.  then Inna can move to some side-adjacent table cell that contains letter "I"; then from this cell she can go to one of the side-adjacent table cells that contains the written letter "M"; then she can go to a side-adjacent cell that contains letter "A". Then Inna assumes that she has gone through her sweetheart's name; 1.  Inna's next move can be going to one of the side-adjacent table cells that contains letter "D" and then walk on through name DIMA in the similar manner. Inna never skips a letter. So, from the letter "D" she always goes to the letter "I", from the letter "I" she always goes the to letter "M", from the letter "M" she always goes to the letter "A", and from the letter "A" she always goes to the letter "D". 
Depending on the choice of the initial table cell, Inna can go through name DIMA either an infinite number of times or some positive finite number of times or she can't go through his name once. Help Inna find out what maximum number of times she can go through name DIMA.

Input Specification:
The first line of the input contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=103). 

Then follow *n* lines that describe Inna and Dima's table. Each line contains *m* characters. Each character is one of the following four characters: "D", "I", "M", "A". 

Note that it is not guaranteed that the table contains at least one letter "D".

Output Specification:
If Inna cannot go through name DIMA once, print on a single line "Poor Dima!" without the quotes. If there is the infinite number of names DIMA Inna can go through, print "Poor Inna!" without the quotes. Otherwise print a single integer — the maximum number of times Inna can go through name DIMA.

Demo Input:
['1 2\nDI\n', '2 2\nMA\nID\n', '5 5\nDIMAD\nDIMAI\nDIMAM\nDDMAA\nAAMID\n']

Demo Output:
['Poor Dima!\n', 'Poor Inna!\n', '4\n']

Note:
Notes to the samples:

In the first test sample, Inna cannot go through name DIMA a single time.

In the second test sample, Inna can go through the infinite number of words DIMA. For that, she should move in the clockwise direction starting from the lower right corner.

In the third test sample the best strategy is to start from the cell in the upper left corner of the table. Starting from this cell, Inna can go through name DIMA four times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Friday is Polycarpus' favourite day of the week. Not because it is followed by the weekend, but because the lessons on Friday are 2 IT lessons, 2 math lessons and 2 literature lessons. Of course, Polycarpus has prepared to all of them, unlike his buddy Innocentius. Innocentius spent all evening playing his favourite game Fur2 and didn't have enough time to do the literature task. As Innocentius didn't want to get an F, he decided to do the task and read the book called "Storm and Calm" during the IT and Math lessons (he never used to have problems with these subjects). When the IT teacher Mr. Watkins saw this, he decided to give Innocentius another task so that the boy concentrated more on the lesson and less — on the staff that has nothing to do with IT. 

Mr. Watkins said that a palindrome is a string that can be read the same way in either direction, from the left to the right and from the right to the left. A concatenation of strings a, b is a string ab that results from consecutive adding of string b to string a. Of course, Innocentius knew it all but the task was much harder than he could have imagined. Mr. Watkins asked change in the "Storm and Calm" the minimum number of characters so that the text of the book would also be a concatenation of no more than k palindromes. Innocentius can't complete the task and therefore asks you to help him.

Input

The first input line contains a non-empty string s which is the text of "Storm and Calm" (without spaces). The length of the string s does not exceed 500 characters. String s consists of uppercase and lowercase Latin letters. The second line contains a single number k (1 ≤ k ≤ |s|, where |s| represents the length of the string s).

Output

Print on the first line the minimum number of changes that Innocentius will have to make. Print on the second line the string consisting of no more than k palindromes. Each palindrome should be non-empty and consist of uppercase and lowercase Latin letters. Use the character "+" (ASCII-code 43) to separate consecutive palindromes. If there exist several solutions, print any of them.

The letters' case does matter, that is an uppercase letter is not considered equivalent to the corresponding lowercase letter.

Examples

Input

abacaba
1


Output

0
abacaba


Input

abdcaba
2


Output

1
abdcdba


Input

abdcaba
5


Output

0
a+b+d+c+aba


Input

abacababababbcbabcd
3


Output

1
abacaba+babab+bcbabcb

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The provided code stub will read in a dictionary containing key/value pairs of name:[marks] for a list of students.  Print the average of the marks array for the student name provided, showing 2 places after the decimal.  

Example 

$\textbf{marks key:value pairs are}$ 

$\text{'alpha'}:[20,30,40]$ 

$\text{'beta'}:[30,50,70]$ 

$\textbf{query_name}=\textbf{'beta'}$  

The query_name is 'beta'.  beta's average score is $(30+50+70)/3=50.0$.

Input Format

The first line contains the integer $n$, the number of students' records. The next $n$ lines contain the names and marks obtained by a student, each value separated by a space. The final line contains query_name, the name of a student to query.

Constraints

$2\leq n\leq10$  
$0\leq\textit{marks}[i]\leq100$  
$\textbf{length of marks arrays}=3$  

Output Format

Print one line: The average of the marks obtained by the particular student correct to 2 decimal places.

Sample Input 0
3
Krishna 67 68 69
Arjun 70 98 63
Malika 52 56 60
Malika

Sample Output 0
56.00

Explanation 0

Marks for Malika are $\{52,56,60\}$ whose average is $\frac{52+56+60}{3}\Rightarrow56$

Sample Input 1
2
Harsh 25 26.5 28
Anurag 26 28 30
Harsh

Sample Output 1
26.50

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For an integer N, we will choose a permutation \{P_1, P_2, ..., P_N\} of \{1, 2, ..., N\}.
Then, for each i=1,2,...,N, let M_i be the remainder when i is divided by P_i.
Find the maximum possible value of M_1 + M_2 + \cdots + M_N.

-----Constraints-----
 - N is an integer satisfying 1 \leq N \leq 10^9.

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

-----Output-----
Print the maximum possible value of M_1 + M_2 + \cdots + M_N.

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

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

When the permutation \{P_1, P_2\} = \{2, 1\} is chosen, M_1 + M_2 = 1 + 0 = 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarpus has an array, consisting of n integers a_1, a_2, ..., a_{n}. Polycarpus likes it when numbers in an array match. That's why he wants the array to have as many equal numbers as possible. For that Polycarpus performs the following operation multiple times:

  he chooses two elements of the array a_{i}, a_{j} (i ≠ j);  he simultaneously increases number a_{i} by 1 and decreases number a_{j} by 1, that is, executes a_{i} = a_{i} + 1 and a_{j} = a_{j} - 1. 

The given operation changes exactly two distinct array elements. Polycarpus can apply the described operation an infinite number of times. 

Now he wants to know what maximum number of equal array elements he can get if he performs an arbitrary number of such operation. Help Polycarpus.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the array size. The second line contains space-separated integers a_1, a_2, ..., a_{n} (|a_{i}| ≤ 10^4) — the original array.


-----Output-----

Print a single integer — the maximum number of equal array elements he can get if he performs an arbitrary number of the given operation.


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

Output
1

Input
3
1 4 1

Output
3

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petr likes to come up with problems about randomly generated data. This time problem is about random permutation. He decided to generate a random permutation this way: he takes identity permutation of numbers from $1$ to $n$ and then $3n$ times takes a random pair of different elements and swaps them. Alex envies Petr and tries to imitate him in all kind of things. Alex has also come up with a problem about random permutation. He generates a random permutation just like Petr but swaps elements $7n+1$ times instead of $3n$ times. Because it is more random, OK?!

You somehow get a test from one of these problems and now you want to know from which one.

Input Specification:
In the first line of input there is one integer $n$ ($10^{3} \le n \le 10^{6}$).

In the second line there are $n$ distinct integers between $1$ and $n$ — the permutation of size $n$ from the test.

It is guaranteed that all tests except for sample are generated this way: First we choose $n$ — the size of the permutation. Then we randomly choose a method to generate a permutation — the one of Petr or the one of Alex. Then we generate a permutation using chosen method.

Output Specification:
If the test is generated via Petr's method print "Petr" (without quotes). If the test is generated via Alex's method print "Um_nik" (without quotes).

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

Demo Output:
['Petr\n']

Note:
Please note that the sample is not a valid test (because of limitations for $n$) and is given only to illustrate input/output format. Your program still has to print correct answer to this test to get AC.

Due to randomness of input hacks in this problem are forbidden.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Uh oh, Someone at the office has dropped all these sequences on the floor and forgotten to label them with their correct bases. 

We have to fix this before the boss gets back or we're all going to be fired!

This is what your years of coding have been leading up to, now is your time to shine!

## Task

You will have to create a function which takes in a sequence of numbers in **random order** and you will have to return the correct base of those numbers.

The base is the number of unique digits. For example, a base 10 number can have 10 unique digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and a base 2 number (Binary) can have 2 unique digits: 0 and 1.

### Constraints

The sequence will always be 10 numbers long and we know that the base is going to be between 2 and 10 inclusive so no need to worry about any letters. When sorted, the sequence is made up of consecutive numbers.

### Examples

```
[ "1", "2", "3", "4", "5", "6", "7", "8", "9", "10" ]     -->  10
[ "1", "2", "3", "4", "5", "6", "10", "11", "12", "13" ]  -->   7
```

**Good luck!**

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