vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Having already mastered cooking, Chef has now decided to learn how to play the guitar. Often while trying to play a song, Chef has to skip several strings to reach the string he has to pluck. Eg. he may have to pluck the $1^{st}$ string and then the $6^{th}$ string. This is easy in guitars with only $6$ strings; However, Chef is playing a guitar with $10^{6}$ strings. In order to simplify his task, Chef wants you to write a program that will tell him the total number of strings he has to skip while playing his favourite song.

This is how guitar strings are numbered (In ascending order from right to left). Eg. to switch from string $1$ to $6$, Chef would have to skip $4$ strings $(2, 3, 4, 5)$. 

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
The first line of each test case contains $N$, the number of times Chef has to pluck a string
The second line of each test case contains $N$ space separated integers - $S_{1}$, $S_{2}$, ..., $S_{N}$, where $S_{i}$ is the number of the $i^{th}$ string Chef has to pluck.

------ Output: ------
For each testcase, output the total number of strings Chef has to skip over while playing his favourite song. 

------ Constraints  ------
$1 ≤ T ≤ 10$
$2 ≤ N ≤ 10^{5}$
$1 ≤ S_{i} ≤ 10^{6}$
For each valid $i$, $S_{i} \neq S_{i+1}$

------ Subtasks ------
30 points : for each valid $i$, $S_{i} < S_{i+1}$
70 points : No additional constraints

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

6

1 6 11 6 10 11

4

1 3 5 7
----- Sample Output 1 ------ 
15

3
----- explanation 1 ------ 
Test Case $1$     
- Chef skips $4$ strings $(2, 3, 4, 5)$ to move from $1$ to $6$     
- Chef skips $4$ strings $(7, 8, 9, 10)$ to move from $6$ to $11$     
- Chef skips $4$ strings $(10, 9, 8, 7)$ to move from $11$ to $6$     
- Chef skips $3$ strings $(7, 8, 9)$ to move from $6$ to $10$     
- Chef skips $0$ strings to move from $10$ to $11$     

Therefore, the answer is $4 + 4 + 4 + 3 + 0 = 15$     

Test Case $2$     
- Chef skips $1$ string to move from $1$ to $3$     
- Chef skips $1$ string to move from $3$ to $5$     
- Chef skips $1$ string to move from $5$ to $7$     

Therefore, the answer is $1 + 1 + 1 = 3$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a galaxy far, far away Lesha the student has just got to know that he has an exam in two days. As always, he hasn't attended any single class during the previous year, so he decided to spend the remaining time wisely.

Lesha knows that today he can study for at most $a$ hours, and he will have $b$ hours to study tomorrow. Note that it is possible that on his planet there are more hours in a day than on Earth. Lesha knows that the quality of his knowledge will only depend on the number of lecture notes he will read. He has access to an infinite number of notes that are enumerated with positive integers, but he knows that he can read the first note in one hour, the second note in two hours and so on. In other words, Lesha can read the note with number $k$ in $k$ hours. Lesha can read the notes in arbitrary order, however, he can't start reading a note in the first day and finish its reading in the second day.

Thus, the student has to fully read several lecture notes today, spending at most $a$ hours in total, and fully read several lecture notes tomorrow, spending at most $b$ hours in total. What is the maximum number of notes Lesha can read in the remaining time? Which notes should he read in the first day, and which — in the second?


-----Input-----

The only line of input contains two integers $a$ and $b$ ($0 \leq a, b \leq 10^{9}$) — the number of hours Lesha has today and the number of hours Lesha has tomorrow.


-----Output-----

In the first line print a single integer $n$ ($0 \leq n \leq a$) — the number of lecture notes Lesha has to read in the first day. In the second line print $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq a$), the sum of all $p_i$ should not exceed $a$.

In the third line print a single integer $m$ ($0 \leq m \leq b$) — the number of lecture notes Lesha has to read in the second day. In the fourth line print $m$ distinct integers $q_1, q_2, \ldots, q_m$ ($1 \leq q_i \leq b$), the sum of all $q_i$ should not exceed $b$.

All integers $p_i$ and $q_i$ should be distinct. The sum $n + m$ should be largest possible.


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

Output
1
3 
2
2 1 
Input
9 12

Output
2
3 6
4
1 2 4 5



-----Note-----

In the first example Lesha can read the third note in $3$ hours in the first day, and the first and the second notes in one and two hours correspondingly in the second day, spending $3$ hours as well. Note that Lesha can make it the other way round, reading the first and the second notes in the first day and the third note in the second day.

In the second example Lesha should read the third and the sixth notes in the first day, spending $9$ hours in total. In the second day Lesha should read the first, second fourth and fifth notes, spending $12$ hours in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Take 2 strings `s1` and `s2` including only letters from `a`to `z`.
Return a new **sorted** string, the longest possible, containing distinct letters,
- each taken only once - coming from s1 or s2.

# Examples:
```
a = "xyaabbbccccdefww"
b = "xxxxyyyyabklmopq"
longest(a, b) -> "abcdefklmopqwxy"

a = "abcdefghijklmnopqrstuvwxyz"
longest(a, a) -> "abcdefghijklmnopqrstuvwxyz"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Steve Jobs' ghost has come down to BITS Pilani Hyderabad Campus, since he has heard a lot about the coding culture here. Hoping to recruit talented people to work on top-secret Apple software, he keeps a strict coding test.

Apple is currently working on a upgraded version of a automated form filler. They call it the iComplete application. Steve Jobs is looking for BPHC talent to work on it.

Therefore, his coding test requires contestants to work on a basic iComplete application.

iComplete V1.0 is an application that works by receiving part of a word and automatically completing it depending on the dictionary present on the device. Therefore for the coding test, you are given a dictionary of n words. Now Steve Jobs will come over to your machine and type a string s. Your task is to complete s to match one of the words in the dictionary.

In case many words have s as a prefix, you have to find the lexicographically smallest word amongst these. In case no match is found, simply return the string s.

Input

The first line contains the string s which Steve Jobs' ghost types. The second line contains an integer n (1 ≤ n ≤ 100) which is the number of words in the dictionary. Then follow n lines which are the words on the dictionary, one on each line. All the lines have lengths of 1 to 100 characters inclusively, and consist of lowercase English letters only.
Output
If s is not the beginning of any of n words in the dictionary, print s. Otherwise, print the lexicographically lowest word beginning with s.

The lexicographical order is the order of words in a dictionary.

Sample test(s)
Input
next
2
nextpermutation
nextelement

Output
nextelement

Input
find
4
find
findfirstof
findit
fand

Output
find

Input
find
4
fondfind
fondfirstof
fondit
fand

Output
find

SAMPLE INPUT
next
2
nextpermutation
nextelement

SAMPLE OUTPUT
nextelement

Explanation

Since nextelement is smaller when seen in dictionary, it is preferred over nextpermutation.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's call a non-empty sequence of positive integers *a*1,<=*a*2... *a**k* coprime if the greatest common divisor of all elements of this sequence is equal to 1.

Given an array *a* consisting of *n* positive integers, find the number of its coprime subsequences. Since the answer may be very large, print it modulo 109<=+<=7.

Note that two subsequences are considered different if chosen indices are different. For example, in the array [1,<=1] there are 3 different subsequences: [1], [1] and [1,<=1].

Input Specification:
The first line contains one integer number *n* (1<=≤<=*n*<=≤<=100000).

The second line contains *n* integer numbers *a*1,<=*a*2... *a**n* (1<=≤<=*a**i*<=≤<=100000).

Output Specification:
Print the number of coprime subsequences of *a* modulo 109<=+<=7.

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

Demo Output:
['5\n', '15\n', '100\n']

Note:
In the first example coprime subsequences are: 
 1.  1 1.  1, 2 1.  1, 3 1.  1, 2, 3 1.  2, 3 
In the second example all subsequences are coprime.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Function Descriptions=====
floor
The tool floor returns the floor of the input element-wise.
The floor of x is the largest integer i where i≤x.

import numpy

my_array = numpy.array([1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9])
print numpy.floor(my_array)         #[ 1.  2.  3.  4.  5.  6.  7.  8.  9.]

ceil
The tool ceil returns the ceiling of the input element-wise.
The ceiling of x is the smallest integer i where i≥x.

import numpy

my_array = numpy.array([1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9])
print numpy.ceil(my_array)          #[  2.   3.   4.   5.   6.   7.   8.   9.  10.]

rint
The rint tool rounds to the nearest integer of input element-wise.

import numpy

my_array = numpy.array([1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9])
print numpy.rint(my_array)          #[  1.   2.   3.   4.   6.   7.   8.   9.  10.]

=====Problem Statement=====
You are given a 1-D array, A. Your task is to print the floor, ceil and rint of all the elements of A.

=====Input Format=====
A single line of input containing the space separated elements of array A.

=====Output Format=====
On the first line, print the floor of A.
On the second line, print the ceil of A.
On the third line, print the rint of A.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A palindrome is a string that reads the same backward as forward. For example, the strings "z", "aaa", "aba", and "abccba" are palindromes, but "codeforces" and "ab" are not. You hate palindromes because they give you déjà vu.

There is a string s. You must insert exactly one character 'a' somewhere in s. If it is possible to create a string that is not a palindrome, you should find one example. Otherwise, you should report that it is impossible.

For example, suppose s= "cbabc". By inserting an 'a', you can create "acbabc", "cababc", "cbaabc", "cbabac", or "cbabca". However "cbaabc" is a palindrome, so you must output one of the other options.

Input

The first line contains a single integer t (1≤ t≤ 10^4) — the number of test cases.

The only line of each test case contains a string s consisting of lowercase English letters.

The total length of all strings does not exceed 3⋅ 10^5.

Output

For each test case, if there is no solution, output "NO".

Otherwise, output "YES" followed by your constructed string of length |s|+1 on the next line. If there are multiple solutions, you may print any.

You can print each letter of "YES" and "NO" in any case (upper or lower).

Example

Input


6
cbabc
ab
zza
ba
a
nutforajaroftuna


Output


YES
cbabac
YES
aab
YES
zaza
YES
baa
NO
YES
nutforajarofatuna

Note

The first test case is described in the statement.

In the second test case, we can make either "aab" or "aba". But "aba" is a palindrome, so "aab" is the only correct answer.

In the third test case, "zaza" and "zzaa" are correct answers, but not "azza".

In the fourth test case, "baa" is the only correct answer.

In the fifth test case, we can only make "aa", which is a palindrome. So the answer is "NO".

In the sixth test case, "anutforajaroftuna" is a palindrome, but inserting 'a' elsewhere is valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number N, generate bit patterns from 0 to 2^N-1 such that successive patterns differ by one bit. 
A Gray code sequence must begin with 0.
 
Example 1:
Input:
N = 2
Output: 
00 01 11 10
Explanation: 
00 and 01 differ by one bit.
01 and 11 differ by one bit.
11 and 10 also differ by one bit.
 
Example 2:
Input:
N=3
Output:
000 001 011 010 110 111 101 100
Explanation:
000 and 001 differ by one bit.
001 and 011 differ by one bit.
011 and 010 differ by one bit.
Similarly, every successive pattern 
differs by one bit.
Your task:
You don't need to read input or print anything. Your task is to complete the function graycode() which takes an integer N as input and returns a la list of patterns.
 
Expected Time Complexity: O(2^{n})
Expected Auxiliary Space: O(2^{n})
 
Constraints :
1<=N<=16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's a Pokemon battle! Your task is to calculate the damage that a particular move would do using the following formula (not the actual one from the game):

Where:

* attack = your attack power
* defense = the opponent's defense
* effectiveness = the effectiveness of the attack based on the matchup (see explanation below)

Effectiveness:

Attacks can be super effective, neutral, or not very effective depending on the matchup. For example, water would be super effective against fire, but not very effective against grass.

* Super effective: 2x damage
* Neutral: 1x damage
* Not very effective: 0.5x damage

To prevent this kata from being tedious, you'll only be dealing with four types: `fire`, `water`, `grass`, and `electric`.  Here is the effectiveness of each matchup:

* `fire > grass`
* `fire < water`
* `fire = electric`

* `water < grass`
* `water < electric`

* `grass = electric`

For this kata, any type against itself is not very effective. Also, assume that the relationships between different types are symmetric (if `A` is super effective against `B`, then `B` is not very effective against `A`).

The function you must implement takes in:
1. your type
2. the opponent's type
3. your attack power
4. the opponent's defense

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

You have to write a function **pattern** which returns the following Pattern(See Examples) upto n rows, where n is parameter.

####Rules/Note:
* If the Argument is 0 or a Negative Integer then it should return "" i.e. empty string.
* The length of each line = (2n-1).
* Range of n is (-∞,100]

###Examples:

pattern(5):

        12345
       12345 
      12345  
     12345   
    12345    

pattern(10):

             1234567890
            1234567890 
           1234567890  
          1234567890   
         1234567890    
        1234567890     
       1234567890      
      1234567890       
     1234567890        
    1234567890         

pattern(15):

                  123456789012345
                 123456789012345 
                123456789012345  
               123456789012345   
              123456789012345    
             123456789012345     
            123456789012345      
           123456789012345       
          123456789012345        
         123456789012345         
        123456789012345          
       123456789012345           
      123456789012345            
     123456789012345             
    123456789012345              

pattern(20):

                       12345678901234567890
                      12345678901234567890 
                     12345678901234567890  
                    12345678901234567890   
                   12345678901234567890    
                  12345678901234567890     
                 12345678901234567890      
                12345678901234567890       
               12345678901234567890        
              12345678901234567890         
             12345678901234567890          
            12345678901234567890           
           12345678901234567890            
          12345678901234567890             
         12345678901234567890              
        12345678901234567890               
       12345678901234567890                
      12345678901234567890                 
     12345678901234567890                  
    12345678901234567890

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n × m table. Each cell of the table is colored white or black. Find the number of non-empty sets of cells such that:

  All cells in a set have the same color.  Every two cells in a set share row or column. 


-----Input-----

The first line of input contains integers n and m (1 ≤ n, m ≤ 50) — the number of rows and the number of columns correspondingly.

The next n lines of input contain descriptions of rows. There are m integers, separated by spaces, in each line. The number equals 0 if the corresponding cell is colored white and equals 1 if the corresponding cell is colored black.


-----Output-----

Output single integer  — the number of non-empty sets from the problem description.


-----Examples-----
Input
1 1
0

Output
1

Input
2 3
1 0 1
0 1 0

Output
8



-----Note-----

In the second example, there are six one-element sets. Additionally, there are two two-element sets, the first one consists of the first and the third cells of the first row, the second one consists of the first and the third cells of the second row. To sum up, there are 8 sets.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Hacker, pack your bags!

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
It's well known that the best way to distract from something is to do one's favourite thing. Job is such a thing for Leha.

So the hacker began to work hard in order to get rid of boredom. It means that Leha began to hack computers all over the world. For such zeal boss gave the hacker a vacation of exactly *x* days. You know the majority of people prefer to go somewhere for a vacation, so Leha immediately went to the travel agency. There he found out that *n* vouchers left. *i*-th voucher is characterized by three integers *l**i*, *r**i*, *cost**i* — day of departure from Vičkopolis, day of arriving back in Vičkopolis and cost of the voucher correspondingly. The duration of the *i*-th voucher is a value *r**i*<=-<=*l**i*<=+<=1.

At the same time Leha wants to split his own vocation into two parts. Besides he wants to spend as little money as possible. Formally Leha wants to choose exactly two vouchers *i* and *j* (*i*<=≠<=*j*) so that they don't intersect, sum of their durations is exactly *x* and their total cost is as minimal as possible. Two vouchers *i* and *j* don't intersect if only at least one of the following conditions is fulfilled: *r**i*<=&lt;<=*l**j* or *r**j*<=&lt;<=*l**i*.

Help Leha to choose the necessary vouchers!

Input Specification:
The first line contains two integers *n* and *x* (2<=≤<=*n*,<=*x*<=≤<=2·105) — the number of vouchers in the travel agency and the duration of Leha's vacation correspondingly.

Each of the next *n* lines contains three integers *l**i*, *r**i* and *cost**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=2·105,<=1<=≤<=*cost**i*<=≤<=109) — description of the voucher.

Output Specification:
Print a single integer — a minimal amount of money that Leha will spend, or print <=-<=1 if it's impossible to choose two disjoint vouchers with the total duration exactly *x*.

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

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

Note:
In the first sample Leha should choose first and third vouchers. Hereupon the total duration will be equal to (3 - 1 + 1) + (6 - 5 + 1) = 5 and the total cost will be 4 + 1 = 5.

In the second sample the duration of each voucher is 3 therefore it's impossible to choose two vouchers with the total duration equal to 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are twelve types of tiles in Fig. 1. You were asked to fill a table with R × C cells with these tiles. R is the number of rows and C is the number of columns.

How many arrangements in the table meet the following constraints?

* Each cell has one tile.

* the center of the upper left cell (1,1) and the center of the lower right cell (C, R) are connected by some roads.




<image>

Fig. 1: the types of tiles



Input

The first line contains two integers R and C (2 ≤ R × C ≤ 15). You can safely assume at least one of R and C is greater than 1.
The second line contains twelve integers, t1, t2, ..., t12 (0 ≤ t1 + .... + t12 ≤ 15). ti represents the number of the i-th tiles you have.

Output

Output the number of arrangments in a line.

Examples

Input

3 3
4 2 2 0 0 0 0 0 0 0 0 1


Output

2


Input

3 3
0 1 1 0 0 0 0 0 0 0 0 7


Output

66


Input

3 3
0 0 0 0 0 0 0 0 0 0 0 10


Output

1


Input

2 4
0 0 1 1 1 2 0 1 0 0 1 1


Output

2012


Input

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


Output

8512

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A teacher asks the class to open their books to a page number. A student can either start turning pages from the front of the book or from the back of the book. They always turn pages one at a time.  When they open the book, page $1$ is always on the right side:

When they flip page $1$, they see pages $2$ and $3$.  Each page except the last page will always be printed on both sides.  The last page may only be printed on the front, given the length of the book.  If the book is $n$ pages long, and a student wants to turn to page $\boldsymbol{p}$, what is the minimum number of pages to turn?  They can start at the beginning or the end of the book. 

Given $n$ and $\boldsymbol{p}$, find and print the minimum number of pages that must be turned in order to arrive at page $\boldsymbol{p}$. 

Example  

$n=5$ 

$p=3$  

Using the diagram above, if the student wants to get to page $3$, they open the book to page $1$, flip $1$ page and they are on the correct page.  If they open the book to the last page, page $5$, they turn $1$ page and are at the correct page.  Return $1$. 

Function Description  

Complete the pageCount function in the editor below.  

pageCount has the following parameter(s):  

int n: the number of pages in the book   
int p: the page number to turn to  

Returns  

int: the minimum number of pages to turn

Input Format

The first line contains an integer $n$, the number of pages in the book. 

The second line contains an integer, $\boldsymbol{p}$, the page to turn to.

Constraints

$1\leq n\leq10^5$
$1\leq p\leq n$

Sample Input 0
6
2

Sample Output 0
1

Explanation 0

If the student starts turning from page $1$, they only need to turn $1$ page:

If a student starts turning from page $\boldsymbol{6}$, they need to turn $2$ pages:

Return the minimum value, $1$.

Sample Input 1
5
4

Sample Output 1
0

Explanation 1

If the student starts turning from page $1$, they need to turn $2$ pages:

If they start turning from page $5$, they do not need to turn any pages:

Return the minimum value, $0$.

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