vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: New Problem

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Coming up with a new problem isn't as easy as many people think. Sometimes it is hard enough to name it. We'll consider a title original if it doesn't occur as a substring in any titles of recent Codeforces problems. 

You've got the titles of *n* last problems — the strings, consisting of lowercase English letters. Your task is to find the shortest original title for the new problem. If there are multiple such titles, choose the lexicographically minimum one. Note, that title of the problem can't be an empty string.

A substring *s*[*l*... *r*] (1<=≤<=*l*<=≤<=*r*<=≤<=|*s*|) of string *s*<==<=*s*1*s*2... *s*|*s*| (where |*s*| is the length of string *s*) is string *s**l**s**l*<=+<=1... *s**r*.

String *x*<==<=*x*1*x*2... *x**p* is lexicographically smaller than string *y*<==<=*y*1*y*2... *y**q*, if either *p*<=&lt;<=*q* and *x*1<==<=*y*1,<=*x*2<==<=*y*2,<=... ,<=*x**p*<==<=*y**p*, or there exists such number *r* (*r*<=&lt;<=*p*,<=*r*<=&lt;<=*q*), that *x*1<==<=*y*1,<=*x*2<==<=*y*2,<=... ,<=*x**r*<==<=*y**r* and *x**r*<=+<=1<=&lt;<=*y**r*<=+<=1. The string characters are compared by their ASCII codes.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=30) — the number of titles you've got to consider. Then follow *n* problem titles, one per line. Each title only consists of lowercase English letters (specifically, it doesn't contain any spaces) and has the length from 1 to 20, inclusive.

Output Specification:
Print a string, consisting of lowercase English letters — the lexicographically minimum shortest original title.

Demo Input:
['5\nthreehorses\ngoodsubstrings\nsecret\nprimematrix\nbeautifulyear\n', '4\naa\nbdefghijklmn\nopqrstuvwxyz\nc\n']

Demo Output:
['j\n', 'ab\n']

Note:
In the first sample the first 9 letters of the English alphabet (a, b, c, d, e, f, g, h, i) occur in the problem titles, so the answer is letter j.

In the second sample the titles contain 26 English letters, so the shortest original title cannot have length 1. Title aa occurs as a substring in the first title.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"Night gathers, and now my watch begins. It shall not end until my death. I shall take no wife, hold no lands, father no children. I shall wear no crowns and win no glory. I shall live and die at my post. I am the sword in the darkness. I am the watcher on the walls. I am the shield that guards the realms of men. I pledge my life and honor to the Night's Watch, for this night and all the nights to come." — The Night's Watch oath.

With that begins the watch of Jon Snow. He is assigned the task to support the stewards.

This time he has n stewards with him whom he has to provide support. Each steward has his own strength. Jon Snow likes to support a steward only if there exists at least one steward who has strength strictly less than him and at least one steward who has strength strictly greater than him.

Can you find how many stewards will Jon support?


-----Input-----

First line consists of a single integer n (1 ≤ n ≤ 10^5) — the number of stewards with Jon Snow.

Second line consists of n space separated integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9) representing the values assigned to the stewards.


-----Output-----

Output a single integer representing the number of stewards which Jon will feed.


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

Output
0
Input
3
1 2 5

Output
1


-----Note-----

In the first sample, Jon Snow cannot support steward with strength 1 because there is no steward with strength less than 1 and he cannot support steward with strength 5 because there is no steward with strength greater than 5.

In the second sample, Jon Snow can support steward with strength 2 because there are stewards with strength less than 2 and greater than 2.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus has a hobby — he develops an unusual social network. His work is almost completed, and there is only one more module to implement — the module which determines friends. Oh yes, in this social network one won't have to add friends manually! Pairs of friends are deduced in the following way. Let's assume that user *A* sent user *B* a message at time *t*1, and user *B* sent user *A* a message at time *t*2. If 0<=&lt;<=*t*2<=-<=*t*1<=≤<=*d*, then user *B*'s message was an answer to user *A*'s one. Users *A* and *B* are considered to be friends if *A* answered at least one *B*'s message or *B* answered at least one *A*'s message.

You are given the log of messages in chronological order and a number *d*. Find all pairs of users who will be considered to be friends.

Input Specification:
The first line of the input contains two integers *n* and *d* (1<=≤<=*n*,<=*d*<=≤<=1000). The next *n* lines contain the messages log. The *i*-th line contains one line of the log formatted as "*A**i* *B**i* *t**i*" (without the quotes), which means that user *A**i* sent a message to user *B**i* at time *t**i* (1<=≤<=*i*<=≤<=*n*). *A**i* and *B**i* are non-empty strings at most 20 characters long, consisting of lowercase letters ('a' ... 'z'), and *t**i* is an integer (0<=≤<=*t**i*<=≤<=10000). It is guaranteed that the lines are given in non-decreasing order of *t**i*'s and that no user sent a message to himself. The elements in the lines are separated by single spaces.

Output Specification:
In the first line print integer *k* — the number of pairs of friends. In the next *k* lines print pairs of friends as "*A**i* *B**i*" (without the quotes). You can print users in pairs and the pairs themselves in any order. Each pair must be printed exactly once.

Demo Input:
['4 1\nvasya petya 1\npetya vasya 2\nanya ivan 2\nivan anya 4\n', '1 1000\na b 0\n']

Demo Output:
['1\npetya vasya\n', '0\n']

Note:
In the first sample test case Vasya and Petya are friends because their messages' sending times are one second apart. Anya and Ivan are not, because their messages' sending times differ by more than one second.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N integers A_1, A_2, ..., A_N.
There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 2 \times 10^5
 - 1 \leq K \leq \frac{N(N-1)}{2}
 - -10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 \dots A_N

-----Output-----
Print the answer.

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

-----Sample Output-----
-6

There are six ways to form a pair. The products of those pairs are 9, -12, -6, -12, -6, 8.
Sorting those numbers in ascending order, we have -12, -12, -6, -6, 8, 9. The third number in this list is -6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Create a function that takes a Number as its argument and returns a Chinese numeral string. You don't need to validate the input argument, it will always be a Number in the range `[-99999.999, 99999.999]`, rounded to 8 decimal places.

Simplified Chinese numerals have characters representing each number from 0 to 9 and additional numbers representing larger numbers like 10, 100, 1000, and 10000. 

```
0 líng 零
1 yī 一
2 èr 二
3 sān 三
4 sì 四
5 wǔ 五
6 liù 六
7 qī 七
8 bā 八
9 jiǔ 九
10 shí 十
100 bǎi 百
1000 qiān 千
10000 wàn 万
```

Multiple-digit numbers are constructed by first the digit value (1 to 9) and then the place multiplier (such as 10, 100, 1000), starting with the most significant digit. A special case is made for 10 - 19 where the leading digit value (yī 一) is dropped. Note that this special case is only made for the actual values 10 - 19, not any larger values.

```
10 十
11 十一
18 十八
21 二十一
110 一百一十
123 一百二十三
24681 二万四千六百八十一
```

Trailing zeros are omitted, but interior zeros are grouped together and indicated by a single 零 character without giving the place multiplier.

```
10 十
20 二十
104 一百零四
1004 一千零四
10004 一万零四
10000 一万
```

Decimal numbers are constructed by first writing the whole number part, and then inserting a point (diǎn 点), followed by the decimal portion. The decimal portion is expressed using only the digits 0 to 9, without any positional characters and without grouping zeros.

```
0.1 零点一
123.45 一百二十三点四五
```

Negative numbers are the same as other numbers, but add a 负 (fù) before the number.

For more information, please see http://en.wikipedia.org/wiki/Chinese_numerals.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks n integers a_1, a_2, ..., a_{n} are good.

Now she is interested in good sequences. A sequence x_1, x_2, ..., x_{k} is called good if it satisfies the following three conditions:  The sequence is strictly increasing, i.e. x_{i} < x_{i} + 1 for each i (1 ≤ i ≤ k - 1).  No two adjacent elements are coprime, i.e. gcd(x_{i}, x_{i} + 1) > 1 for each i (1 ≤ i ≤ k - 1) (where gcd(p, q) denotes the greatest common divisor of the integers p and q).  All elements of the sequence are good integers. 

Find the length of the longest good sequence.


-----Input-----

The input consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of good integers. The second line contains a single-space separated list of good integers a_1, a_2, ..., a_{n} in strictly increasing order (1 ≤ a_{i} ≤ 10^5; a_{i} < a_{i} + 1).


-----Output-----

Print a single integer — the length of the longest good sequence.


-----Examples-----
Input
5
2 3 4 6 9

Output
4

Input
9
1 2 3 5 6 7 8 9 10

Output
4



-----Note-----

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today is Chef's birthday. His mom decided to surprise him with a truly fantastic gift: his favourite binary string B. But, unfortunately, all the stocks of binary string B have been sold out, and only a binary string A (A ≠ B) is available in the market.
She purchases the string A and tries to convert it to string B by applying any of following three operations zero or more times.
AND Operation:
She will choose a pair of indices i and j such that i != j and perform following sequence of operations.

-  result = Ai & Aj 
-  Ai = result & Ai 
-  Aj = result & Aj 

OR Operation:
She will choose a pair of indices i and j such that i != j and perform following sequence of operations.

-  result = Ai | Aj 
-  Ai = result | Ai 
-  Aj = result | Aj 

XOR Operation:
She will choose a pair of indices i and j such that i != j and perform following sequence of operations.

-  result = Ai ^ Aj 
-  Ai = result ^ Ai 
-  Aj = result ^ Aj 

Chef's mom is eagerly waiting to surprise him with his favourite gift and therefore, she wants to convert string A to string B as fast as possible. Can you please help her by telling her the minimum number of operations she will require? If it is impossible to do so, then let Chef's mom know about it.

-----Input-----
First line of input contains a single integer T denoting the number of test cases. T test cases follow.
First line of each test case, will contain binary string A.
Second line of each test case, will contain binary string B.

-----Output-----
For each test case, Print "Lucky Chef" (without quotes) in first line and minimum number of operations required to convert string A to sting B in second line if conversion is possible. Print "Unlucky Chef" (without quotes) in a new line otherwise.

-----Constraints-----
- 1 ≤ T ≤ 105
- 1 ≤ |A| ≤ 106
- 1 ≤ |B| ≤ 106
- A != B
- |A| = |B|
- sum of |A| over all test cases does not exceed 106
- sum of |B| over all test cases does not exceed 106

-----Subtasks-----
-  Subtask #1 (40 points) : Sum of |A| & |B| over all test cases does not exceed 103
-  Subtask #2 (60 points) : Sum of |A| & |B| over all test cases does not exceed 106

-----Example-----
Input
2
101
010
1111
1010
Output
Lucky Chef
2
Unlucky Chef

-----Explanation-----
Example case 1.
- Applying XOR operation with indices i = 1 and j = 2. Resulting string will be 011.
- Then, Applying AND operation with indices i = 1 and j = 3. Resulting string will be 010.

Example case 2.
- It is impossible to convert string A to string B.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp is going to participate in the contest. It starts at $h_1:m_1$ and ends at $h_2:m_2$. It is guaranteed that the contest lasts an even number of minutes (i.e. $m_1 \% 2 = m_2 \% 2$, where $x \% y$ is $x$ modulo $y$). It is also guaranteed that the entire contest is held during a single day. And finally it is guaranteed that the contest lasts at least two minutes.

Polycarp wants to know the time of the midpoint of the contest. For example, if the contest lasts from $10:00$ to $11:00$ then the answer is $10:30$, if the contest lasts from $11:10$ to $11:12$ then the answer is $11:11$.


-----Input-----

The first line of the input contains two integers $h_1$ and $m_1$ in the format hh:mm.

The second line of the input contains two integers $h_2$ and $m_2$ in the same format (hh:mm).

It is guaranteed that $0 \le h_1, h_2 \le 23$ and $0 \le m_1, m_2 \le 59$.

It is guaranteed that the contest lasts an even number of minutes (i.e. $m_1 \% 2 = m_2 \% 2$, where $x \% y$ is $x$ modulo $y$). It is also guaranteed that the entire contest is held during a single day. And finally it is guaranteed that the contest lasts at least two minutes.


-----Output-----

Print two integers $h_3$ and $m_3$ ($0 \le h_3 \le 23, 0 \le m_3 \le 59$) corresponding to the midpoint of the contest in the format hh:mm. Print each number as exactly two digits (prepend a number with leading zero if needed), separate them with ':'.


-----Examples-----
Input
10:00
11:00

Output
10:30

Input
11:10
11:12

Output
11:11

Input
01:02
03:02

Output
02:02

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Victoria is splurging on expensive accessories at her favorite stores. Each store stocks $\mbox{A}$ types of accessories, where the $i^{\mbox{th}}$ accessory costs $\boldsymbol{i}$ dollars ($1\leq i\leq A$). Assume that an item's type identifier is the same as its cost, and the store has an unlimited supply of each accessory.

Victoria wants to purchase a total of $L$ accessories according to the following rule:

Any $N$-element subset of the purchased items must contain at least $\mbox{D}$ different types of accessories. 

For example, if $L=6$, $N=3$, and $D=2$, then she must choose $\boldsymbol{6}$ accessories such that any subset of $3$ of the $\boldsymbol{6}$ accessories will contain at least $2$ distinct types of items. 

Given $L$, $\mbox{A}$, $N$, and $\mbox{D}$ values for $\mathbf{T}$ shopping trips, find and print the maximum amount of money that Victoria can spend during each trip; if it's not possible for Victoria to make a purchase during a certain trip, print SAD instead. You must print your answer for each trip on a new line.

Input Format

The first line contains an integer, $\mathbf{T}$, denoting the number of shopping trips. 

Each of the $\mathbf{T}$ subsequent lines describes a single shopping trip as four space-separated integers corresponding to $L$, $\mbox{A}$, $N$, and $\mbox{D}$, respectively.

Constraints

$1\leq T\leq10^6$  
$1\leq D\leq N\leq L\leq10^5$  
$1\leq A\leq10^9$  
The sum of the $L$'s for all $\mathbf{T}$ shopping trips $\leq8\cdot10^{6}$.  

Output Format

For each shopping trip, print a single line containing either the maximum amount of money Victoria can spend; if there is no collection of items satisfying her shopping rule for the trip's $L$, $\mbox{A}$, $N$, and $\mbox{D}$ values, print SAD instead.

Sample Input
2
6 5 3 2
2 1 2 2

Sample Output
24
SAD

Explanation

Shopping Trip 1: 

We know that:

Victoria wants to buy $L=6$ accessories. 
The store stocks the following $A=5$ types of accessories: $\{1,2,3,4,5\}$. 
For any grouping of $N=3$ of her $L$ accessories, there must be at least $D=2$ distinct types of accessories.  

Victoria can satisfy her shopping rule and spend the maximum amount of money by purchasing the following set of accessories: $\{3,4,5,5,4,3\}$. The total cost is $3+4+5+5+4+3=24$, so we print $24$ on a new line.

Shopping Trip 2: 

We know that:

Victoria wants to buy $L=2$ accessories.
The store stocks $A=1$ type of accessory: $\{1\}$. 
For any grouping of $N=2$ of her $L$ accessories, there must be at least $D=2$ distinct types of accessories. 

Because the store only carries $1$ type of accessory, Victoria cannot make a purchase satisfying the constraint that there be at least $D=2$ distinct types of accessories. Because Victoria will not purchase anything, we print that she is SAD on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This task is very simple.You are given two string A and B and you have to find how many times you can form string B from string A. You are only allow to delete some character from string A and Change postion of characters .You are not allow to use same index character of A two times in the same string to form string B.

For example :- string A = aba  and string B=ab, 
             so we can form 2 string from A same as B
 two string are different if atleast one place you use differently indexed character from A.

 InputFirst line  of input will have no. test cases (T) and  each test case contain two strings A and B .
 Output  Number of time string B can form from A. Output become large so take module with 10^9+7.

Constraints
1 ≤ T ≤ 100 

1 ≤ |A| , |B| ≤10^6

String consist only lowercase letters 'a' to 'z'

SAMPLE INPUT
1
aba 
ab

SAMPLE OUTPUT
2

Explanation

for A= aba two string can be form first by delete 'a' at index 2 and second  by deleting 'a' at index 0 and then  replacing  position of a and b

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Insecure Inc. has decided to shift directions after a failed attempt at developing a new encryption standard. Their new effort is a password system used to hide a password inside another string of characters we denote as a message. However, it is important that the message has a certain property relative to the hidden password.

Let us assume that we denote the characters of the password as $ c_1 c_2 \ldots c_ P$ (although those characters need not be distinct). To be a valid message for the password, if you start from the beginning of the message and search for any character from the set $\{ c_1, \ldots , c_ P \} $, it must be that $c_1$ is the first that you find. Subsequently, if you continue looking from that point of the message for any character from the set $\{ c_2, \ldots , c_ P \} $, it must be that $c_2$ is the next that you find. Continuing in that manner, $c_3$ must be the next character from the set $\{ c_3, \ldots , c_ P\} $, and so on until reaching $c_ P$.

For example, if the password is ABC, then the string HAPPYBIRTHDAYCACEY is a valid message.
 - Notice that A is the first of the set $\{ $A, B, C$\} $ to appear in the message. (The initial H is not relevant.)
 - Following the A that was found, the next occurrence from the set $\{ $B, C$\} $ is B.
 - Following the B that was found, the next occurrence from the set $\{ $C$\} $ is indeed C.

 (Note that the A in DAY is not relevant, since we are only looking for a C at this point, and the additional A and C in CACEY are not relevant, because we have already completed the password with the first C.)

However, for the password ABC, the string TRAGICBIRTHDAYCACEY is not a valid message.
 - While the A is the first of the set $\{ $A, B, C$\} $ to appear in the string,

 the next occurrence from the set $\{ $B, C$\} $ is C rather than B.

Also, the string HAPPYBIRTHDAY is not a valid message for the password ABC because the C never appears.

As an example with duplicate letters in the password, consider the password SECRET. For this password, the string SOMECHORESARETOUGH is a valid message. In contrast, the string SOMECHEERSARETOUGH is not a valid message, because an extraneous E is found at the point when an R is first expected.

-----Input-----
The input consists of a single line containing two strings. The first string is the password, having length $P$, with $3 \leq P \leq 8$. The second string has length $S$, with $10 \leq S \leq 40$. Both strings will consist solely of uppercase letters. (That is, neither string can include whitespace, lowercase letters, digits, or other special characters.)

-----Output-----
Output a single line with the word PASS if the second string is a valid message for the password, or FAIL otherwise.



-----Examples-----
Sample Input 1:
ABC HAPPYBIRTHDAYCACEY
Sample Output 1:
PASS

Sample Input 2:
ABC TRAGICBIRTHDAYCACEY
Sample Output 2:
FAIL

Sample Input 3:
ABC HAPPYBIRTHDAY
Sample Output 3:
FAIL

Sample Input 4:
SECRET SOMECHORESARETOUGH
Sample Output 4:
PASS

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Author note: I think some of you might remember the problem "Two Melodies" from Eductational Codeforces Round 22. Now it's time to make it a bit more difficult!

Alice is a composer, and recently she had recorded two tracks that became very popular. Now she has got a lot of fans who are waiting for new tracks. 

This time Alice wants to form four melodies for her tracks.

Alice has a sheet with n notes written on it. She wants to take four such non-empty non-intersecting subsequences that all of them form a melody and sum of their lengths is maximal.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Subsequence forms a melody when each two adjacent notes either differ by 1 or are congruent modulo 7.

You should write a program which will calculate maximum sum of lengths of such four non-empty non-intersecting subsequences that all of them form a melody.

Input

The first line contains one integer number n (4 ≤ n ≤ 3000).

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 105) — notes written on a sheet.

Output

Print maximum sum of lengths of such four non-empty non-intersecting subsequences that all of them form a melody.

Examples

Input

5
1 3 5 7 9


Output

4


Input

5
1 3 5 7 2


Output

5

Note

In the first example it is possible to compose 4 melodies by choosing any 4 notes (and each melody will consist of only one note).

In the second example it is possible to compose one melody with 2 notes — {1, 2}. Remaining notes are used in other three melodies (one note per each melody).

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