vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Saitama Destroys Hotel

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Saitama accidentally destroyed a hotel again. To repay the hotel company, Genos has volunteered to operate an elevator in one of its other hotels. The elevator is special — it starts on the top floor, can only move down, and has infinite capacity. Floors are numbered from 0 to *s* and elevator initially starts on floor *s* at time 0.

The elevator takes exactly 1 second to move down exactly 1 floor and negligible time to pick up passengers. Genos is given a list detailing when and on which floor passengers arrive. Please determine how long in seconds it will take Genos to bring all passengers to floor 0.

Input Specification:
The first line of input contains two integers *n* and *s* (1<=≤<=*n*<=≤<=100, 1<=≤<=*s*<=≤<=1000) — the number of passengers and the number of the top floor respectively.

The next *n* lines each contain two space-separated integers *f**i* and *t**i* (1<=≤<=*f**i*<=≤<=*s*, 1<=≤<=*t**i*<=≤<=1000) — the floor and the time of arrival in seconds for the passenger number *i*.

Output Specification:
Print a single integer — the minimum amount of time in seconds needed to bring all the passengers to floor 0.

Demo Input:
['3 7\n2 1\n3 8\n5 2\n', '5 10\n2 77\n3 33\n8 21\n9 12\n10 64\n']

Demo Output:
['11\n', '79\n']

Note:
In the first sample, it takes at least 11 seconds to bring all passengers to floor 0. Here is how this could be done:

1. Move to floor 5: takes 2 seconds.

2. Pick up passenger 3.

3. Move to floor 3: takes 2 seconds.

4. Wait for passenger 2 to arrive: takes 4 seconds.

5. Pick up passenger 2.

6. Go to floor 2: takes 1 second.

7. Pick up passenger 1.

8. Go to floor 0: takes 2 seconds.

This gives a total of 2 + 2 + 4 + 1 + 2 = 11 seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?


Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:


Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right


Example 2:


Input: m = 7, n = 3
Output: 28

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Create a program that reads poker hand data and outputs the role for each. However, this issue follows the rules below.

* Poker is a competition with 5 playing cards.
* No more than 5 cards with the same number.
* There is no joker.
* Suppose you only consider the following poker roles: (The higher the number, the higher the role.)


1. No role (does not apply to any of the following)
2. One pair (two cards with the same number)
3. Two pairs (two pairs of cards with the same number)
4. Three cards (one set of three cards with the same number)
5. Straight (the numbers on 5 cards are consecutive)
However, in the case of a straight containing A, the sequence ending with A is also straight. In other words, there are two types of straights containing A: A 2 3 4 5 and 10 J Q K A. Lines that straddle A, such as J Q K A 2, are not straight. (In this case, it will be "no role").
6. Full House (one set of three cards with the same number and the other two cards with the same number)
7. Four Cards (one set of four cards with the same number)



Input

The input consists of multiple datasets. Each dataset is given in the following format:


Hand 1, Hand 2, Hand 3, Hand 4, Hand 5


In your hand, Trump's J (jack) is 11, Q (queen) is 12, K (king) is 13, A (ace) is 1, and the others are represented by their respective numbers.

The number of datasets does not exceed 50.

Output

For each dataset, output one of the highest roles you can play in your hand. Follow the output example for the notation of the role.

Example

Input

1,2,3,4,1
2,3,2,3,12
12,13,11,12,12
7,6,7,6,7
3,3,2,3,3
6,7,8,9,10
11,12,10,1,13
11,12,13,1,2


Output

one pair
two pair
three card
full house
four card
straight
straight
null

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ronald's uncle left him 3 fertile chickens in his will. When life gives you chickens, you start a business selling chicken eggs which is exactly what Ronald decided to do. 

A chicken lays 300 eggs in its first year. However, each chicken's egg production decreases by 20% every following year (rounded down) until when it dies (after laying its quota of eggs). 

After his first successful year of business, Ronald decides to buy 3 more chickens at the start of each year.  


Your Task: 

For a given year, and life span of chicken span,  calculate how many eggs Ronald's chickens will lay him that year, whereby year=1 is when Ronald first got his inheritance and span>0.

If year=0, make sure to return "No chickens yet!".


Note: 
1. All chickens have the same life span regardless of when they are bought. 
2. Let's assume all calculations are made at the end of the year so don't bother taking eggs laid per month into consideration. 
3. Each chicken's egg production goes down by 20% each year, NOT the total number of eggs produced by each 'batch' of chickens. While this might appear to be the same thing, it doesn't once non-integers come into play so take care that this is reflected in your kata!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Remember the game 2048?

The main part of this game is merging identical tiles in a row. 

* Implement a function that models the process of merging all of the tile values in a single row.  
* This function takes the array line as a parameter and returns a new array with the tile values from line slid towards the front of the array (index 0) and merged.
* A given tile can only merge once.
* Empty grid squares are represented as zeros.
* Your function should work on arrays containing arbitrary number of elements.


## Examples

```
merge([2,0,2,2])  -->  [4,2,0,0]
```

Another example with repeated merges: 

```
merge([4,4,8,16])  -->  [8,8,16,0]
merge([8,8,16,0])  -->  [16,16,0,0]
merge([16,16,0,0]) -->  [32,0,0,0]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Igor K. stopped programming and took up math. One late autumn evening he was sitting at a table reading a book and thinking about something. 

The following statement caught his attention: "Among any six people there are either three pairwise acquainted people or three pairwise unacquainted people"

Igor just couldn't get why the required minimum is 6 people. "Well, that's the same for five people, too!" — he kept on repeating in his mind. — "Let's take, say, Max, Ilya, Vova — here, they all know each other! And now let's add Dima and Oleg to Vova — none of them is acquainted with each other! Now, that math is just rubbish!"

Igor K. took 5 friends of his and wrote down who of them is friends with whom. Now he wants to check whether it is true for the five people that among them there are either three pairwise acquainted or three pairwise not acquainted people.

Input

The first line contains an integer m (0 ≤ m ≤ 10), which is the number of relations of acquaintances among the five friends of Igor's.

Each of the following m lines contains two integers ai and bi (1 ≤ ai, bi ≤ 5;ai ≠ bi), where (ai, bi) is a pair of acquainted people. It is guaranteed that each pair of the acquaintances is described exactly once. The acquaintance relation is symmetrical, i.e. if x is acquainted with y, then y is also acquainted with x.

Output

Print "FAIL", if among those five people there are no either three pairwise acquainted or three pairwise unacquainted people. Otherwise print "WIN".

Examples

Input

4
1 3
2 3
1 4
5 3


Output

WIN


Input

5
1 2
2 3
3 4
4 5
5 1


Output

FAIL

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function which reduces fractions to their simplest form! Fractions will be presented as an array/tuple (depending on the language), and the reduced fraction must be returned as an array/tuple:

```
input:   [numerator, denominator]
output:  [newNumerator, newDenominator]
example: [45, 120] --> [3, 8]
```

All numerators and denominators will be positive integers.

Note: This is an introductory Kata for a series... coming soon!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob is playing with $6$-sided dice. A net of such standard cube is shown below.

[Image]

He has an unlimited supply of these dice and wants to build a tower by stacking multiple dice on top of each other, while choosing the orientation of each dice. Then he counts the number of visible pips on the faces of the dice.

For example, the number of visible pips on the tower below is $29$ — the number visible on the top is $1$, from the south $5$ and $3$, from the west $4$ and $2$, from the north $2$ and $4$ and from the east $3$ and $5$.

[Image]

The one at the bottom and the two sixes by which the dice are touching are not visible, so they are not counted towards total.

Bob also has $t$ favourite integers $x_i$, and for every such integer his goal is to build such a tower that the number of visible pips is exactly $x_i$. For each of Bob's favourite integers determine whether it is possible to build a tower that has exactly that many visible pips.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of favourite integers of Bob. 

The second line contains $t$ space-separated integers $x_i$ ($1 \leq x_i \leq 10^{18}$) — Bob's favourite integers.


-----Output-----

For each of Bob's favourite integers, output "YES" if it is possible to build the tower, or "NO" otherwise (quotes for clarity).


-----Example-----
Input
4
29 34 19 38

Output
YES
YES
YES
NO



-----Note-----

The first example is mentioned in the problem statement.

In the second example, one can build the tower by flipping the top dice from the previous tower.

In the third example, one can use a single die that has $5$ on top.

The fourth example is impossible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petr is a detective in Braginsk. Somebody stole a huge amount of money from a bank and Petr is to catch him. Somebody told Petr that some luxurious car moves along the roads without stopping.

Petr knows that it is the robbers who drive the car. The roads in Braginsk are one-directional and each of them connects two intersections. Petr wants to select one intersection such that if the robbers continue to drive the roads indefinitely, they will sooner or later come to that intersection. The initial position of the robbers is unknown. Find such an intersection that fits the requirements.

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 10^5, 2 ≤ m ≤ 5 ⋅ 10^5) — the number of intersections and the number of directed roads in Braginsk, respectively.

Each of the next m lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) — the start and finish of the i-th directed road. It is guaranteed that the robbers can move along the roads indefinitely.

Output

Print a single integer k — the intersection Petr needs to choose. If there are multiple answers, print any. If there are no such intersections, print -1.

Examples

Input

5 6
1 2
2 3
3 1
3 4
4 5
5 3


Output

3

Input

3 3
1 2
2 3
3 1


Output

1

Note

In the first example the robbers can move, for example, along the following routes: (1-2-3-1), (3-4-5-3), (1-2-3-4-5-3-1). We can show that if Petr chooses the 3-rd intersection, he will eventually meet the robbers independently of their route.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A robber has attempted to rob a bank but failed to complete his task. However, he had managed to open all the safes.

Oleg the bank client loves money (who doesn't), and decides to take advantage of this failed robbery and steal some money from the safes. There are many safes arranged in a line, where the *i*-th safe from the left is called safe *i*. There are *n* banknotes left in all the safes in total. The *i*-th banknote is in safe *x**i*. Oleg is now at safe *a*. There are two security guards, one of which guards the safe *b* such that *b*<=&lt;<=*a*, i.e. the first guard is to the left of Oleg. The other guard guards the safe *c* so that *c*<=&gt;<=*a*, i.e. he is to the right of Oleg.

The two guards are very lazy, so they do not move. In every second, Oleg can either take all the banknotes from the current safe or move to any of the neighboring safes. However, he cannot visit any safe that is guarded by security guards at any time, becaues he might be charged for stealing. Determine the maximum amount of banknotes Oleg can gather.

Input Specification:
The first line of input contains three space-separated integers, *a*, *b* and *c* (1<=≤<=*b*<=&lt;<=*a*<=&lt;<=*c*<=≤<=109), denoting the positions of Oleg, the first security guard and the second security guard, respectively.

The next line of input contains a single integer *n* (1<=≤<=*n*<=≤<=105), denoting the number of banknotes.

The next line of input contains *n* space-separated integers *x*1,<=*x*2,<=...,<=*x**n* (1<=≤<=*x**i*<=≤<=109), denoting that the *i*-th banknote is located in the *x**i*-th safe. Note that *x**i* are not guaranteed to be distinct.

Output Specification:
Output a single integer: the maximum number of banknotes Oleg can take.

Demo Input:
['5 3 7\n8\n4 7 5 5 3 6 2 8\n', '6 5 7\n5\n1 5 7 92 3\n']

Demo Output:
['4\n', '0\n']

Note:
In the first example Oleg can take the banknotes in positions 4, 5, 6 (note that there are 2 banknotes at position 5). Oleg can't take the banknotes in safes 7 and 8 because he can't run into the second security guard. Similarly, Oleg cannot take the banknotes at positions 3 and 2 because he can't run into the first security guard. Thus, he can take a maximum of 4 banknotes.

For the second sample, Oleg can't take any banknotes without bumping into any of the security guards.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp has $n$ coins, the value of the $i$-th coin is $a_i$. It is guaranteed that all the values are integer powers of $2$ (i.e. $a_i = 2^d$ for some non-negative integer number $d$).

Polycarp wants to know answers on $q$ queries. The $j$-th query is described as integer number $b_j$. The answer to the query is the minimum number of coins that is necessary to obtain the value $b_j$ using some subset of coins (Polycarp can use only coins he has). If Polycarp can't obtain the value $b_j$, the answer to the $j$-th query is -1.

The queries are independent (the answer on the query doesn't affect Polycarp's coins).

Input Specification:
The first line of the input contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of coins and the number of queries.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ — values of coins ($1 \le a_i \le 2 \cdot 10^9$). It is guaranteed that all $a_i$ are integer powers of $2$ (i.e. $a_i = 2^d$ for some non-negative integer number $d$).

The next $q$ lines contain one integer each. The $j$-th line contains one integer $b_j$ — the value of the $j$-th query ($1 \le b_j \le 10^9$).

Output Specification:
Print $q$ integers $ans_j$. The $j$-th integer must be equal to the answer on the $j$-th query. If Polycarp can't obtain the value $b_j$ the answer to the $j$-th query is -1.

Demo Input:
['5 4\n2 4 8 2 4\n8\n5\n14\n10\n']

Demo Output:
['1\n-1\n3\n2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A positive integer number n is written on a blackboard. It consists of not more than 105 digits. You have to transform it into a beautiful number by erasing some of the digits, and you want to erase as few digits as possible.

The number is called beautiful if it consists of at least one digit, doesn't have leading zeroes and is a multiple of 3. For example, 0, 99, 10110 are beautiful numbers, and 00, 03, 122 are not.

Write a program which for the given n will find a beautiful number such that n can be transformed into this number by erasing as few digits as possible. You can erase an arbitraty set of digits. For example, they don't have to go one after another in the number n.

If it's impossible to obtain a beautiful number, print -1. If there are multiple answers, print any of them.

Input

The first line of input contains n — a positive integer number without leading zeroes (1 ≤ n < 10100000).

Output

Print one number — any beautiful number obtained by erasing as few as possible digits. If there is no answer, print  - 1.

Examples

Input

1033


Output

33


Input

10


Output

0


Input

11


Output

-1

Note

In the first example it is enough to erase only the first digit to obtain a multiple of 3. But if we erase the first digit, then we obtain a number with a leading zero. So the minimum number of digits to be erased is two.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has a pepperoni pizza in the shape of a $N \times N$ grid; both its rows and columns are numbered $1$ through $N$. Some cells of this grid have pepperoni on them, while some do not. Chef wants to cut the pizza vertically in half and give the two halves to two of his friends. Formally, one friend should get everything in the columns $1$ through $N/2$ and the other friend should get everything in the columns $N/2+1$ through $N$.
Before doing that, if Chef wants to, he may choose one row of the grid and reverse it, i.e. swap the contents of the cells in the $i$-th and $N+1-i$-th column in this row for each $i$ ($1 \le i \le N/2$).
After the pizza is cut, let's denote the number of cells containing pepperonis in one half by $p_1$ and their number in the other half by $p_2$. Chef wants to minimise their absolute difference. What is the minimum value of $|p_1-p_2|$?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains a string with length $N$ describing the $i$-th row of the grid; this string contains only characters '1' (denoting a cell with pepperonis) and '0' (denoting a cell without pepperonis).

-----Output-----
For each test case, print a single line containing one integer — the minimum absolute difference between the number of cells with pepperonis in the half-pizzas given to Chef's friends.

-----Constraints-----
- $1 \le T \le 1,000$
- $2 \le N \le 1,000$
- $N$ is even
- the sum of $N \cdot N$ over all test cases does not exceed $2 \cdot 10^6$

-----Example Input-----
2
6
100000
100000
100000
100000
010010
001100
4
0011
1100
1110
0001

-----Example Output-----
2
0

-----Explanation-----
Example case 1: Initially, $|p_1-p_2| = 4$, but if Chef reverses any one of the first four rows from "100000" to "000001", $|p_1-p_2|$ becomes $2$.
Example case 2: Initially, $|p_1-p_2| = 0$. We cannot make that smaller by reversing any row.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Strange Game On Matrix

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ivan is playing a strange game.

He has a matrix *a* with *n* rows and *m* columns. Each element of the matrix is equal to either 0 or 1. Rows and columns are 1-indexed. Ivan can replace any number of ones in this matrix with zeroes. After that, his score in the game will be calculated as follows:
 1.  Initially Ivan's score is 0; 1.  In each column, Ivan will find the topmost 1 (that is, if the current column is *j*, then he will find minimum *i* such that *a**i*,<=*j*<==<=1). If there are no 1's in the column, this column is skipped; 1.  Ivan will look at the next *min*(*k*,<=*n*<=-<=*i*<=+<=1) elements in this column (starting from the element he found) and count the number of 1's among these elements. This number will be added to his score. 
Of course, Ivan wants to maximize his score in this strange game. Also he doesn't want to change many elements, so he will replace the minimum possible number of ones with zeroes. Help him to determine the maximum possible score he can get and the minimum possible number of replacements required to achieve that score.

Input Specification:
The first line contains three integer numbers *n*, *m* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=100, 1<=≤<=*m*<=≤<=100).

Then *n* lines follow, *i*-th of them contains *m* integer numbers — the elements of *i*-th row of matrix *a*. Each number is either 0 or 1.

Output Specification:
Print two numbers: the maximum possible score Ivan can get and the minimum number of replacements required to get this score.

Demo Input:
['4 3 2\n0 1 0\n1 0 1\n0 1 0\n1 1 1\n', '3 2 1\n1 0\n0 1\n0 0\n']

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

Note:
In the first example Ivan will replace the element *a*<sub class="lower-index">1, 2</sub>.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a singly linked list of N nodes. Find the first node of the loop if the linked list has a loop. If a loop is present return the node data of the first node of the loop else return -1.
Example 1:
Input:
Output: 3
Explanation:
We can see that there exists a loop 
in the given linked list and the first
node of the loop is 3.
 
Example 2:
Input:
Output: -1
Explanation: No loop exists in the above
linked list.So the output is -1.
 
Your Task:
The task is to complete the function findFirstNode() which contains reference to the head as only argument. This function should return the value of the first node of the loop if the linked list contains a loop, else return -1.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{5}
1 <= Data on Node <= 10^{6} 
0 <= pos <= N

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings.
The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.



A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.



The input will be two strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.


Example 1:

Input: "aba", "cdc"
Output: 3
Explanation: The longest uncommon subsequence is "aba" (or "cdc"), because "aba" is a subsequence of "aba", but not a subsequence of any other strings in the group of two strings. 



Note:

Both strings' lengths will not exceed 100.
Only letters from a ~ z will appear in input strings.

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