vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Pizza, Pizza, Pizza!!!

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Katie, Kuro and Shiro are best friends. They have known each other since kindergarten. That's why they often share everything with each other and work together on some very hard problems.

Today is Shiro's birthday. She really loves pizza so she wants to invite her friends to the pizza restaurant near her house to celebrate her birthday, including her best friends Katie and Kuro.

She has ordered a very big round pizza, in order to serve her many friends. Exactly $n$ of Shiro's friends are here. That's why she has to divide the pizza into $n + 1$ slices (Shiro also needs to eat). She wants the slices to be exactly the same size and shape. If not, some of her friends will get mad and go home early, and the party will be over.

Shiro is now hungry. She wants to cut the pizza with minimum of straight cuts. A cut is a straight segment, it might have ends inside or outside the pizza. But she is too lazy to pick up the calculator.

As usual, she will ask Katie and Kuro for help. But they haven't come yet. Could you help Shiro with this problem?

Input Specification:
A single line contains one non-negative integer $n$ ($0 \le n \leq 10^{18}$) — the number of Shiro's friends. The circular pizza has to be sliced into $n + 1$ pieces.

Output Specification:
A single integer — the number of straight cuts Shiro needs.

Demo Input:
['3\n', '4\n']

Demo Output:
['2', '5']

Note:
To cut the round pizza into quarters one has to make two cuts through the center with angle $90^{\circ}$ between them.

To cut the round pizza into five equal parts one has to make five cuts.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string t, we will call it unbalanced if and only if the length of t is at least 2, and more than half of the letters in t are the same. For example, both `voodoo` and `melee` are unbalanced, while neither `noon` nor `a` is.

You are given a string s consisting of lowercase letters. Determine if there exists a (contiguous) substring of s that is unbalanced. If the answer is positive, show a position where such a substring occurs in s.

Constraints

* 2 ≦ |s| ≦ 10^5
* s consists of lowercase letters.

Input

The input is given from Standard Input in the following format:


s


Output

If there exists no unbalanced substring of s, print `-1 -1`.

If there exists an unbalanced substring of s, let one such substring be s_a s_{a+1} ... s_{b} (1 ≦ a < b ≦ |s|), and print `a b`. If there exists more than one such substring, any of them will be accepted.

Examples

Input

needed


Output

2 5


Input

atcoder


Output

-1 -1

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

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
The whole world got obsessed with robots,and to keep pace with the progress, great Berland's programmer Draude decided to build his own robot. He was working hard at the robot. He taught it to walk the shortest path from one point to another, to record all its movements, but like in many Draude's programs, there was a bug — the robot didn't always walk the shortest path. Fortunately, the robot recorded its own movements correctly. Now Draude wants to find out when his robot functions wrong. Heh, if Draude only remembered the map of the field, where he tested the robot, he would easily say if the robot walked in the right direction or not. But the field map was lost never to be found, that's why he asks you to find out if there exist at least one map, where the path recorded by the robot is the shortest.

The map is an infinite checkered field, where each square is either empty, or contains an obstruction. It is also known that the robot never tries to run into the obstruction. By the recorded robot's movements find out if there exist at least one such map, that it is possible to choose for the robot a starting square (the starting square should be empty) such that when the robot moves from this square its movements coincide with the recorded ones (the robot doesn't run into anything, moving along empty squares only), and the path from the starting square to the end one is the shortest.

In one movement the robot can move into the square (providing there are no obstrutions in this square) that has common sides with the square the robot is currently in.

Input Specification:
The first line of the input file contains the recording of the robot's movements. This recording is a non-empty string, consisting of uppercase Latin letters L, R, U and D, standing for movements left, right, up and down respectively. The length of the string does not exceed 100.

Output Specification:
In the first line output the only word OK (if the above described map exists), or BUG (if such a map does not exist).

Demo Input:
['LLUUUR\n', 'RRUULLDD\n']

Demo Output:
['OK\n', 'BUG\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin Chinese  and Russian. 

Haku has been newly hired by Chef to clean tables at his restaurant. So whenever a customer wants a table, Haku must clean it.
But Haku happens to be a lazy boy. So in the morning, when the restaurant is opened, all the tables are dirty from night before.
The customer don't leave the table unless they are politely requested to do so. And customers can order meal later again. So if they were already having a table, they can be served on the same table [Haku doesn't have to clean :)]. But if they don't have a table then they must be given some table [Haku must clean :(]
The restaurant has N tables. When a customer requires a table, he/she can occupy any unoccupied table. However if all tables are occupied, then Haku is free to ask politely any customer to leave his/her table. And the freed table can be given to the waiting customer.
Now Chef has the psychic ability to tell the order of customer meal requests for the entire day. Given this list, help Haku find the minimum number of times he has to clean the tables.

------ Input ------ 

First line contains integer T, number of test cases.
First line of each test case contains 2 integers N, number of tables and M, number of customer orders. Followed by M integers on next line, which is the order in which customers ask for meal. Customers are referenced by integer C.

------ Output ------ 

For each test case output the minimum number of times Haku must clean the table(s).

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 200$
$1 ≤ M ≤ 400$
$1 ≤ C ≤ 400$

----- Sample Input 1 ------ 
4
2 4
1 2 3 4
3 2
4 1
3 6
1 2 1 3 4 1
3 5
1 2 1 3 4
----- Sample Output 1 ------ 
4
2
4
4
----- explanation 1 ------ 
Example case 1. In the starting all tables i.e. 2 tables are unoccupied. When customer 1 asks for table, he can be given any of the 2 tables. Haku has to clean either of the table. Next customer 2 can occupy the other free table. Haku must clean second time. When customer 3 comes Haku can ask either customer 1 or 2 to leave. Suppose he asks customer 1 to leave. Then he has to clean table for the third time. When customer 4 comes, Haku can ask customer 2 or 3 to leave. In either case Haku will have to clean the table for the fourth time. Phew!!
Example case 4. Suppose the tables are listed as [-, -, -]. A possible optimal order of allocating tables can be [1, -, -] -> [1, 2, -] -> [1, 2, -] -> [1, 2, 3] -> [4, 2, 3]. So Haku will have to clean table for order no. 1, 2, 4 and 5. That is 4 times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today Pari and Arya are playing a game called Remainders.

Pari chooses two positive integer x and k, and tells Arya k but not x. Arya have to find the value $x \text{mod} k$. There are n ancient numbers c_1, c_2, ..., c_{n} and Pari has to tell Arya $x \operatorname{mod} c_{i}$ if Arya wants. Given k and the ancient values, tell us if Arya has a winning strategy independent of value of x or not. Formally, is it true that Arya can understand the value $x \text{mod} k$ for any positive integer x?

Note, that $x \text{mod} y$ means the remainder of x after dividing it by y.


-----Input-----

The first line of the input contains two integers n and k (1 ≤ n,  k ≤ 1 000 000) — the number of ancient integers and value k that is chosen by Pari.

The second line contains n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 1 000 000).


-----Output-----

Print "Yes" (without quotes) if Arya has a winning strategy independent of value of x, or "No" (without quotes) otherwise.


-----Examples-----
Input
4 5
2 3 5 12

Output
Yes

Input
2 7
2 3

Output
No



-----Note-----

In the first sample, Arya can understand $x \operatorname{mod} 5$ because 5 is one of the ancient numbers.

In the second sample, Arya can't be sure what $x \text{mod} 7$ is. For example 1 and 7 have the same remainders after dividing by 2 and 3, but they differ in remainders after dividing by 7.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The auditorium of Stanford University is made up of L*R matrix (assume each coordinate has a chair). On the occasion of an event Chef was called as a chief guest. The auditorium was filled with males (M) and females (F), occupying one chair each. Our Chef is very curious guy, so he asks the gatekeeper some queries. The queries were as follows: Is there any K*K sub-matrix in the auditorium which contains all Males or Females.

-----Input-----
- The first line contains three space-separated integers L, R  and Q describing the dimension of the auditorium and the number of questions Chef will ask.
- Each of next L lines contains R characters (M or F).
- Next Q lines contains K and a character (M or F).

-----Output-----
- For each query output "yes" (without quotes) if there exist any K*K sub-matrix in the auditorium which contains all Males (if he asks about Male) or Females (if he asks about Female), otherwise output "no" (without quotes).

-----Constraints and Subtasks-----
- 1 <= L, R, K <= 1000
- 1 <= Q <= 1e6
Subtask 1: 30 points
- 1 <= L, R, Q <= 200
Subtask 2: 70 points
- Original Contraints

-----Example-----
Input:
4 3 3
MMF
MMM
FFM
FFM
2 F
3 M
1 M

Output:
yes
no
yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The non-negative integer a is a divisor of the non-negative integer b if and only if there exists a positive integer c such that a × c = b. 

Some numbers are really interesting. Commander Surena defines some interesting properties for non-negative integers:

  * An integer is happy if it is divisible by at least one of its digits and not by all of them. 
  * An integer is happier if it is divisible by all of its digits. 
  * An integer is upset if it's divisible by none of its digits. 



Surena asks you to find out if a given number is happy, happier or upset.

Input

Input contains a single non-negative integer n (1 ≤ n ≤ 108).

Output

Write on a single line the type of the integer: happy, happier or upset. Print the type in lowercase letters.

Examples

Input

99


Output

happier


Input

29994


Output

happy


Input

23


Output

upset

Note

In the second test 29994 is only divisible by 2.

In the third test 23 is a prime number.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given sequence of integers $A = \\{a_0, a_1, ..., a_{n-1}\\}$, perform the following operations.

* count($b, e, k$): print the number of the specific values $k$ in $a_b, a_{b+1}, ..., a_{e-1}$.

Constraints

* $1 \leq n \leq 1,000$
* $-1,000,000,000 \leq a_i, k_i \leq 1,000,000,000$
* $1 \leq q \leq 1,000$
* $0 \leq b < e \leq n$

Input

The input is given in the following format.


$n$
$a_0 \; a_1, ..., \; a_{n-1}$
$q$
$b_1 \; e_1 \; k_1$
$b_2 \; e_2 \; k_2$
:
$b_q \; e_q \; k_q$


The number of elements $n$ and each element $a_i$ are given in the first line and the second line respectively. In the third line, the number of queries $q$ is given and the following $q$ lines, $q$ integers $b_i \; b_e \; k_i$ are given as queries.

Output

For each query, print the number of specified values.

Example

Input

9
1 4 1 4 2 1 3 5 6
3
0 9 1
1 6 1
3 7 5


Output

3
2
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A rectangle sheetof NxM. Make C cuts parallel to edges such that area of the smallest piece after cutting is maximised i.e. After cutting, the area of the smallest rectangle should be maximised. Print the area of the smallest such rectangle.
All cuts should be made at integer points.
If it is not possible to make c cuts, print -1.

Input
First line : number of test cases
A single line contains three integers n, m, c (T ≤ 1000  1 ≤ N, M≤ 10 ^ 9;  1 ≤ C ≤ 10 ^ 9).

Output
Output a single integer representing the answer. If it is impossible to cut the rectangle c times, print -1.

Explanation of Sample Input :

If you have a rectangle of size 3X4, and you can make only 1 cut. Then cut it into two rectangles of 3X2 and 3X2 to get the maximum area of smallest rectangle i.e. 6.
Supposedly, If you cut it into 3X1 and 3X3, then the smallest area would be 3 , which is less than 6.
So the maximum area of minimum rectangle will be 6 ( 3X2 rectangle).

Problem Setter : Shivam Beri

SAMPLE INPUT
1
3 4 1

SAMPLE OUTPUT
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our beloved detective, Sherlock is currently trying to catch a serial killer who kills a person each day. Using his powers of deduction, he came to know that the killer has a strategy for selecting his next victim.

The killer starts with two potential victims on his first day, selects one of these two, kills selected victim and replaces him with a new person. He repeats this procedure each day. This way, each day he has two potential victims to choose from. Sherlock knows the initial two potential victims. Also, he knows the murder that happened on a particular day and the new person who replaced this victim.

You need to help him get all the pairs of potential victims at each day so that Sherlock can observe some pattern.


-----Input-----

First line of input contains two names (length of each of them doesn't exceed 10), the two initials potential victims. Next line contains integer n (1 ≤ n ≤ 1000), the number of days.

Next n lines contains two names (length of each of them doesn't exceed 10), first being the person murdered on this day and the second being the one who replaced that person.

The input format is consistent, that is, a person murdered is guaranteed to be from the two potential victims at that time. Also, all the names are guaranteed to be distinct and consists of lowercase English letters.


-----Output-----

Output n + 1 lines, the i-th line should contain the two persons from which the killer selects for the i-th murder. The (n + 1)-th line should contain the two persons from which the next victim is selected. In each line, the two names can be printed in any order.


-----Examples-----
Input
ross rachel
4
ross joey
rachel phoebe
phoebe monica
monica chandler

Output
ross rachel
joey rachel
joey phoebe
joey monica
joey chandler

Input
icm codeforces
1
codeforces technex

Output
icm codeforces
icm technex



-----Note-----

In first example, the killer starts with ross and rachel.   After day 1, ross is killed and joey appears.  After day 2, rachel is killed and phoebe appears.  After day 3, phoebe is killed and monica appears.  After day 4, monica is killed and chandler appears.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rachel has some candies and she decided to distribute them among $N$ kids. The ith kid receives $A_i$ candies. The kids are happy iff the difference between the highest and lowest number of candies received is less than $X$.
Find out if the children are happy or not.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- The first line contains $N$ and $X$. 
- The second line contains $N$ integers $A_1,A_2,...,A_N$. 

-----Output:-----
For each test case print either "YES"(without quotes) if the kids are happy else "NO"(without quotes)

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N, X \leq 10^5$
- $1 \leq A_i \leq 10^5$

-----Sample Input:-----
2

5 6

3 5 6 8 1

3 10

5 2 9

-----Sample Output:-----
NO

YES

-----EXPLANATION:-----
- Example 1: Difference between maximum and minimum candies received is 8-1=7. 7 is greater than 6, therefore, the kids are not happy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will be given a fruit which a farmer has harvested, your job is to see if you should buy or sell.

You will be given 3 pairs of fruit. Your task is to trade your harvested fruit back into your harvested fruit via the intermediate pair, you should return a string of 3 actions.

if you have harvested apples, you would buy this fruit pair: apple_orange, if you have harvested oranges, you would sell that fruit pair.

(In other words, to go from left to right (apples to oranges) you buy, and to go from right to left you sell (oranges to apple))

e.g. 
apple_orange, orange_pear, apple_pear
1. if you have harvested apples, you would buy this fruit pair: apple_orange
2. Then you have oranges, so again you would buy this fruit pair: orange_pear
3. After you have pear, but now this time you would sell this fruit pair: apple_pear
4. Finally you are back with the apples

So your function would return a list: [“buy”,”buy”,”sell”]

If any invalid input is given, "ERROR" should be returned

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Fajlu and Laal Baadshah are extremely good, and passionate Age of Empires 2 players. They're crazy about the game, and the passion they display for the game, if displayed for their semester exams - will make them top the university, even. But well, that's them.

Laal Baadshah relies on rushing through the game, so he tries to create as many weird units as quick as possible, without realizing how much power and strength his total army is giving him. While, Little Fajlu is an extremely smart player - he plans his games in a very smart, and strategic manner... which makes it very difficult to defeat him. Really. Not kidding.

We want the problem solvers to learn Fajlu's strategy, too. So, here it goes.
The top three units he uses are: Samurai, Paladins, and Champions.
The cost of a Samurai is: 100 food, 0 gold.
The cost of a Paladin is: 125 food, 50 gold.
The cost of a Champion is: 50 food, 100 gold.

What Fajlu does is given the state of his current economy, and how much will each unit increase his total advantage over his opponent, he manages to get the maximum army strength he can manage to get.

What you need to do is to calculate this amount quickly, faster than Fajlu and let Laal Baadshah know how much strength will he need to overcome Fajlu?

Input format:
The first line contains a number, T, denoting the number of test cases. The next line contains SIX integers. 
 1. The amount of food F Fajlu has, where  1 ≤ F ≤ 40000
 2. The amount of gold G Fajlu has, where 1 ≤ G ≤ 40000
 3. Power of a Samurai S, where 1 ≤ S ≤ 1000
 4. Power of a Paladin P , where 1 ≤ P ≤ 1000
 5. Power of a Champion C, where 1 ≤ C ≤ 1000
 6. Total power Power Laal Baadshah already has, where 1 ≤ Power ≤ 3000

1 ≤ T ≤ 100  

Output format:
You've to print how much more power would Laal Baadshah need to defeat Fajlu. If he already has more or equal power to defeat him, print -1.

PS: The image contains violent deaths. Adult supervision required. 

SAMPLE INPUT
1
389 130 16 13 18 24

SAMPLE OUTPUT
42

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Deepu loves positive things in life, positive girlfriends, positive marks. He's, in general a lover of positive things, so for obvious reasons he loves an array which contains positive elements.

Anyway, Little Deepu also thinks that not every value in his so called positive array deserves to be valued so high, so he makes an operation called HIT which takes exactly one argument, i.e., HIT (X). When HIT (X) is called, it decreases the value of all the elements of the array by 1 which are greater than X.

Now, to test how positive can you stay in life, he performs M HIT operations, and after they have been done, Deepu wants you to print the final array.

Input:
First line contains N the size of array. Second lines contains N elements of array. Third line contains an integer M next M lines contains a single integer X.

Output:
Print final array after M HIT operations.  

Constraints:
1 ≤ N ≤ 100000
1 ≤ A[i] ≤ 1000000000
1 ≤ M ≤ 20000
1 ≤ X ≤ 1000000000  

SAMPLE INPUT
5
7 8 3 2 10
4
1
3
5
7SAMPLE OUTPUT
5 5 2 1 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two strings A and B, you need to find the last occurrence ( 1 based indexing) of string B in string A.
 
Example 1:
Input:
A = abcdefghijklghifghsd
B = ghi
Output:
13
Explanation:
ghi occurs at position 13 for the
last time in string A.
Example 2:
Input:
A = abdbccaeab
B = abc
Output:
-1
Explanation:
abc is not a substring of A
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function findLastOccurence() which takes two strings A and B as input parameters and returns the position of the last occurrence of B in A. If B is not present in A, return -1.
 
Expected Time Complexity: O(len(A))
Expected Space Complexity: O(len(A))
 
Constarints:
1<=T<=100
1<=len(B)<=10^{5}
1<=len(A)<=10^{6}
len(A)>=len(B)

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