vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.
Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take 1, 2 or 3 stones from the first remaining stones in the row.
The score of each player is the sum of values of the stones taken. The score of each player is 0 initially.
The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.
Assume Alice and Bob play optimally.
Return "Alice" if Alice will win, "Bob" if Bob will win or "Tie" if they end the game with the same score.
 
Example 1:
Input: values = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

Example 2:
Input: values = [1,2,3,-9]
Output: "Alice"
Explanation: Alice must choose all the three piles at the first move to win and leave Bob with negative score.
If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. The next move Alice will take the pile with value = -9 and lose.
If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. The next move Alice will take the pile with value = -9 and also lose.
Remember that both play optimally so here Alice will choose the scenario that makes her win.

Example 3:
Input: values = [1,2,3,6]
Output: "Tie"
Explanation: Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.

Example 4:
Input: values = [1,2,3,-1,-2,-3,7]
Output: "Alice"

Example 5:
Input: values = [-1,-2,-3]
Output: "Tie"

 
Constraints:

1 <= values.length <= 50000
-1000 <= values[i] <= 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given two positive integers `a` and `b` and your task will be to apply the following operations:

```
i) If a = 0 or b = 0, return [a,b]. Otherwise, go to step (ii);
ii) If a ≥ 2*b, set a = a - 2*b, and repeat step (i). Otherwise, go to step (iii);
iii) If b ≥ 2*a, set b = b - 2*a, and repeat step (i). Otherwise, return [a,b].
```

`a` and `b` will both be lower than 10E8.

More examples in tests cases. Good luck!

Please also try [Simple time difference](https://www.codewars.com/kata/5b76a34ff71e5de9db0000f2)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today, Chef woke up to find that he had no clean socks. Doing laundry is such a turn-off for Chef, that in such a situation, he always buys new socks instead of cleaning the old dirty ones. He arrived at the fashion store with money rupees in his pocket and started looking for socks. Everything looked good, but then Chef saw a new jacket which cost jacketCost rupees. The jacket was so nice that he could not stop himself from buying it.

Interestingly, the shop only stocks one kind of socks, enabling them to take the unsual route of selling single socks, instead of the more common way of selling in pairs. Each of the socks costs sockCost rupees.

Chef bought as many socks as he could with his remaining money. It's guaranteed that the shop has more socks than Chef can buy. But now, he is interested in the question: will there be a day when he will have only 1 clean sock, if he uses a pair of socks each day starting tommorow? If such an unlucky day exists, output "Unlucky Chef", otherwise output "Lucky Chef". Remember that Chef never cleans or reuses any socks used once.

-----Input-----
The first line of input contains three integers — jacketCost, sockCost, money — denoting the cost of a jacket, cost of a single sock, and the initial amount of money Chef has, respectively.

-----Output-----
In a single line, output "Unlucky Chef" if such a day exists. Otherwise, output "Lucky Chef". 

-----Constraints-----
- 1 ≤ jacketCost ≤ money ≤ 109
- 1 ≤ sockCost ≤ 109

-----Example-----
Input:
1 2 3

Output:
Unlucky Chef

Input:
1 2 6

Output:
Lucky Chef

-----Subtasks-----
- Subtask 1:  jacketCost, money, sockCost ≤ 103. Points - 20
- Subtask 2: Original constraints. Points - 80

-----Explanation-----
Test #1:
When Chef arrived at the shop, he had 3 rupees. After buying the jacket, he has 2 rupees left, enough to buy only 1 sock.
Test #2:
Chef had 6 rupees in the beginning. After buying the jacket, he has 5 rupees left, enough to buy a pair of socks for 4 rupees.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Nothing has changed since the last round. Dima and Inna still love each other and want to be together. They've made a deal with Seryozha and now they need to make a deal with the dorm guards...

There are four guardposts in Dima's dorm. Each post contains two guards (in Russia they are usually elderly women). You can bribe a guard by a chocolate bar or a box of juice. For each guard you know the minimum price of the chocolate bar she can accept as a gift and the minimum price of the box of juice she can accept as a gift. If a chocolate bar for some guard costs less than the minimum chocolate bar price for this guard is, or if a box of juice for some guard costs less than the minimum box of juice price for this guard is, then the guard doesn't accept such a gift.

In order to pass through a guardpost, one needs to bribe both guards.

The shop has an unlimited amount of juice and chocolate of any price starting with 1. Dima wants to choose some guardpost, buy one gift for each guard from the guardpost and spend exactly *n* rubles on it.

Help him choose a post through which he can safely sneak Inna or otherwise say that this is impossible. Mind you, Inna would be very sorry to hear that!

Input Specification:
The first line of the input contains integer *n* (1<=≤<=*n*<=≤<=105) — the money Dima wants to spend. Then follow four lines describing the guardposts. Each line contains four integers *a*,<=*b*,<=*c*,<=*d* (1<=≤<=*a*,<=*b*,<=*c*,<=*d*<=≤<=105) — the minimum price of the chocolate and the minimum price of the juice for the first guard and the minimum price of the chocolate and the minimum price of the juice for the second guard, correspondingly.

Output Specification:
In a single line of the output print three space-separated integers: the number of the guardpost, the cost of the first present and the cost of the second present. If there is no guardpost Dima can sneak Inna through at such conditions, print -1 in a single line. 

The guardposts are numbered from 1 to 4 according to the order given in the input.

If there are multiple solutions, you can print any of them.

Demo Input:
['10\n5 6 5 6\n6 6 7 7\n5 8 6 6\n9 9 9 9\n', '10\n6 6 6 6\n7 7 7 7\n4 4 4 4\n8 8 8 8\n', '5\n3 3 3 3\n3 3 3 3\n3 3 3 3\n3 3 3 3\n']

Demo Output:
['1 5 5\n', '3 4 6\n', '-1\n']

Note:
Explanation of the first example.

The only way to spend 10 rubles to buy the gifts that won't be less than the minimum prices is to buy two 5 ruble chocolates to both guards from the first guardpost.

Explanation of the second example.

Dima needs 12 rubles for the first guardpost, 14 for the second one, 16 for the fourth one. So the only guardpost we can sneak through is the third one. So, Dima can buy 4 ruble chocolate for the first guard and 6 ruble juice of the second guard.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Bear and String Distance

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Limak is a little polar bear. He likes nice strings — strings of length *n*, consisting of lowercase English letters only.

The distance between two letters is defined as the difference between their positions in the alphabet. For example, , and .

Also, the distance between two nice strings is defined as the sum of distances of corresponding letters. For example, , and .

Limak gives you a nice string *s* and an integer *k*. He challenges you to find any nice string *s*' that . Find any *s*' satisfying the given conditions, or print "-1" if it's impossible to do so.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use gets/scanf/printf instead of getline/cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*n*<=≤<=105, 0<=≤<=*k*<=≤<=106).

The second line contains a string *s* of length *n*, consisting of lowercase English letters.

Output Specification:
If there is no string satisfying the given conditions then print "-1" (without the quotes).

Otherwise, print any nice string *s*' that .

Demo Input:
['4 26\nbear\n', '2 7\naf\n', '3 1000\nhey\n']

Demo Output:
['roar', 'db\n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Cheesy Cheeseman just got a new monitor! He is happy with it, but he just discovered that his old desktop wallpaper no longer fits. He wants to find a new wallpaper, but does not know which size wallpaper he should be looking for, and alas, he just threw out the new monitor's box. Luckily he remembers the width and the aspect ratio of the monitor from when Bob Mortimer sold it to him. Can you help Cheesy out?
# The Challenge

Given an integer `width` and a string `ratio` written as `WIDTH:HEIGHT`, output the screen dimensions as a string written as `WIDTHxHEIGHT`.

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.
A smallest different sequence (SDS) is a sequence of positive integers created as follows: $A_1=r \geq 1$. For $n>1$, $A_ n=A_{n-1}+d$, where $d$ is the smallest positive integer not yet appearing as a value in the sequence or as a difference between two values already in the sequence. For example, if $A_1 =1$, then since $2$ is the smallest number not in our sequence so far, $A_2=A_1+2=3$. Likewise $A_3=7$, since $1, 2$ and $3$ are already accounted for, either as values in the sequence, or as a difference between two values. Continuing, we have $1, 2, 3, 4, 6$, and $7$ accounted for, leaving $5$ as our next smallest difference; thus $A_4=12$. The next few values in this SDS are $20, 30, 44, 59, 75, 96, \ldots $ For a positive integer $m$, you are to determine where in the SDS $m$ first appears, either as a value in the SDS or as a difference between two values in the SDS. In the above SDS, $12, 5, 9$ and $11$ first appear in step $4$.

-----Input-----
Input consists of a single line containing two positive integers $A_1$$m$ ($1 \leq r \leq 100, 1 \leq m \leq 200000000$).

-----Output-----
Display the smallest value $n$ such that the sequence $A_1, \ldots , A_ n$ either contains $m$ as a value in the sequence or as a difference between two values in the sequence. All answers will be $\leq 10000$.

-----Examples-----
Sample Input 1:
1 5
Sample Output 1:
4

Sample Input 2:
1 12
Sample Output 2:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a permutation p = {p_1,\ p_2,\ ...,\ p_n} of {1,\ 2,\ ...,\ n}.
Print the number of elements p_i (1 < i < n) that satisfy the following condition:
 - p_i is the second smallest number among the three numbers p_{i - 1}, p_i, and p_{i + 1}.

-----Constraints-----
 - All values in input are integers.
 - 3 \leq n \leq 20
 - p is a permutation of {1,\ 2,\ ...,\ n}.

-----Input-----
Input is given from Standard Input in the following format:
n
p_1 p_2 ... p_n

-----Output-----
Print the number of elements p_i (1 < i < n) that satisfy the condition.

-----Sample Input-----
5
1 3 5 4 2

-----Sample Output-----
2

p_2 = 3 is the second smallest number among p_1 = 1, p_2 = 3, and p_3 = 5. Also, p_4 = 4 is the second smallest number among p_3 = 5, p_4 = 4, and p_5 = 2. These two elements satisfy the condition.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Croatia’s national television programme is broadcasting an entertainment show titled “I Love Croatia”, modeled on the licensed format I love my country. In this show two teams of celebrities and public figures play various games which require knowledge about Croatia. One of the games is Happy Birthday, which will be used in this task, although somewhat altered.

Eight players numbered one through eight are seated in a circle (see picture). One of them is holding a box which will explode after 3 minutes and 30 seconds from the beginning of the game when some colorful confetti will be blown out. The game begins with a question to the player holding the box. If the players answers incorrectly or skips the question, he is immediately given the next question. If the player answers correctly, he passes the box to the first player seated on his left and then that player gets the next question.

You are given the numbered label of the player who has the box in the beginning and the outcomes of the first $N$ questions asked. Determine the numbered label of the player who had the box when it finally exploded. The question outcome is described with the following data - time passed from the beginning of the question being asked to the moment an answer was given and whether the answer was true (“T”), false (“N”) or skipped (“P”). The time between giving the answer and asking the next question shouldn’t be taken into consideration, as well as time necessary for the box to be passed to the next player. The box will surely explode on a player’s turn.

-----Input-----
The first line of input contains a positive integer $K$ ($1 \leq K \leq 8$), the numbered label of the player who has the box initially. The second line of input contains a positive integer $N$ ($1 \leq N \leq 100$), the number of questions asked during the game. Each of the following $N$ lines contains a positive integer $T$ ($1 \leq T \leq 100$), time passed from the beginning of the $i$-th question being asked to the moment an answer was given, measured in seconds, and a single character $Z$ (“T”, “N” or “P”), the type of answer given.

-----Output-----
The first and only line of output must contain the numbered label of the player who had the box when it finally exploded.

-----Examples-----
Sample Input 1:
1
5
20 T
50 T
80 T
50 T
30 T
Sample Output 1:
5

Sample Input 2:
3
5
100 T
100 N
100 T
100 T
100 N
Sample Output 2:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s, determine if it contains any palindrome of length exactly 100 as a subsequence. If it has any, print any one of them. If it doesn't have any, print a palindrome that is a subsequence of s and is as long as possible.

Input

The only line of the input contains one string s of length n (1 ≤ n ≤ 5·104) containing only lowercase English letters.

Output

If s contains a palindrome of length exactly 100 as a subsequence, print any palindrome of length 100 which is a subsequence of s. If s doesn't contain any palindromes of length exactly 100, print a palindrome that is a subsequence of s and is as long as possible.

If there exists multiple answers, you are allowed to print any of them.

Examples

Input

bbbabcbbb


Output

bbbcbbb


Input

rquwmzexectvnbanemsmdufrg


Output

rumenanemur

Note

A subsequence of a string is a string that can be derived from it by deleting some characters without changing the order of the remaining characters. A palindrome is a string that reads the same forward or backward.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sequence of moves for a robot. Check if the sequence is circular or not. 
A sequence of moves is circular if the first and last positions of the robot are the same. A move can be one of the following :
    G - Go one unit
    L - Turn left
    R - Turn right
Example 1:
Input: path = "GLGLGLG"
Output: "Circular"
Explanation: If we start form 
(0,0) in a plane then we will 
back to (0,0) by the end of the 
sequence.
Ã¢â¬â¹Example 2:
Input: path = "GGGGL"
Output: "Not Circular"
Explanation: We can't return to 
same place at the end of the path.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function isCircular() which takes the string path as input and returns "Circular" if the path is circular else returns "Not Circular".
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Walter was once a promising chemist. Now he teaches high school students chemistry, and was recently diagnosed with lung cancer. In both desperation and excitement he decides to use his chemistry skills to produce illegal drugs and make quick money for his family. He forms a partnership with one of his old students, Jesse, who has some experience with the drug scene.

Now Walter and Jesse are preparing for their first “cook” (the process of making the drugs). They have a list of items they need for the cook, but they realized they have to be very careful when going to the store. The reason is that it may be suspicious to buy certain pairs of items, like cold medicine and battery acid, in the same trip.

They decide to divide the items among themselves, so that each of them can go one trip to the store and buy their share of items without the risk of anyone becoming suspicious. Help them find such a division, or tell them that it is not possible.

-----Input-----
The first line of input contains an integer $N$, $1 \leq N < 100000$, the number of items they want to buy. The following $N$ lines contain the names of these items, all of which are different. A name consists of at most $20$ lowercase letters from the English alphabet or underscores, and is non-empty. The next line of input contains an integer $M$, $0 \leq M < 100000$, the number of pairs of items that are considered suspicious when bought together. Then follow $M$ lines, each containing the names of two different items that form a suspicious pair. Each suspicious pair will be listed exactly once.

-----Output-----
If it is possible for Walter and Jesse to divide the items among themselves, then output two lines. In the first line output the names of the items that Walter should buy. In the second line output the names of the items that Jesse should buy. If there are multiple solutions, output any of them. If this is not possible, output impossible.

-----Examples-----
Sample Input:
5
battery_acid
drain_cleaner
antifreeze
cold_medicine
lantern_fuel
2
cold_medicine battery_acid
antifreeze lantern_fuel
Sample Output:
lantern_fuel drain_cleaner battery_acid
antifreeze cold_medicine

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Devu loves to play with his dear mouse Jerry.  One day they play a game on 2 dimensional grid of dimensions n * n (n ≥ 2). Jerry is currently at coordinates (sx, sy) and wants to move to location (ex, ey) where cheese is placed by Devu. Also Devu is very cunning and has placed a bomb at location (bx, by). All these three locations are distinct. 

In a single move, Jerry can go either up, down, left or right in the grid such that it never goes out of the grid. Also, it has to avoid the bomb. Find out minimum number of moves Jerry needs. It is guaranteed that it is always possible to do so.

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows."
- The first line of each test case contains seven space separated integers n, sx, sy , ex, ey, bx, by. 

-----Output-----
- For each test case, output a single line containing an integer corresponding to minimum number of moves Jerry needs.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 2 ≤ n ≤ 20
-  1 ≤ sx, sy , ex, ey, bx, by ≤ n 
- No two or more poitns in the three points are same.

-----Example-----
Input:
2
2 1 1 2 2 1 2
3 1 1 1 3 1 2

Output:
2
4

-----Explanation-----
Example case 1. ...
Jerry will move directly (1, 1) to (2, 1) and then to (2, 2) in total 2 moves.

Example case 2. ...

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

You are given a polynomial of degree N with integer coefficients. Your task is to find the value of this polynomial at some K different integers, modulo 786433.

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

The first line of the input contains an integer N denoting the degree of the polynomial.
The following line of each test case contains (N+1) integers denoting the coefficients of the polynomial. The i^{th} numbers in this line denotes the coefficient a_{i-1} in the polynomial a_{0} + a_{1} × x^{1} + a_{2} × x^{2} + ... + a_{N} × x^{N}. 
The following line contains a single integer Q denoting the number of queries.
The j^{th} of the following Q lines contains an integer number x_{j} denoting the query.

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

For each query, output a single line containing the answer to the corresponding query. In other words, the j^{th} line of the output should have an integer equal to a_{0} + a_{1} × x_{j} + a_{2} × x_{j}^{2} + ... + a_{N} × x_{j}^{N} modulo 786433.

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

$0 ≤ a_{i}, x_{j} < 786433$
$Subtask #1 (37 points): 0 ≤ N, Q ≤ 1000$
$Subtask #2 (63 points): 0 ≤ N, Q ≤ 2.5 × 10^{5}$

------ Example ------ 

Input:
2
1 2 3
3
7
8
9

Output:
162
209
262

------ Explanation ------ 

Example case 1. 

$Query 1: 1 + 2 × 7 + 3 × 7 × 7 = 162$
$Query 2: 1 + 2 × 8 + 3 × 8 × 8 = 209$
$Query 3: 1 + 2 × 9 + 3 × 9 × 9 = 262$

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