vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
As we all know, a palindrome is a word that equals its reverse. Here are some examples of palindromes: malayalam, gag, appa, amma.
We consider any sequence consisting of the letters of the English alphabet to be a word. So axxb,abbba and bbbccddx are words for our purpose. And aaabbaaa, abbba and bbb are examples of palindromes.
By a subword of a word, we mean a contiguous subsequence of the word. For example the subwords of the word abbba are a, b, ab, bb, ba, abb, bbb, bba, abbb, bbba and abbba.
In this task you will given a word and you must find the longest subword of this word that is also a palindrome.
For example if the given word is abbba then the answer is abbba. If the given word is abcbcabbacba then the answer is bcabbacb.

-----Input:-----
The first line of the input contains a single integer $N$ indicating the length of the word. The following line contains a single word of length $N$, made up of the letters a,b,…, z.

-----Output:-----
The first line of the output must contain a single integer indicating the length of the longest subword of the given word that is a palindrome. The second line must contain a subword that is a palindrome and which of maximum length. If there is more than one subword palindrome of maximum length, it suffices to print out any one.

-----Constraints:-----
- $1 \leq N \leq 5000$. 
- You may assume that in $30 \%$ of the inputs $1 \leq N \leq 300$.

-----Sample Input 1:-----
5
abbba

-----Sample Output 1:-----
5
abbba

-----Sample Input 2:-----
12
abcbcabbacba

-----Sample Output 2:-----
8
bcabbacb

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given three integers $n$, $d$ and $k$.

Your task is to construct an undirected tree on $n$ vertices with diameter $d$ and degree of each vertex at most $k$, or say that it is impossible.

An undirected tree is a connected undirected graph with $n - 1$ edges.

Diameter of a tree is the maximum length of a simple path (a path in which each vertex appears at most once) between all pairs of vertices of this tree.

Degree of a vertex is the number of edges incident to this vertex (i.e. for a vertex $u$ it is the number of edges $(u, v)$ that belong to the tree, where $v$ is any other vertex of a tree).

Input Specification:
The first line of the input contains three integers $n$, $d$ and $k$ ($1 \le n, d, k \le 4 \cdot 10^5$).

Output Specification:
If there is no tree satisfying the conditions above, print only one word "NO" (without quotes).

Otherwise in the first line print "YES" (without quotes), and then print $n - 1$ lines describing edges of a tree satisfying the conditions above. Vertices of the tree must be numbered from $1$ to $n$. You can print edges and vertices connected by an edge in any order. If there are multiple answers, print any of them.1

Demo Input:
['6 3 3\n', '6 2 3\n', '10 4 3\n', '8 5 3\n']

Demo Output:
['YES\n3 1\n4 1\n1 2\n5 2\n2 6\n', 'NO\n', 'YES\n2 9\n2 10\n10 3\n3 1\n6 10\n8 2\n4 3\n5 6\n6 7\n', 'YES\n2 5\n7 2\n3 7\n3 1\n1 6\n8 7\n4 3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Gotta Catch Em' All!

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bash wants to become a Pokemon master one day. Although he liked a lot of Pokemon, he has always been fascinated by Bulbasaur the most. Soon, things started getting serious and his fascination turned into an obsession. Since he is too young to go out and catch Bulbasaur, he came up with his own way of catching a Bulbasaur.

Each day, he takes the front page of the newspaper. He cuts out the letters one at a time, from anywhere on the front page of the newspaper to form the word "Bulbasaur" (without quotes) and sticks it on his wall. Bash is very particular about case — the first letter of "Bulbasaur" must be upper case and the rest must be lower case. By doing this he thinks he has caught one Bulbasaur. He then repeats this step on the left over part of the newspaper. He keeps doing this until it is not possible to form the word "Bulbasaur" from the newspaper.

Given the text on the front page of the newspaper, can you tell how many Bulbasaurs he will catch today?

Note: uppercase and lowercase letters are considered different.

Input Specification:
Input contains a single line containing a string *s* (1<=<=≤<=<=|*s*|<=<=≤<=<=105) — the text on the front page of the newspaper without spaces and punctuation marks. |*s*| is the length of the string *s*.

The string *s* contains lowercase and uppercase English letters, i.e. .

Output Specification:
Output a single integer, the answer to the problem.

Demo Input:
['Bulbbasaur\n', 'F\n', 'aBddulbasaurrgndgbualdBdsagaurrgndbb\n']

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

Note:
In the first case, you could pick: Bulbbasaur.

In the second case, there is no way to pick even a single Bulbasaur.

In the third case, you can rearrange the string to BulbasaurBulbasauraddrgndgddgargndbb to get two words "Bulbasaur".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A robot in a two-dimensional maze again. The maze has an entrance and an exit this time, though.

Just as in the previous problem, the maze is made up of H × W grid cells, its upper side faces north, and each cell is either empty or wall. Unlike the previous, on the other hand, one of the empty cells is connected to the entrance and another to the exit.

The robot is rather complex - there is some control, but not full. It is associated with a controller that has two buttons, namely forward and turn. The forward button moves the robot forward to the next cell, if possible. The robot can not move into a wall nor outside the maze. The turn button turns the robot as programmed. Here the program is a finite sequence of N commands, each of which is either 'L' (indicating a left turn) or 'R' (a right turn). The first turn follows the first command; the second turn follows the second command; similar for the following turns. The turn button stops working once the commands are exhausted; the forward button still works in such a case though. The robot always turns by 90 degrees at once.

The robot is initially put on the entrance cell, directed to the north. Your mission is to determine whether it can reach the exit cell if controlled properly.



Input

The input is a sequence of datasets. Each dataset is formatted as follows.

H W N
s1 ... sN
c1,1c1,2...c1,W
...
cH,1cH,2...cH,W


The first line of a dataset contains three integers H, W and N (1 ≤ H, W ≤ 1,000, 1 ≤ N ≤ 1,000,000).

The second line contains a program of N commands.

Each of the following H lines contains exactly W characters. Each of these characters represents a cell of the maze. "." indicates empty, "#" indicates a wall, "S" indicates an entrance, and "G" indicates an exit. There is exactly one entrance cell and one exit cell.

The end of input is indicated by a line with three zeros.

Output

For each dataset, output whether the robot can reach the exit in a line: "Yes" if it can or "No" otherwise (without quotes).

Examples

Input

2 2 1
L
G.
#S
2 2 2
RR
G.
.S
3 3 6
LLLLLL
G#.
...
.#S
0 0 0


Output

Yes
No
Yes


Input

2 2 1
L
G.
S
2 2 2
RR
G.
.S
3 3 6
LLLLLL
G#.
...
.#S
0 0 0


Output

Yes
No
Yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer N. Can you find the least positive integer X made up of only 9's and 0's, such that, X is a multiple of N?

Update  

X is made up of one or more occurences of 9 and zero or more occurences of 0. 

Input Format 

The first line contains an integer T which denotes the number of test cases. T lines follow. 

Each line contains the integer N for which the solution has to be found.

Output Format 

Print the answer X to STDOUT corresponding to each test case. The output should not contain any leading zeroes. 

Constraints 

1 <= T <= 10^{4} 

1 <= N <= 500

Sample Input  

3
5
7
1

Sample Output  

90
9009
9

Explanation 

90 is the smallest number made up of 9's and 0's divisible by 5. 
Similarly, you can derive for other cases. 

Timelimits
Timelimits for this challenge is given here

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ students in a university. The number of students is even. The $i$-th student has programming skill equal to $a_i$. 

The coach wants to form $\frac{n}{2}$ teams. Each team should consist of exactly two students, and each student should belong to exactly one team. Two students can form a team only if their skills are equal (otherwise they cannot understand each other and cannot form a team).

Students can solve problems to increase their skill. One solved problem increases the skill by one.

The coach wants to know the minimum total number of problems students should solve to form exactly $\frac{n}{2}$ teams (i.e. each pair of students should form a team). Your task is to find this number.


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 100$) — the number of students. It is guaranteed that $n$ is even.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$), where $a_i$ is the skill of the $i$-th student.


-----Output-----

Print one number — the minimum total number of problems students should solve to form exactly $\frac{n}{2}$ teams.


-----Examples-----
Input
6
5 10 2 3 14 5

Output
5

Input
2
1 100

Output
99



-----Note-----

In the first example the optimal teams will be: $(3, 4)$, $(1, 6)$ and $(2, 5)$, where numbers in brackets are indices of students. Then, to form the first team the third student should solve $1$ problem, to form the second team nobody needs to solve problems and to form the third team the second student should solve $4$ problems so the answer is $1 + 4 = 5$.

In the second example the first student should solve $99$ problems to form a team with the second one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef wants to serve mankind by making people immortal by preparing a dish, a dish of life - a dish with the best taste in the universe, one with the smell and splash of fresh water flowing down the springs of the mountain, one with the smell of the best lily flowers of the garden, one that has contained the very essence of life in a real sense. 
This dish will contain K ingredients that are found only in remote islands amid mountains. For sake of convenience, we enumerate the ingredients by the integers from 1 to K, both inclusive. There are N islands and each of them offers some ingredients. Chef being a little child did not know how to collect the ingredients for the recipe. He went to all the islands and bought all the ingredients offered in each island. Could he possibly have saved some time by skipping some island? If it was not possible for Chef to collect the required ingredients (i.e. all the K ingredients), output "sad". If it was possible for him to skip some islands, output "some", otherwise output "all".

-----Input-----
First line of the input contains an integer T denoting number of test cases. The description of T test cases follow.
The first line of each test case contains two space separated integers N, K.
The i-th of the next lines will contain first an integer Pi, denoting the number of ingredients grown in the i-th island, followed by Pi distinct integers in the range [1, K]. All the integers are space separated. 

-----Output-----
For each test case, output a single line containing one of the strings "sad", "all" or "some" (without quotes) according to the situation. 

-----Constraints-----
- 1 ≤ T  ≤ 10
- 1 ≤ N, K ≤ 105
- 1 ≤ Pi ≤ K
- Sum of Pi over all test cases ≤ 106

-----Subtasks-----
Subtask #1 (30 points)
- 1 ≤ N, K ≤ 50

Subtask #2 (30 points)
- 1 ≤ K ≤ 50

Subtask #3 (40 points)
- original constraints

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

Output
sad
some
all

-----Explanation-----
Example 1. The ingredient 4 is not available in any island, so Chef can't make the dish of life. Hence, the answer is "sad".
Example 2. Chef can just go to the first island and collect all the three ingredients required. He does not need to visit the second island. So, the answer is "some".
Example 3. Chef has to visit both the islands in order to obtain all the three ingredients. So, the answer is "all".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arya Stark a headstrong, fiercely independent, disdains traditional women's pursuits, the younger daughter of Lord Eddard Stark and his wife Lady Catelyn Starkand who is often mistaken for a boy, becomes increasingly hardened and brutalized, and personally kills a number of men after the execution of her father. She compiles a list of people she intends to kill.
Chiswyck - For capturing them, for thinking that Polliver taking her Needle was funny.
Dunsen - For capturing them, for taking Gendry's bull's horn helmet
Ser Meryn Trant - For killing Syrio Forel
Today, while working her routine she manages to cross another villain off her list "Ser Meryn Trant", the cruelest member of the Kingsguard, who she blames for killing Syrio Forel, the man hired by Ned Stark to train her with a swordand later had a hand in Ned Stark’s execution.
But like always it's not an easy task.
Little Arya is on the one corner of the hallway and Ser Meryn Trant on the diagonaly opposite corner. There is a little trick in the hallway of House of Black and White. Little Arya can jump only on white tile and move but can't jump on black tile,if she jumps Ser Meryn Trant will flew away.The hallway is of size N*N with source position of Arya as (0,0) and Ser Meryn Trant as (N-1,N-1) in the hallway. There are combination of white and black tiles ,the black ones are marked as 0 which are blocked cells, rest being marked 1.

A path is a connected sequence of elements from (0,0) to (N-1,N-1) which consists of 1 for arya to execute. A sequence of 1s in the hallway is connected if every 1 in the sequence is adjacent (the above or left neighbour) to the next 1 in the sequence.

For example,

'1' '1' '0'

'0' '1' '1'

'1' '0' '1'

the 1s marked in quotes is a connected path from (0,0) to (2,2)

Note that cells at (0,0) and (N-1,N-1) are always 1. she can either make movement towards right or down, i.e., from position (x,y) she can go to either the position (x,y+1) or (x+1,y).

Input

First line consists of the number of test cases and second line consist of size of hallway (N ≤ 50), following that would be the state of NxN maze which would consist of 0s and 1s.

Output

You have to print "POSSIBLE" if there exists a path between Arya and the Ser Meryn Trant, otherwise print "NOT POSSIBLE".

SAMPLE INPUT
2
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
3
1 0 0
0 0 0
0 0 1

SAMPLE OUTPUT
POSSIBLE
NOT POSSIBLE

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An LCM tree is a binary tree in which each node has a positive integer value, and either zero or two children. If two nodes $x$ and $y$ are the children of node $z$, then the Least Common Multiple (LCM) of the values of node $x$ and node $y$ must equal the value of node $z$. 

You are given $n$ nodes with positive integer values to be arranged into an LCM tree. In how many ways (modulo $10^9 + 7$) can you do that? Two ways are considered different if there are two nodes $x$ and $y$ so that $x$ is a child of $y$ in one way but not in the other way.

The illustration shows one of the two ways for the first sample case. The other way can be obtained by swapping the two nodes with value $4$. Note that swapping the two leaves with values $2$ and $4$ does not give a different way.

-----Input-----
The first line has an odd integer $n$ ($1 \leq n \leq 25$). The second line has $n$ positive integers no larger than $10^9$, giving the values of the nodes.

-----Output-----
Output the number of ways to arrange the given nodes into an LCM tree, modulo $10^9 + 7$.

-----Examples-----
Sample Input 1:
7
2 3 4 4 8 12 24
Sample Output 1:
2

Sample Input 2:
3
7 7 7
Sample Output 2:
3

Sample Input 3:
5
1 2 3 2 1
Sample Output 3:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
[BasE91](http://base91.sourceforge.net/) is a method for encoding binary as ASCII characters. It is more efficient than Base64 and needs 91 characters to represent the encoded data.

The following ASCII charakters are used:

    'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
    '!#$%&()*+,./:;<=>?@[]^_`{|}~"'
    
Create two functions that encode strings to basE91 string and decodes the other way round. 

    b91encode('test') = 'fPNKd'
    b91decode('fPNKd') = 'test'
    
    b91decode('>OwJh>Io0Tv!8PE') = 'Hello World!'
    b91encode('Hello World!') = '>OwJh>Io0Tv!8PE'
    
Input strings are valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The students of Codechef Middle School are visiting an amusement park. The children want to go on a ride, however, there is a minimum height requirement of $X$ cm. Determine if the children are eligible to go on the ride. 
Print "Yes" if they are eligible, "No" otherwise.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, two integers $H$ which is a child's height in cm and $X$ which is the minimum permissible height. 

-----Output:-----
For each testcase, output in a single line $"Yes"$ or $"No"$. You cannot give your answer as "YeS", "YES", "yes" or any other variation.

-----Constraints-----
- $1 \leq T \leq 10^4$
- $50 \leq H \leq 200$
- $50 \leq X \leq 200$

-----Sample Input:-----
2
120 100
90 100

-----Sample Output:-----
Yes
No

-----EXPLANATION:-----
The first child has height more than minimum permissible height, so he can go on the ride while the other person cannot!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have n-strip colorless bar code, where each strip is of unit length. You are given k brushes having their own different width. Using a brush of width w you can paint at a time exactly w consecutive strips on a bar code with black color, with the condition that initially all those w strips should be colorless. You can use any brush infinite times.

Find the number of distinct bar codes that you can create. Two bar codes are considered different if there exists at least one strip that is black in first and colorless in other. Print your answer modulo 10^9+7.

Input:

First line of input contains two space separated integers n and k denoting number of strips on bar code and number of brushes respectively. Next line contains k space separated integers, the i^th integer denoting the width of i^th brush.

Output:

Output in single line, your answer modulo 10^9+7.

Constraints:

1 ≤ n , k ≤ 10^3 
1 ≤ width of i^th brush (wi) ≤ 10^3

SAMPLE INPUT
3 1
1

SAMPLE OUTPUT
8

Explanation

Here are the possible bar codes that you can generate on strip of size 3 and brush of width 1. (0-white, 1-black)

000
001
010
100
011
101
110
111
Hence answer is 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Wet Shark once had 2 sequences: 
{a_n}= {a_1, a_2, a_3, ... , a_(10^9)}  
{b_n} = {b_1, b_2, b_3, ... , b_(10^9)}  
However, he only kept one element from each sequence. Luckily, both the elements that Wet Shark kept have the same index in Wet Shark's sequences: that is, he took a_i and b_i for some 1 ≤ i ≤ 10^9. 
Right after Wet Shark loses his sequences, he finds that he actually needs them to break the code of Cthulhu to escape a labyrinth. Cthulhu's code is a single floating point number Q. However, the code verifier is faulty. If Wet Shark enters any code c such that |c - Q| ≤ 0.01 , Cthulhu's code checker will allow him to escape.
Wet Shark now starts to panic, and consults Dry Dolphin for help via ultrasonic waves. After the Dry Dolphin Sequence Processing Factory processes data of Wet Shark's sequences, the machines give Wet Shark the following 2 relations his sequences follow for all 1 ≤ n < 10^9, where x = sqrt(2) and y = sqrt(3).



Wet Shark is now clueless on how to compute anything, and asks you for help.
Wet Shark has discovered that Cthulhu's code is actually defined as Q = (a_k + b_k) / (2^s), where s is a predetermined number, k is the index of another element in Wet Shark's sequence, and a_k, b_k are precisely the k^th elements of Wet Shark's sequences {a_n} and {b_n}, respectively.
Given k, i, and the 2 elements of the arrays Wet Shark has lost, find any value of the code c that will allow Wet Shark to exit Cthulhu's labyrinth.

Input
The first line of input contains 3 space separated integers i, k, s — the common index of the two elements Wet Shark kept, the index of Wet Shark's array needed to break Cthulhu's code, and the number s described in the problem statement, respectively. It is guaranteed that Cthulhu's code, Q, is between -10^9 and 10^9 (both inclusive).
The second line of the input contains 2 space separated integers a_i and b_i, representing the i^th element of sequence {a_n} and the i^th element of sequence {b_n}, respectively.

Output
Output any number c that will crack Cthulhu's code. Recall that if Wet Shark enters any code c such that |c - Q| ≤ 0.01 , Cthulhu's code checker will allow him to exit the labyrinth.

 Constraints 

  SUBTASK 1: 20 POINTS  
 1 ≤ i ≤ 10^3 
 1 ≤ k ≤ 10^3 
 -10^3 ≤ s ≤ 10^3 
 1 ≤ a_i, b_i ≤ 10^3 

  SUBTASK 2: 80 POINTS  
 1 ≤ i ≤ 10^10 
 1 ≤ k ≤ 10^10 
 -10^10 ≤ s ≤ 10^10 
 1 ≤ a_i, b_i ≤ 10^10 

It is guaranteed that -10^10 ≤ Q ≤  10^10.

Example
Input:
1 1 5
4 5

Output:
0.28125



Explanation
Example case 1. In this case, a_1 = 4, b_1 = 5, and s = 5. Cthulhu's code in this case is (a_1 + b_1) / (2^s) = 9/32 = 0.28125.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Iroha loves Haiku. Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order.
To create a Haiku, Iroha has come up with three different phrases. These phrases have A, B and C syllables, respectively. Determine whether she can construct a Haiku by using each of the phrases once, in some order.

-----Constraints-----
 - 1≦A,B,C≦10

-----Input-----
The input is given from Standard Input in the following format:
A B C

-----Output-----
If it is possible to construct a Haiku by using each of the phrases once, print YES (case-sensitive). Otherwise, print NO.

-----Sample Input-----
5 5 7

-----Sample Output-----
YES

Using three phrases of length 5, 5 and 7, it is possible to construct a Haiku.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are developing a new feature for the website which sells airline tickets: being able to sort tickets by price! You have already extracted the tickets' prices, so there's just the last step to be done...

You are given an array of integers. Sort it in non-descending order.


-----Input-----

The input consists of a single line of space-separated integers. The first number is n (1 ≤ n ≤ 10) — the size of the array. The following n numbers are the elements of the array (1 ≤ a_{i} ≤ 100).


-----Output-----

Output space-separated elements of the sorted array.


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

Output
1 2 3 



-----Note-----

Remember, this is a very important feature, and you have to make sure the customers appreciate it!

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