vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Asterix, Obelix and their temporary buddies Suffix and Prefix has finally found the Harmony temple. However, its doors were firmly locked and even Obelix had no luck opening them.

A little later they found a string s, carved on a rock below the temple's gates. Asterix supposed that that's the password that opens the temple and read the string aloud. However, nothing happened. Then Asterix supposed that a password is some substring t of the string s.

Prefix supposed that the substring t is the beginning of the string s; Suffix supposed that the substring t should be the end of the string s; and Obelix supposed that t should be located somewhere inside the string s, that is, t is neither its beginning, nor its end.

Asterix chose the substring t so as to please all his companions. Besides, from all acceptable variants Asterix chose the longest one (as Asterix loves long strings). When Asterix read the substring t aloud, the temple doors opened. 

You know the string s. Find the substring t or determine that such substring does not exist and all that's been written above is just a nice legend.

Input

You are given the string s whose length can vary from 1 to 106 (inclusive), consisting of small Latin letters.

Output

Print the string t. If a suitable t string does not exist, then print "Just a legend" without the quotes.

Examples

Input

fixprefixsuffix


Output

fix

Input

abcdabc


Output

Just a legend

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
When users post an update on social media,such as a URL, image, status update etc., other users in their network are able to view this new post on their news feed. Users can also see exactly when the post was published, i.e, how many hours, minutes or seconds ago. 

Since sometimes posts are published and viewed in different time zones, this can be confusing. You are given two timestamps of one such post that a user can see on his newsfeed in the following format: 

Day dd Mon yyyy hh:mm:ss +xxxx

Here +xxxx represents the time zone. Your task is to print the absolute difference (in seconds) between them.  

Input Format

The first line contains $\mathbf{T}$, the number of testcases. 

Each testcase contains $2$ lines, representing time $\boldsymbol{t_1}$ and time $t_2$. 

Constraints

Input contains only valid timestamps
$year\:\leq3000$. 

Output Format

Print the absolute difference $(t_1-t_2)$ in seconds.  

Sample Input 0
2
Sun 10 May 2015 13:54:36 -0700
Sun 10 May 2015 13:54:36 -0000
Sat 02 May 2015 19:54:36 +0530
Fri 01 May 2015 13:54:36 -0000

Sample Output 0
25200
88200

Explanation 0

In the first query, when we compare the time in UTC for both the time stamps, we see a difference of 7 hours. which is $7\times3600$ seconds or $25200$ seconds.  

Similarly, in the second query, time difference is 5 hours and 30 minutes for time zone adjusting for that we have a difference of 1 day and 30 minutes. Or $24\times3600+30\times60\Rightarrow88200$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fans of The Wire will appreciate this one. 
For those that haven't seen the show, the Barksdale Organization has a simple method for encoding telephone numbers exchanged via pagers: "Jump to the other side of the 5 on the keypad, and swap 5's and 0's."

Here's a keypad for visualization.
```
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 4 │ 5 │ 6 │
├───┼───┼───┤
│ 7 │ 8 │ 9 │
└───┼───┼───┘
    │ 0 │
    └───┘
```

Detective, we're hot on their trail! We have a big pile of encoded messages here to use as evidence, but it would take way too long to decode by hand. Could you write a program to do this for us?


Write a funciton called decode(). Given an encoded string, return the actual phone number in string form. Don't worry about input validation, parenthesies, or hyphens.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of positive integers, replace every element with the least greater element to its right.
 If there is no greater element to its right, replace it with -1. For instance, given the array 
 
 `[8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28]`,
 
 the desired output is 
 
 `[18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1]`.

Your task is to create a function "arrayManip()" that takes in an array as its argument, manipulates the array as described above, then return the resulting array.

Note: Return a new array, rather than modifying the passed array.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sam has been teaching Jon the Game of Stones to sharpen his mind and help him devise a strategy to fight the white walkers. The rules of this game are quite simple:  The game starts with n piles of stones indexed from 1 to n. The i-th pile contains s_{i} stones. The players make their moves alternatively. A move is considered as removal of some number of stones from a pile. Removal of 0 stones does not count as a move. The player who is unable to make a move loses.

Now Jon believes that he is ready for battle, but Sam does not think so. To prove his argument, Sam suggested that they play a modified version of the game.

In this modified version, no move can be made more than once on a pile. For example, if 4 stones are removed from a pile, 4 stones cannot be removed from that pile again.

Sam sets up the game and makes the first move. Jon believes that Sam is just trying to prevent him from going to battle. Jon wants to know if he can win if both play optimally.


-----Input-----

First line consists of a single integer n (1 ≤ n ≤ 10^6) — the number of piles.

Each of next n lines contains an integer s_{i} (1 ≤ s_{i} ≤ 60) — the number of stones in i-th pile.


-----Output-----

Print a single line containing "YES" (without quotes) if Jon wins, otherwise print "NO" (without quotes)


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

Output
NO
Input
2
1
2

Output
YES


-----Note-----

In the first case, Sam removes all the stones and Jon loses.

In second case, the following moves are possible by Sam: $\{1,2 \} \rightarrow \{0,2 \}, \{1,2 \} \rightarrow \{1,0 \}, \{1,2 \} \rightarrow \{1,1 \}$ 

In each of these cases, last move can be made by Jon to win the game as follows: $\{0,2 \} \rightarrow \{0,0 \}, \{1,0 \} \rightarrow \{0,0 \}, \{1,1 \} \rightarrow \{0,1 \}$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Each floating-point number should be formatted that only the first two decimal places are returned. You don't need to check whether the input is a valid number because only valid numbers are used in the tests.  

Don't round the numbers! Just cut them after two decimal places!
```
Right examples:  
32.8493 is 32.84  
14.3286 is 14.32

Incorrect examples (e.g. if you round the numbers):  
32.8493 is 32.85  
14.3286 is 14.33
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this kata the function returns an array/list like the one passed to it but with its nth element removed (with `0 <= n <= array/list.length - 1`). The function is already written for you and the basic tests pass, but random tests fail. Your task is to figure out why and fix it.

Good luck!

~~~if:javascript
Some good reading: [MDN Docs about arrays](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array)
~~~
~~~if:python
Some good reading: [Python Docs about lists](https://docs.python.org/3/tutorial/datastructures.html)
~~~
~~~if:coffeescript
Some good reading: [CoffeeScript docs](http://coffeescript.org/)
~~~

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Crazy Town is a plane on which there are n infinite line roads. Each road is defined by the equation a_{i}x + b_{i}y + c_{i} = 0, where a_{i} and b_{i} are not both equal to the zero. The roads divide the plane into connected regions, possibly of infinite space. Let's call each such region a block. We define an intersection as the point where at least two different roads intersect.

Your home is located in one of the blocks. Today you need to get to the University, also located in some block. In one step you can move from one block to another, if the length of their common border is nonzero (in particular, this means that if the blocks are adjacent to one intersection, but have no shared nonzero boundary segment, then it are not allowed to move from one to another one in one step).

Determine what is the minimum number of steps you have to perform to get to the block containing the university. It is guaranteed that neither your home nor the university is located on the road.


-----Input-----

The first line contains two space-separated integers x_1, y_1 ( - 10^6 ≤ x_1, y_1 ≤ 10^6) — the coordinates of your home.

The second line contains two integers separated by a space x_2, y_2 ( - 10^6 ≤ x_2, y_2 ≤ 10^6) — the coordinates of the university you are studying at.

The third line contains an integer n (1 ≤ n ≤ 300) — the number of roads in the city. The following n lines contain 3 space-separated integers ( - 10^6 ≤ a_{i}, b_{i}, c_{i} ≤ 10^6; |a_{i}| + |b_{i}| > 0) — the coefficients of the line a_{i}x + b_{i}y + c_{i} = 0, defining the i-th road. It is guaranteed that no two roads are the same. In addition, neither your home nor the university lie on the road (i.e. they do not belong to any one of the lines).


-----Output-----

Output the answer to the problem.


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

Output
2

Input
1 1
-1 -1
3
1 0 0
0 1 0
1 1 -3

Output
2



-----Note-----

Pictures to the samples are presented below (A is the point representing the house; B is the point representing the university, different blocks are filled with different colors): [Image]  [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imagine that you are given two sticks. You want to end up with three sticks of equal length. You are allowed to cut either or both of the sticks to accomplish this, and can throw away leftover pieces.

Write a function, maxlen, that takes the lengths of the two sticks (L1 and L2, both positive values), that will return the maximum length you can make the three sticks.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Arjit is the leader of a marvellous fighting army. His team is very good at fighting against all their enemies. But like Hound from Game of Thrones, Little Arjit and his entire team is scared of fire. When they see fire, they feel threatened, and scared like a little child, and don’t even mind giving up from a fight.

Now, you’re given the location of the army men of Little Arjit, their enemies, and fire in a pathway. You’ve got to figure out how many enemies will survive after the massacre done by Little Arjit and his army.

Let’s say Little Arjit and his army is denoted by ‘X’, all their enemies are denoted by ‘O’, and fire is denoted as ‘*’ 

Here’s what happens:

When a X faces an O, i.e., when X is adjacent to O, X kills O. Always. Whenever there will be an O adjacent to  X  ,X will kill O .
The moment X faces a *, he stops, and he cannot move any further.

Given a string containing X, O, * - can you help Little Arjit figure out how many of his enemies will still survive this attack because of fire?

Input:
First line of input contains a integer T,number of test cases. Next T lines contains a single string S.   

Output:
For each test case print number of enemies survive after attack.

Constraints: 
1 ≤ T ≤ 30
1 ≤ |S| ≤ 100000

SAMPLE INPUT
3
X*OO*XX
X*OX*XO*
X*OO*OO*X*OX*

SAMPLE OUTPUT
2
0
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kolya got an integer array $a_1, a_2, \dots, a_n$. The array can contain both positive and negative integers, but Kolya doesn't like $0$, so the array doesn't contain any zeros.

Kolya doesn't like that the sum of some subsegments of his array can be $0$. The subsegment is some consecutive segment of elements of the array. 

You have to help Kolya and change his array in such a way that it doesn't contain any subsegments with the sum $0$. To reach this goal, you can insert any integers between any pair of adjacent elements of the array (integers can be really any: positive, negative, $0$, any by absolute value, even such a huge that they can't be represented in most standard programming languages).

Your task is to find the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum $0$.


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 200\,000$) — the number of elements in Kolya's array.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^{9} \le a_i \le 10^{9}, a_i \neq 0$) — the description of Kolya's array.


-----Output-----

Print the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum $0$.


-----Examples-----
Input
4
1 -5 3 2

Output
1

Input
5
4 -2 3 -9 2

Output
0

Input
9
-1 1 -1 1 -1 1 1 -1 -1

Output
6

Input
8
16 -5 -11 -15 10 5 4 -4

Output
3



-----Note-----

Consider the first example. There is only one subsegment with the sum $0$. It starts in the second element and ends in the fourth element. It's enough to insert one element so the array doesn't contain any subsegments with the sum equal to zero. For example, it is possible to insert the integer $1$ between second and third elements of the array.

There are no subsegments having sum $0$ in the second example so you don't need to do anything.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko and Slavko are playing a new game. Again. Slavko starts each round by giving Mirko two numbers $A$ and $B$, both smaller than 100. Mirko then has to slove the following task for Slavko: how to pair all given $A$ numbers with all given $B$ numbers so that the maximal sum of such pairs is as small as possible.

In other words, if during previous rounds Slavko gave numbers $a_1, a_2 ,a_3, \ldots , a_ n$ and $b_1, b_2, b_3, \ldots , b_ n$ , determine $n$ pairings $(a_ i, b_ j)$ such that each number in the $A$ sequence is used in exactly one pairing, each number in the $B$ sequence is used in exactly one pairing, and the maximum of all sums $a_ i + b_ j$ is minimal.

-----Input-----
The first line of input contains a single integer $N$ ($1 \leq N \leq 100000$), the number of rounds.

The next $N$ lines contain two integers $A$ and $B$ ($1 \leq A, B \leq 100$), the numbers given by Slavko in that round.

-----Output-----
The output consists of $N$ lines, one for each round. Each line should contain the smallest maximal sum for that round.

-----Examples-----
Sample Input:
3
2 8
3 1
1 4
Sample Output:
10
10
9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko has an array of $N$ different words that he wants to encrypt using a substitution cypher.

We encrypt the text using a substitution cypher by first choosing a key – a permutation of the English alphabet. Then we replace all occurrences of letter ‘a’ with the first letter of the key, all occurrences of letter ‘b’ with the second letter of the key, and so on until letter ‘z’.

Besides the words, Mirko has an array $A$ consisting of numbers from $1$ to $N$ given in a certain order (in other words, array $A$ is a permutation of numbers from $1$ to $N$). Mirko wants to pick a key such that the array of words after encrypting and lexicographic sorting corresponds to array $A$. More precisely, he wants the word initially located at $A_ i$ to be at location $i$ after encryption and sorting.

Let’s recall that the lexicographic word order is the order in which the words appear in the dictionary. If we are comparing two words, going from left to right, we search for the first position in both words where the letters differ and, based on that, we determine which word is lexicographically smaller. If word $X$ is the beginning of the word $Y$, then word $X$ is lexicographically smaller than word $Y$.

Mirko is currently not in the mood for encrypting, so he kindly asks you to do it for him.

-----Input-----
The first line of input contains the integer $N$ ($2 \leq N \leq 100$). Each of the following $N$ lines contains a single word that consists of at most $100$ lowercase letters of the English alphabet. The words will be mutually distinct. The last line contains $N$ integers – the elements of array $A$.

-----Output-----
In the case when a solution doesn’t exist, output “NE”. Otherwise, output “DA” in the first line, and in the second line output a word consisting of $26$ different letters of the English alphabet – the key for the substitution cipher. If multiple solutions exist, output any.

-----Examples-----
Sample Input 1:
2
ab
bc
2 1
Sample Output 1:
DA
bacdefghijklmnopqrstuvwxyz

Sample Input 2:
3
abc
bcd
add
1 2 3
Sample Output 2:
NE

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A and B are preparing themselves for programming contests.

An important part of preparing for a competition is sharing programming knowledge from the experienced members to those who are just beginning to deal with the contests. Therefore, during the next team training A decided to make teams so that newbies are solving problems together with experienced participants.

A believes that the optimal team of three people should consist of one experienced participant and two newbies. Thus, each experienced participant can share the experience with a large number of people.

However, B believes that the optimal team should have two experienced members plus one newbie. Thus, each newbie can gain more knowledge and experience.

As a result, A and B have decided that all the teams during the training session should belong to one of the two types described above. Furthermore, they agree that the total number of teams should be as much as possible.

There are n experienced members and m newbies on the training session. Can you calculate what maximum number of teams can be formed?


-----Input-----

The first line contains two integers n and m (0 ≤ n, m ≤ 5·10^5) — the number of experienced participants and newbies that are present at the training session. 


-----Output-----

Print the maximum number of teams that can be formed.


-----Examples-----
Input
2 6

Output
2

Input
4 5

Output
3



-----Note-----

Let's represent the experienced players as XP and newbies as NB.

In the first test the teams look as follows: (XP, NB, NB), (XP, NB, NB).

In the second test sample the teams look as follows: (XP, NB, NB), (XP, NB, NB), (XP, XP, NB).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Cherry has a string S$S$ consisting of lowercase English letters. Using this string, he formed a pyramid of infinite length with certain rules:
- N$N$-th row of pyramid contains N$N$ characters.
- Each row of pyramid begins with the first character of the string.
- The subsequent characters of the row are appended to the string in cyclic fashion, until the size of string for that Row is reached (See example pyramid for better understanding).
He has another string T$T$ of smaller (or equal) size.
You are asked Q$Q$ queries. Each query is provided with a row number N$N$. The answer to the query is number of occurrences of string T$T$ in that particular row of pyramid. No of occurrences of String T$T$ in a string V$V$ would mean that you'd need to find number of substrings Vi,Vi+1...Vj$V_i, V_{i+1} ... V_j$ which are equal to String T$T$, where i≤j$i \leq j$.
For eg: If the string is code, then the pyramid will be of the form:
c
co
cod
code
codec
codeco
codecod
codecode
codecodec
codecodeco
...

-----Input:-----
- The first line contains string S$S$ — consisting of lowercase English letters.
- The second line contains string T$T$ — consisting of lowercase English letters.
- Next line contains an integer Q$Q$ — the number of queries.
- Then follow Q$Q$ lines with queries descriptions. Each of them contains a single integer N$N$ denoting the row number of pyramid.

-----Output:-----
- Print Q$Q$ lines. The i$i$-th of them should contain a integer denoting occurrences of string T$T$ in that particular row.

-----Constraints-----
- 1≤|S|≤105$1 \leq |S| \leq 10^5$
- 1≤|T|≤|S|$1 \leq |T| \leq |S|$
- 1≤Q≤105$1 \leq Q \leq 10^5$
- 1≤N≤109$1 \leq N \leq 10^9$

-----Sample Input:-----
codechef
chefcode
3
4
12
1455

-----Sample Output:-----
0
1
181

-----Explanation:-----
Pyramid will be formed as explained in the statement.
Query 1: Row number 4 of the pyramid is code. The number of occurrences of chefcode in code is 0.
Query 2: Row number 12 of the pyramid is codechefcode. The number of occurrences of chefcode in codechefcode is 1.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
When Valera has got some free time, he goes to the library to read some books. Today he's got *t* free minutes to read. That's why Valera took *n* books in the library and for each book he estimated the time he is going to need to read it. Let's number the books by integers from 1 to *n*. Valera needs *a**i* minutes to read the *i*-th book.

Valera decided to choose an arbitrary book with number *i* and read the books one by one, starting from this book. In other words, he will first read book number *i*, then book number *i*<=+<=1, then book number *i*<=+<=2 and so on. He continues the process until he either runs out of the free time or finishes reading the *n*-th book. Valera reads each book up to the end, that is, he doesn't start reading the book if he doesn't have enough free time to finish reading it. 

Print the maximum number of books Valera can read.

Input Specification:
The first line contains two integers *n* and *t* (1<=≤<=*n*<=≤<=105; 1<=≤<=*t*<=≤<=109) — the number of books and the number of free minutes Valera's got. The second line contains a sequence of *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=104), where number *a**i* shows the number of minutes that the boy needs to read the *i*-th book.

Output Specification:
Print a single integer — the maximum number of books Valera can read.

Demo Input:
['4 5\n3 1 2 1\n', '3 3\n2 2 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.