vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Vasya's Function

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya is studying number theory. He has denoted a function *f*(*a*,<=*b*) such that:
 -  *f*(*a*,<=0)<==<=0; -  *f*(*a*,<=*b*)<==<=1<=+<=*f*(*a*,<=*b*<=-<=*gcd*(*a*,<=*b*)), where *gcd*(*a*,<=*b*) is the greatest common divisor of *a* and *b*. 
Vasya has two numbers *x* and *y*, and he wants to calculate *f*(*x*,<=*y*). He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly.

Input Specification:
The first line contains two integer numbers *x* and *y* (1<=≤<=*x*,<=*y*<=≤<=1012).

Output Specification:
Print *f*(*x*,<=*y*).

Demo Input:
['3 5\n', '6 3\n']

Demo Output:
['3\n', '1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently, Chef got obsessed with piano. He is a just a rookie in this stuff and can not move his fingers from one key to other fast enough. He discovered that the best way to train finger speed is to play scales.

There are different kinds of scales which are divided on the basis of their interval patterns. For instance, major scale is defined by pattern T-T-S-T-T-T-S, where ‘T’ stands for a whole tone whereas ‘S’ stands for a semitone. Two semitones make one tone. To understand how they are being played, please refer to the below image of piano’s octave – two consecutive keys differ by one semitone.

If we start playing from first key (note C), then we’ll play all white keys in a row (notes C-D-E-F-G-A-B-C – as you can see C and D differ for a tone as in pattern, and E and F differ for a semitone).

This pattern could be played some number of times (in cycle).


Each time Chef takes some type of a scale and plays using some number of octaves. Sometimes Chef can make up some scales, so please don’t blame him if you find some scale that does not exist in real world.

Formally, you have a set of 12 keys (i.e. one octave) and you have N such sets in a row. So in total, you have 12*N keys. You also have a pattern that consists of letters 'T' and 'S', where 'T' means move forward for two keys (from key x to key x + 2, and 'S' means move forward for one key (from key x to key x + 1).

Now, you can start playing from any of the 12*N keys. In one play, you can repeat the pattern as many times as you want, but you cannot go outside the keyboard.

Repeating pattern means that if, for example, you have pattern STTST, you can play STTST as well as STTSTSTTST, as well as STTSTSTTSTSTTST, as well as any number of repeating. For this pattern, if you choose to repeat it once, if you start at some key x, you'll press keys: x (letter 'S')-> x + 1 (letter 'T')-> x + 3 (letter 'T')-> x + 5 (letter 'S') -> x + 6 (letter 'T')-> x + 8. Also 1 ≤ x, x + 8 ≤ 12*N so as to avoid going off the keyboard.

You are asked to calculate number of different plays that can be performed. Two plays differ if and only if they start at different keys or patterns are repeated different number of times.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

First line of each test case contains scale’s pattern – string s consisting of letters ‘T’ and ‘S’ only.

Second line contains one integer N – number of octaves he’ll be using.

-----Output-----
For each test case output a single number in a line corresponding to number of different scales he’ll play. 

-----Constraints-----
- 1 ≤ T ≤ 105
- 1 ≤ |S| ≤ 100
- 1 ≤ n ≤ 7

-----Subtasks-----
Subtask 1: T < 10 4, N = 1 
Subtask 2: No additional constraints.

-----Example-----
Input:
2 
TTTT
1
TTSTTTS
3

Output:
4
36

-----Explanation-----
Example case 1. In the first case there is only one octave and Chef can play scale (not in cycle each time) starting with notes C, C#, D, D# - four together.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In ACM-ICPC contests, there are usually three people in a team. For each person in the team, you know their scores in three skills - hard work, intelligence and persistence.
You want to check whether it is possible to order these people (assign them numbers from 1 to 3) in such a way that for each 1 ≤ i ≤ 2, i+1-th person is stricly better than the i-th person.
A person x is said to be better than another person y if x doesn't score less than y in any of the skills and scores more than y in at least one skill.
Determine whether such an ordering exists.

-----Input-----
The first line fo the input contains an integer T denoting the number of test cases.
Each test consists of three lines. Each of these lines contains three space separated integers s1, s2 and s3 denoting the scores of one member of the team in each of the three skills, in the given order.

-----Output-----
For each test case, output a single line containing "yes" if such an ordering exists or "no" if doesn't exist (without quotes).

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ s1, s2, s3 ≤ 100

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

Output
yes
no
yes

-----Explanation-----
Test Case 1: We can order them as (3, 2, 1). Person 3 is better than Person 2 because his scores in the first two skills are not lesser than Person 2's. And in skill 3, Person 3 scores higher. Similarly, Person 2 is better than Person 1. He scores more than Person 1 in every skill, in fact.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When l is an odd number, the median of l numbers a_1, a_2, ..., a_l is the (\frac{l+1}{2})-th largest value among a_1, a_2, ..., a_l.
You are given N numbers X_1, X_2, ..., X_N, where N is an even number.
For each i = 1, 2, ..., N, let the median of X_1, X_2, ..., X_N excluding X_i, that is, the median of X_1, X_2, ..., X_{i-1}, X_{i+1}, ..., X_N be B_i.
Find B_i for each i = 1, 2, ..., N.

-----Constraints-----
 - 2 \leq N \leq 200000
 - N is even.
 - 1 \leq X_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
X_1 X_2 ... X_N

-----Output-----
Print N lines.
The i-th line should contain B_i.

-----Sample Input-----
4
2 4 4 3

-----Sample Output-----
4
3
3
4

 - Since the median of X_2, X_3, X_4 is 4, B_1 = 4.
 - Since the median of X_1, X_3, X_4 is 3, B_2 = 3.
 - Since the median of X_1, X_2, X_4 is 3, B_3 = 3.
 - Since the median of X_1, X_2, X_3 is 4, B_4 = 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Little Elephant is playing with the Cartesian coordinates' system. Most of all he likes playing with integer points. The Little Elephant defines an integer point as a pair of integers (x; y), such that 0 ≤ x ≤ w and 0 ≤ y ≤ h. Thus, the Little Elephant knows only (w + 1)·(h + 1) distinct integer points.

The Little Elephant wants to paint a triangle with vertexes at integer points, the triangle's area must be a positive integer. For that, he needs to find the number of groups of three points that form such triangle. At that, the order of points in a group matters, that is, the group of three points (0;0), (0;2), (2;2) isn't equal to the group (0;2), (0;0), (2;2).

Help the Little Elephant to find the number of groups of three integer points that form a nondegenerate triangle with integer area.

Input

A single line contains two integers w and h (1 ≤ w, h ≤ 4000).

Output

In a single output line print an integer — the remainder of dividing the answer to the problem by 1000000007 (109 + 7).

Examples

Input

2 1


Output

36


Input

2 2


Output

240

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
AltF4 and CtrlF4 again started playing games. This time they drew a N x N matrix and filled number in each of the cells randomly.  The game is played in turns (AltF4 always starts first, as his name comes first alphabetically). In each turn, a player calls out a number in the range [1, N] which has not already been called before. Calling this number (say i), blocks row i and column i for that player. 

At the end of the game, the scores are calculated. A player gets the value of cell (i, j) only if he had called both i and j sometimes during the game. The objective of the game is to score as high as possible. Each player plays optimally and your task is to calculate the scores given the matrix of size NxN.

Sample Input & Output
The first line contains the number of matrices T. Then the description of T matrices follows. Each of them has the size of the matrix N in the first line. Next N lines have N space separated numbers each which denoted the matrix for that game.

For each game, you need to predict the score of AltF4 and CtrlF4 separated by a space, provided both play optimally.

Constraints
T ≤ 100
1 ≤ N ≤ 100 
0 ≤ cell[i, j] ≤ 10^9

SAMPLE INPUT
1
2
4 1
1 8

SAMPLE OUTPUT
8 4

Explanation

AltF4 calls number 2. CtrlF4 has no choice but to call 1. cell(1, 1) goes to CtrlF4 because he owns 1, similarly cell(2, 2) goes to AltF4. Cell (1, 2) and (2, 1) are remain with no one because each of them dont have both 1 and 2. Hence final scores are 8 and 4 respectively.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two polynomial numbers represented by a linked list. The task is to complete the function addPolynomial() that adds these lists meaning adds the coefficients who have the same variable powers.
Note:  Given polynomials are sorted in decreasing order of power.
Example 1:
Input:
LinkedList1:  (1,x^{2) }
LinkedList2:  (1,x^{3})
Output:
1x^3 + 1x^2
Explanation: Since, x^{2} and x^{3} both have
different powers as 2 and 3. So, their
coefficient can't be added up.
Example 2:
Input:
LinkedList1:  (1,x^{3}) -> (2,x^{2})
LinkedList2:  (3,x^{3}) -> (4,x^{2})
Output:
4x^3 + 6x^2
Explanation: Since, x^{3} has two different
coefficients as 3 and 1. Adding them up
will lead to 4x^{3}. Also, x^{2} has two
coefficients as 4 and 2. So, adding them
up will give 6x^{2}.
Your Task:
The task is to complete the function addPolynomial() which should add the polynomial with same powers return the required polynomial in decreasing order of the power in the form of a linked list.
Note: Try to solve the question without using any extra space.
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N, M <= 10^{5}
1 <= x, y <= 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are locked in a room with a door that has a keypad with 10 keys corresponding to digits from 0 to 9. To escape from the room, you need to enter a correct code. You also have a sequence of digits.

Some keys on the keypad have fingerprints. You believe the correct code is the longest not necessarily contiguous subsequence of the sequence you have that only contains digits with fingerprints on the corresponding keys. Find such code.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10$) representing the number of digits in the sequence you have and the number of keys on the keypad that have fingerprints.

The next line contains $n$ distinct space-separated integers $x_1, x_2, \ldots, x_n$ ($0 \le x_i \le 9$) representing the sequence.

The next line contains $m$ distinct space-separated integers $y_1, y_2, \ldots, y_m$ ($0 \le y_i \le 9$) — the keys with fingerprints.


-----Output-----

In a single line print a space-separated sequence of integers representing the code. If the resulting sequence is empty, both printing nothing and printing a single line break is acceptable.


-----Examples-----
Input
7 3
3 5 7 1 6 2 8
1 2 7

Output
7 1 2

Input
4 4
3 4 1 0
0 1 7 9

Output
1 0



-----Note-----

In the first example, the only digits with fingerprints are $1$, $2$ and $7$. All three of them appear in the sequence you know, $7$ first, then $1$ and then $2$. Therefore the output is 7 1 2. Note that the order is important, and shall be the same as the order in the original sequence.

In the second example digits $0$, $1$, $7$ and $9$ have fingerprints, however only $0$ and $1$ appear in the original sequence. $1$ appears earlier, so the output is 1 0. Again, the order is important.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have located a major supply line that the enemy has been using. With satellite imaging, you’ve been able to determine the current location and velocity of every vehicle along the supply line, which is for all practical purposes an infinitely long straight line. Furthermore, you know that each vehicle moves at constant velocity, and that they can pass by each other without incident along this supply line. What you need to do now is deploy an air drone with special sensors that can give you readings of the contents of the vehicles. The sensor is capable of reading everything in its range instantaneously, but power limitations allow it to do so only once. In order to minimize the required range, you want to deploy it when the vehicles are as close to each other as possible. Given knowledge of the current location and velocity of all the vehicles, what is the closest that the vehicles will get to each other?

-----Input-----
There will be a single test case in the input. This test case will begin with a line with a single integer $n$ ($1 \le n \le 100000$) representing the number of vehicles. Each of the next $n$ lines will have two integers, $x$ and $v$ ($-100000 \le x,v \le 100000$), indicating the position ($x$, in meters) and velocity ($v$, in meters/hour) of that vehicle. The sign of velocity indicates direction.

-----Output-----
Output a single number equal to the minimum distance that will cover all of the vehicles at some time, in meters. Your result should have an absolute or relative error of less than $10^{-3}$.

-----Examples-----
Sample Input 1:
2
-100 1
100 -1
Sample Output 1:
0

Sample Input 2:
3
-100 1
100 -1
101 -1
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is making Window frames for his new office, for this he has  n wooden Logs whose lengths are l1, l2, … ln respectively. Chef Doesn’t want to break any logs or Stick 2 or more logs together.
To make a  h × w Window Frame, he needs two Logs with lengths equal h and two with length . 
The Chef wants as much sunlight in as possible and for it he has decided to make from the available logs as many frames as possible. Help him in finding the number of window Frames that he can make. 
Note : Chef do not need to use all the logs
Input:
The first line of the input contains a single integer T denoting the number of test cases. The description of each test case follows :.
The first line of each test case contains a single integer n the number of wooden logs. 
The second line contains  n space-separated integers l1,l2,l3….ln The length of each wooden log
Output: 
The only line in Output Contains single Integer denoting the maximum possible number of Wooden Frames.
Constraints:
1 ≤ T ≤ 10
1 ≤ n ≤ 100
1 ≤ li ≤ 10000
Example Input:
2
4
1 2 1 2
8
1 2 1 3 4 1 5 6
Example Output:
1
0
Explanation :
First Case :  We can build a frame of dimension 1x2 as two logs of each dimension are available.
Second Case :  We can’t build any Frame as no logs of length except 1 have more than one piece.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order.
Iroha is looking for X,Y,Z-Haiku (defined below) in integer sequences.
Consider all integer sequences of length N whose elements are between 1 and 10, inclusive. Out of those 10^N sequences, how many contain an X,Y,Z-Haiku?
Here, an integer sequence a_0, a_1, ..., a_{N-1} is said to contain an X,Y,Z-Haiku if and only if there exist four indices x, y, z, w (0 ≦ x < y < z < w ≦ N) such that all of the following are satisfied:
 - a_x + a_{x+1} + ... + a_{y-1} = X
 - a_y + a_{y+1} + ... + a_{z-1} = Y
 - a_z + a_{z+1} + ... + a_{w-1} = Z
Since the answer can be extremely large, print the number modulo 10^9+7.

-----Constraints-----
 - 3 ≦ N ≦ 40
 - 1 ≦ X ≦ 5
 - 1 ≦ Y ≦ 7
 - 1 ≦ Z ≦ 5

-----Input-----
The input is given from Standard Input in the following format:
N X Y Z

-----Output-----
Print the number of the sequences that contain an X,Y,Z-Haiku, modulo 10^9+7.

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

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

Here, the only sequence that contains a 5,7,5-Haiku is [5, 7, 5].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Xavier challenges one of his friend to perform some crazy string functions by giving him some words and each word basically denotes a type of string function which his friend has to perform.

WORDS WITH THEIR MEANING:-

Wordrev n->To arrange each words of the string in reverse order.The last   letter n
denotes upto which letter the words are to be reversed in the   string. For example:-the given string is my name is xavier,the given task is Wordrev 3.Then the output must be ym eman si xavier.The 3 words are reversed because the last letter is 3 that is the task is performed for 3 words,and the remaining are simply dispalyed same as they were.

subpalin n->To find the nth palindrome substring present in the given string.Here n denotes the nth palindrome substring. For eg the string is xyzbabmadamh,the task is subpalin 2.The output must be madam which is the substring of given input string."ababa" is also a palin substring but it   is not the second,it was the first substring.

sortword n->To sort the given string words alphabetically.The letter n denotes the step upto which the sorting is to be done.For example:-The string is he loves to play cricket and the given task is sortword 2.Then the output would be "cricket he to play loves" only the first two words are sorted rest remainsunsorted 

Xaviers friend plans to write a program to solve these questions easily.

Input FORMAT

The first line inputs the String on which the task is to be performed.
Next line denotes number of test cases T.
The next line inputs the T NUMBER tasks to be performed one by one.

Output Format

The output string after the application of each function one by one.

SAMPLE INPUT
my name is xavier
2
Wordrev 3
sortword 2

SAMPLE OUTPUT
ym eman si xavier
is my name xavier

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ask a small girl - "How old are you?". She always says strange things... Lets help her!


For correct answer program should return int from 0 to 9.

Assume test input string always valid and may look like 
"1 year old" or "5 years old", etc.. The first char is number only.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed.

There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by $h[i]\:\text{where}\:i\in[1,\:n]$. If you join $\boldsymbol{\mbox{k}}$ adjacent buildings, they will form a solid rectangle of area $k\times min(h[i],h[i+1],...,h[i+k-1])$.  

Example 

$h=[3,2,3]$    

A rectangle of height $h=2$ and length $k=3$ can be constructed within the boundaries.  The area formed is $h\cdot k=2\cdot3=6$.  

Function Description

Complete the function largestRectangle int the editor below.  It should return an integer representing the largest rectangle that can be formed within the bounds of consecutive buildings.  

largestRectangle has the following parameter(s):

int h[n]: the building heights   

Returns 

- long: the area of the largest rectangle that can be formed within the bounds of consecutive buildings  

Input Format

The first line contains $n$, the number of buildings. 

The second line contains $n$ space-separated integers, each the height of a building.   

Constraints

$1\leq n\leq10^5$  
$1\leq h[i]\leq10^6$

Sample Input
STDIN       Function
-----       --------
5           h[] size n = 5
1 2 3 4 5   h = [1, 2, 3, 4, 5]

Sample Output
9

Explanation

An illustration of the test case follows.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A word or a sentence in some language is called a pangram if all the characters of the alphabet of this language appear in it at least once. Pangrams are often used to demonstrate fonts in printing or test the output devices.

You are given a string consisting of lowercase and uppercase Latin letters. Check whether this string is a pangram. We say that the string contains a letter of the Latin alphabet if this letter occurs in the string in uppercase or lowercase.

Input

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of characters in the string.

The second line contains the string. The string consists only of uppercase and lowercase Latin letters.

Output

Output "YES", if the string is a pangram and "NO" otherwise.

Examples

Input

12
toosmallword


Output

NO


Input

35
TheQuickBrownFoxJumpsOverTheLazyDog


Output

YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
And where the are the phone numbers?

You are given a string s consisting of lowercase English letters and an integer k. Find the lexicographically smallest string t of length k, such that its set of letters is a subset of the set of letters of s and s is lexicographically smaller than t.

It's guaranteed that the answer exists.

Note that the set of letters is a set, not a multiset. For example, the set of letters of abadaba is {a, b, d}.

String p is lexicographically smaller than string q, if p is a prefix of q, is not equal to q or there exists i, such that p_{i} < q_{i} and for all j < i it is satisfied that p_{j} = q_{j}. For example, abc is lexicographically smaller than abcd , abd is lexicographically smaller than abec, afa is not lexicographically smaller than ab and a is not lexicographically smaller than a.


-----Input-----

The first line of input contains two space separated integers n and k (1 ≤ n, k ≤ 100 000) — the length of s and the required length of t.

The second line of input contains the string s consisting of n lowercase English letters.


-----Output-----

Output the string t conforming to the requirements above.

It's guaranteed that the answer exists.


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

Output
aca

Input
3 2
abc

Output
ac

Input
3 3
ayy

Output
yaa

Input
2 3
ba

Output
baa



-----Note-----

In the first example the list of strings t of length 3, such that the set of letters of t is a subset of letters of s is as follows: aaa, aab, aac, aba, abb, abc, aca, acb, .... Among them, those are lexicographically greater than abc: aca, acb, .... Out of those the lexicographically smallest is aca.

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