vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Read problems statements in Mandarin Chinese  and Russian. 
Chef wants to split a team of new chef into two teams to play a game. In order to make the split, he first designates two team captains who take alternate turns selecting players for their teams. During each turn, the captain selects a single player for his team. Since each captain wants to make the strongest possible team, he will always select the best available player. The players have strengths as integer number, where higher strength indicate better players. After all the players have been selected, the team strength is computed as the sum of the strengths of the players on that team.

For example, if strengths of 5 players are 5,7,8,4 and 2, then the first captain selects the player with strength 8 for his team, the second captain gets the player with strength 7, the first gets the one with strength 5, the second the one with strength 4, and the last one (strength 2) goes to the first team. The first team now has a total strength 8+5+2=15, and the second team has strength 7+4=11. 

Now Chef wants to find the absolute strength difference between the two teams. For the example above the answer is 4(=|15-11|).

But Chef does not know exact strengths of each player. He knows some parameter a, b, c and d and a formula to find the strength of each player. The formula is 

	S_{0} = d,

	S_{i} = (a * S_{i-1}^{2} + b * S_{i-1} + c) mod 1000000, for i = 1 to N - 1
	
There are N players numbering 0 to N-1 and S_{i} is the strength of player i.  	

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

First line of the input contains an integer T, number of test cases to follow. Each test consist of single line containing five integers N, a, b, c and d.

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

For each test case, you have to print a single line containing the absolute strength difference between the two teams.

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

1 ≤ T ≤ 50
1 ≤ N ≤ 3000000
0 ≤ a, b, c, d ≤ 100

----- Sample Input 1 ------ 
4
1 1 1 1 1
2 1 1 1 1
3 1 2 3 4
4 2 3 4 1
----- Sample Output 1 ------ 
1
2
763
74896

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Boboniu likes bit operations. He wants to play a game with you.

Boboniu gives you two sequences of non-negative integers $a_1,a_2,\ldots,a_n$ and $b_1,b_2,\ldots,b_m$.

For each $i$ ($1\le i\le n$), you're asked to choose a $j$ ($1\le j\le m$) and let $c_i=a_i\& b_j$, where $\&$ denotes the bitwise AND operation. Note that you can pick the same $j$ for different $i$'s.

Find the minimum possible $c_1 | c_2 | \ldots | c_n$, where $|$ denotes the bitwise OR operation.


-----Input-----

The first line contains two integers $n$ and $m$ ($1\le n,m\le 200$).

The next line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i < 2^9$).

The next line contains $m$ integers $b_1,b_2,\ldots,b_m$ ($0\le b_i < 2^9$).


-----Output-----

Print one integer: the minimum possible $c_1 | c_2 | \ldots | c_n$.


-----Examples-----
Input
4 2
2 6 4 0
2 4

Output
2
Input
7 6
1 9 1 9 8 1 0
1 1 4 5 1 4

Output
0
Input
8 5
179 261 432 162 82 43 10 38
379 357 202 184 197

Output
147


-----Note-----

For the first example, we have $c_1=a_1\& b_2=0$, $c_2=a_2\& b_1=2$, $c_3=a_3\& b_1=0$, $c_4 = a_4\& b_1=0$.Thus $c_1 | c_2 | c_3 |c_4 =2$, and this is the minimal answer we can get.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A string is k palindrome if it can be transformed into a palindrome on removing at most k characters from it. Your task is to complete the function is_k_palin which takes two arguments a string str and a number N . Your function should return true if the string is k palindrome else it should return false.
Input:
The first line of input is an integer T denoting the number of test cases . Then T test cases follow . Each test case  contains a string str and an integer N separated by space.  
Output:
The output will be 1 if the string is  k palindrome else 0 .
Constraints:
1<=T<=100
1<=length of str<=100
1<=N<=20
Example:
Input
2
abcdecba 1
acdcb  1
Output
1
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are both a shop keeper and a shop assistant at a small nearby shop. You have $n$ goods, the $i$-th good costs $a_i$ coins.

You got tired of remembering the price of each product when customers ask for it, thus you decided to simplify your life. More precisely you decided to set the same price for all $n$ goods you have.

However, you don't want to lose any money so you want to choose the price in such a way that the sum of new prices is not less than the sum of the initial prices. It means that if you sell all $n$ goods for the new price, you will receive at least the same (or greater) amount of money as if you sell them for their initial prices.

On the other hand, you don't want to lose customers because of big prices so among all prices you can choose you need to choose the minimum one.

So you need to find the minimum possible equal price of all $n$ goods so if you sell them for this price, you will receive at least the same (or greater) amount of money as if you sell them for their initial prices.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 100$) — the number of queries. Then $q$ queries follow.

The first line of the query contains one integer $n$ ($1 \le n \le 100)$ — the number of goods. The second line of the query contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^7$), where $a_i$ is the price of the $i$-th good.


-----Output-----

For each query, print the answer for it — the minimum possible equal price of all $n$ goods so if you sell them for this price, you will receive at least the same (or greater) amount of money as if you sell them for their initial prices.


-----Example-----
Input
3
5
1 2 3 4 5
3
1 2 2
4
1 1 1 1

Output
3
2
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string. Reverse its characters.

Input

The only line of input contains a string between 1 and 100 characters long. Each character of the string has ASCII-code between 33 (exclamation mark) and 126 (tilde), inclusive.

Output

Output the characters of this string in reverse order.

Examples

Input

secrofedoc


Output

codeforces


Input

!ssalg-gnikool5


Output

5looking-glass!

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a string *s*, consisting of lowercase English letters, and the integer *m*.

One should choose some symbols from the given string so that any contiguous subsegment of length *m* has at least one selected symbol. Note that here we choose positions of symbols, not the symbols themselves.

Then one uses the chosen symbols to form a new string. All symbols from the chosen position should be used, but we are allowed to rearrange them in any order.

Formally, we choose a subsequence of indices 1<=≤<=*i*1<=&lt;<=*i*2<=&lt;<=...<=&lt;<=*i**t*<=≤<=|*s*|. The selected sequence must meet the following condition: for every *j* such that 1<=≤<=*j*<=≤<=|*s*|<=-<=*m*<=+<=1, there must be at least one selected index that belongs to the segment [*j*,<= *j*<=+<=*m*<=-<=1], i.e. there should exist a *k* from 1 to *t*, such that *j*<=≤<=*i**k*<=≤<=*j*<=+<=*m*<=-<=1.

Then we take any permutation *p* of the selected indices and form a new string *s**i**p*1*s**i**p*2... *s**i**p**t*.

Find the lexicographically smallest string, that can be obtained using this procedure.

Input Specification:
The first line of the input contains a single integer *m* (1<=≤<=*m*<=≤<=100<=000).

The second line contains the string *s* consisting of lowercase English letters. It is guaranteed that this string is non-empty and its length doesn't exceed 100<=000. It is also guaranteed that the number *m* doesn't exceed the length of the string *s*.

Output Specification:
Print the single line containing the lexicographically smallest string, that can be obtained using the procedure described above.

Demo Input:
['3\ncbabc\n', '2\nabcab\n', '3\nbcabcbaccba\n']

Demo Output:
['a\n', 'aab\n', 'aaabb\n']

Note:
In the first sample, one can choose the subsequence {3} and form a string "a".

In the second sample, one can choose the subsequence {1, 2, 4} (symbols on this positions are 'a', 'b' and 'a') and rearrange the chosen symbols to form a string "aab".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given positive integers X and Y. If there exists a positive integer not greater than 10^{18} that is a multiple of X but not a multiple of Y, choose one such integer and print it. If it does not exist, print -1.

Constraints

* 1 ≤ X,Y ≤ 10^9
* X and Y are integers.

Input

Input is given from Standard Input in the following format:


X Y


Output

Print a positive integer not greater than 10^{18} that is a multiple of X but not a multiple of Y, or print -1 if it does not exist.

Examples

Input

8 6


Output

16


Input

3 3


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dilku was thinking about the first time he met his girl... It was indeed a walk to remember. The romantic weather and her silly talks. He was completely mesmarized. Those were the days!..    

Today is his girl's birthday and he wants to make it special for her. He wants to again take her on a "special walk" that they would remember for the lifetime.    

The city in which Dilku lives is represented as an unweighted directed graph with N nodes and M edges. A "special walk" in the graph starting at node u is a simple path that begins and ends at the same node u.    

Formally, A special walk is path  u , a1 , a2 , a3 ,..., ai ,.... , u  where ai are distinct and not equal to u for all i.

Now since Dilku is really nervous about taking his girl out, he needs your help. For every node in the given graph, tell whether it is possible for Dilku to take his girl on a "special walk" starting at that node.

Input:

First line of a two space separated integers denoting N and M, the number of nodes and number of directed edges in the corresponding graph.       
Following M lines contain two space separated integers  u v  denoting a directed edge in the graph from vertex numbered u to vertex numbered v.

Output:

Print N space separated integers, where ith integer can be either 1 or 0 depicting whether it is possible to go on a special walk starting at node i or not. 

Constraints:
1 ≤ N ≤ 10^5
1 ≤ M ≤ 2 · 10^5
1 ≤ u, v ≤ N

SAMPLE INPUT
5 5
1 2 
2 3 
3 4 
4 5
4 2

SAMPLE OUTPUT
0 1 1 1 0 

Explanation

In the given graph , there is just one directed cycle :  2-->3-->4-->2. Hence, for all nodes on this cycle, the answer is yes and for others the answer is no.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a binary string S, define its beauty to be the maximum number of [substrings] S can be partitioned into, such that each substring has strictly more ones than zeroes. For example, the beauty of 11011 is 3, as it can be partitioned as [110][1][1]. If such a partition doesn't exist, the beauty is defined to be 0. 

Also, define the happiness of a binary string to be the maximum beauty over all its substrings. For example, the happiness of the string S = 010011011 is 3, which is the beauty of its substring 11011.

You are given N binary strings S_{1}, S_{2}, \ldots, S_{N}. You have to process Q queries:
- Each query consists of two integers L, R, where 1 ≤ L ≤ R ≤ N.
- The result of the query is the maximum possible happiness of S_{p_{1}} + S_{p_{2}} + \ldots S_{p_{(R - L + 1)}}, where p is some permutation of \{L, L + 1, \ldots, R - 1, R\} and + denotes the concatenation operation.

------ Input Format ------ 

The first line of input contains two space-separated integers N and Q, the number of strings and the number of queries. Then, 2N + Q lines follow:
- For each 1 ≤ i ≤ N, S_{i} is represented by two lines. The first line contains the length of S_{i} and the second line contains S_{i} itself.
- Each of the next Q lines contains two integers, L and R, denoting the query parameters

------ Output Format ------ 

For each query, print the maximum possible happiness of the concatenation of some permutation of the given interval on a new line.

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

$1 ≤ N, Q ≤ 10^{5}$
$|S_{i}| ≥ 1$ for each valid $i$.
- Every string consists of characters which are either '0' or '1'.
- The sum of the lengths of all the input strings doesn't exceed $10^{6}$.

------ subtasks ------ 

Subtask 1 (30 points): The sum of $R L + 1$ over all queries doesn't exceed $10^{6}$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
4 1
1
0
2
11
3
010
4
0110
2 4
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
It is optimal to concatenate as $S_{3} + S_{4} + S_{2}$ to get $010011011$ with a happiness value of $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lukas is to hold a presentation on useful mathematical tricks. E.g., to take the square root of a number you just need to remove the first half of the number. To convince his audience he uses the well tested method of proof by example: $\sqrt {25} = 5$ and $\sqrt {5776} = 76$ so the method obviously works. To multiply a number by $X = 2.6$ all you have to do is move the first digit to the end of the number, $135\times 2.6 = 351$ and $270270\times 2.6 = 702702$. 

Lukas wants to demonstrate that this last method works for any $X$. To do this he will ask his audience for values of $X$ and then show them example multiplications for which the method works. Lukas has noticed that he can not just pick arbitrary numbers for his examples, so now he wants your help. Can you write a program that given $X$ gives a list of integers for which multiplying by $X$ is equivalent to moving the first digit to the end of the number? Lukas does not like very large numbers so do not list any numbers with more than 8 digits.

-----Input-----
The input is a single decimal number $X$ ($1\leq X < 1000$) with at most 4 digits after the decimal point.

-----Output-----
Output a list of all positive integers less than $10^8$ for which Lukas’ second trick works. Write the numbers in ascending order, one number per line. If the list is empty, output instead “No solution”.

-----Examples-----
Sample Input:
2.6
Sample Output:
135
270
135135
270270

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
B: Yamanote-line Game-Yamanote-line Game-

Bean (?) Knowledge

The Yamanote line is convenient. The reason is that you can ride as many laps as time allows just by paying 130 yen. However, if you board with a ticket, you must be careful about the valid time of the ticket. It seems safe with an IC card. Taking advantage of the characteristics of the Yamanote Line, there are people in the suburbs of Tokyo who are swayed by trains and devour their sleep. By the way, the questioner of this question has never done it. It's rare for a station employee to find out, but I don't recommend it because it would be annoying.

Problem statement

Let's play a game that utilizes the characteristics of the Yamanote Line. Here, for generalization, there are N stations numbered from 1 to N, and the stations are lined up in the order of 1, 2, ..., N, and you can go to any station from each station. Let's consider the Yamanote Line Modoki as a route that can be boarded for d yen. The game follows the rules below.

* Select your favorite station as the starting point and board the Yamanote Line Modoki for d yen.
* After that, get off at any station and get on again.
* The game ends when you get off at the station where you started.
* If you get off at the i-th station, you can get a reward of p_i yen.
* However, you cannot get the reward again at the station where you got the reward once.
* Also, it costs d yen to get on the Yamanote Line Modoki again after getting off.



Now, how many yen can you make up to? Please give it a try.

Input format


N d
p_1 p_2… p_N


All inputs consist of integers. On the first line, the number N of Modoki stations on the Yamanote line and the fare d are given separated by blanks. On the second line, the rewards received at each station are given separated by blanks, and the i-th value p_i represents the reward for station i.

Constraint

* 3 ≤ N ≤ 1 {,} 000
* 1 ≤ d ≤ 1 {,} 000
* 1 ≤ p_i ≤ 1 {,} 000 (1 ≤ i ≤ N)



Output format

Output the maximum amount of money you can get in the game on one line. If you can't get more than 1 yen, print "kusoge" on one line. The end of the output should be newline and should not contain extra characters.

Input example 1


5 130
130 170 100 120 140


Output example 1


50

Input example 2


3 100
100 90 65


Output example 2


kusoge

Input example 3


6 210
300 270 400 330 250 370


Output example 3


660

Input example 4


4 540
100 460 320 280


Output example 4


kusoge





Example

Input

5 130
130 170 100 120 140


Output

50

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

Time Limit: 1 seconds

Memory Limit: 64 megabytes

Problem Description:
Little Petya likes to play very much. And most of all he likes to play the following game:

He is given a sequence of *N* integer numbers. At each step it is allowed to increase the value of any number by 1 or to decrease it by 1. The goal of the game is to make the sequence non-decreasing with the smallest number of steps. Petya is not good at math, so he asks for your help.

The sequence *a* is called non-decreasing if *a*1<=≤<=*a*2<=≤<=...<=≤<=*a**N* holds, where *N* is the length of the sequence.

Input Specification:
The first line of the input contains single integer *N* (1<=≤<=*N*<=≤<=5000) — the length of the initial sequence. The following *N* lines contain one integer each — elements of the sequence. These numbers do not exceed 109 by absolute value.

Output Specification:
Output one integer — minimum number of steps required to achieve the goal.

Demo Input:
['5\n3 2 -1 2 11\n', '5\n2 1 1 1 1\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two strings $s$ and $t$ both of length $n$ and both consisting of lowercase Latin letters.

In one move, you can choose any length $len$ from $1$ to $n$ and perform the following operation:   Choose any contiguous substring of the string $s$ of length $len$ and reverse it;  at the same time choose any contiguous substring of the string $t$ of length $len$ and reverse it as well. 

Note that during one move you reverse exactly one substring of the string $s$ and exactly one substring of the string $t$.

Also note that borders of substrings you reverse in $s$ and in $t$ can be different, the only restriction is that you reverse the substrings of equal length. For example, if $len=3$ and $n=5$, you can reverse $s[1 \dots 3]$ and $t[3 \dots 5]$, $s[2 \dots 4]$ and $t[2 \dots 4]$, but not $s[1 \dots 3]$ and $t[1 \dots 2]$.

Your task is to say if it is possible to make strings $s$ and $t$ equal after some (possibly, empty) sequence of moves.

You have to answer $q$ independent test cases.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 10^4$) — the number of test cases. Then $q$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $s$ and $t$.

The second line of the test case contains one string $s$ consisting of $n$ lowercase Latin letters.

The third line of the test case contains one string $t$ consisting of $n$ lowercase Latin letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer on it — "YES" (without quotes) if it is possible to make strings $s$ and $t$ equal after some (possibly, empty) sequence of moves and "NO" otherwise.


-----Example-----
Input
4
4
abcd
abdc
5
ababa
baaba
4
asdf
asdg
4
abcd
badc

Output
NO
YES
NO
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Trapped at home in quarantine, Johan tries to keep madness at bay and fend off isolation by playing Critter Junction, a social simulation video game. One of the main aspects of the game is collecting and harvesting various types of resources, in order to gain Bling, the currency of the game. Johan specializes in running the fruit% category of the game, in which the goal is to obtain the maximum amount of Bling in $40$ days using only fruits and no other resources. 

Each fruit can be sold for $100$ Bling, or planted to become a fruit tree (but not both). Every three days, starting on the third day after it was planted, a fruit tree yields three new fruits.

There are also some more exotic fruits that can be bought from the neighboring village. Once per day, the player can travel to the neighboring village and pay $400$ Bling to buy a single exotic fruit which you can then plant or sell already on the same day. Analogously to normal fruits, these exotic fruits can be planted into exotic fruit trees which yield three exotic fruits every three days. Each exotic fruit can be sold for $500$ Bling.

Any number of fruits/exotic fruits can be harvested, sold and planted during a day (subject to availability of course, e.g. it is not possible to sell more fruits than you actually have), but at most a single exotic fruit can be bought. These activities can be done in any order, so it is for instance possible within the same day to first harvest a few fruits (exotic or not), then sell those fruits for Bling, then use that Bling to buy an exotic fruit, and then either plant or sell that exotic fruit.

Given the current state of Johan’s fruit farm, what is the maximum amount of Bling he can achieve in the remaining time?

-----Input-----
The input consists of a single line containing six integers $d$, $b$, $f$, $t_0$, $t_1$ and $t_2$ ($1 \le d \le 40$, $0 \le b \le 500$, and $0 \le f, t_0, t_1, t_2 \le 100$), where:
 - $d$ is the number of remaining days Johan has
 - $b$ is the current amount of Bling Johan has.
 - $f$ is the current number of fruits Johan has.
 - $t_ i$ is the number of fruit trees Johan has that will yield crop $i$ days from today (for $0 \le i \le 2$).

Johan currently does not have any exotic fruits or exotic fruit trees.

-----Output-----
Output a single integer: the maximum amount of Bling Johan can have after playing $d$ days.

-----Examples-----
Sample Input 1:
4 0 1 0 0 0
Sample Output 1:
300

Sample Input 2:
5 0 1 0 1 0
Sample Output 2:
1900

Sample Input 3:
6 0 1 1 0 0
Sample Output 3:
2300

Sample Input 4:
10 399 0 0 0 0
Sample Output 4:
399

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