vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The match is set and your team is ready to win!

The team has $N$ players, each with the ability $A_{i}$.

But you are not happy with the given playing order. You are wondering how to create a new order so that the player with lesser ability go earlier, i.e., in non-decreasing order.

In one move, you can break a suffix of any length of the array and attach it to the front. You can do the move as many times as you like.

For example, the Array $A = [1, 2, 3, 4, 5, 6]$ can become $A = [5, 6, 1, 2, 3, 4]$ in one move by breaking and reattaching the suffix of length $2$.

For each testcase, if the array can be sorted non-decreasingly, print YES and the minimum number of moves to do so. Otherwise, print NO.

------  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.
Each testcase contains two lines. The first line has a single integer $N$, denoting the number of players in the team.
The second list has $N$ space-separated integers of the array $A$, where $A_{i}$ represents the ability of the $i^{th}$ player

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

Print a single line containing the string "YES" if the string can be sorted or "NO" if it does not (without quotes). If answer is yes, print a second line containing a single integer, the minimum number of moves.

You may print each character of each string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

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

$ $1 ≤ T, N ≤ 3 \cdot 10^{5}$
$$ $0 ≤ A_{i} ≤ 10^{9}$
$$ The sum of all $N$ over all testcases $T$, does not exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
2
1 2
3
2 1 3
----- Sample Output 1 ------ 
YES
0
NO
----- explanation 1 ------ 
Example Case 1: The array is already sorted non-decreasingly. Hence, 0 moves required.Example Case 2: We cannot satisfy the condition for the given array. Hence, answer is NO.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given a string that may have mixed uppercase and lowercase letters and your task is to convert that string to either lowercase only or uppercase only based on: 

* make as few changes as possible. 
* if the string contains equal number of uppercase and lowercase letters, convert the string to lowercase. 

For example:
```Haskell
solve("coDe") = "code". Lowercase characters > uppercase. Change only the "D" to lowercase.
solve("CODe") = "CODE". Uppercase characters > lowecase. Change only the "e" to uppercase.
solve("coDE") = "code". Upper == lowercase. Change all to lowercase.
```

More examples in test cases. Good luck!

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

[Simple remove duplicates](https://www.codewars.com/kata/5ba38ba180824a86850000f7)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef and his friend Miron were getting bored and decided to play a game. 
Miron thinks of a sequence of  N  integers (A1, A2, …., AN) and gives Chef a matrix B, where Bi,j = |Ai - Aj|. He further tells Chef that A1 = 0. The game is for Chef to guess the sequence that Miron thought of. 
But Miron is an adversarial player. Every time Chef tries to guess the sequence, he makes a change to the matrix. He makes such a change Q times. Each time, he replaces an entry in some row and the corresponding column with a new one leaving Chef to guess the sequence after each change. 
Chef needs a friend to help him against such an adversarial player. Can you be that friend and help Chef find a suitable sequence A for the initial matrix B and also after each change Miron makes? 
Note that if several answers exist, then print the lexicographically smallest answer. Further, the numbers in the sequence can be negative.

-----Input-----

The first line contains two space-separated integers N, Q. Each of the N subsequent lines contains N space-separated integers, denoting the matrix B.

Q queries follow. Each query has two lines. The first line of each query contains an integer p, denoting the number of row and column that is changed. The second line of each query contains N space-separated integers F1, F2, F3, ... FN, denoting the new values to the corresponding cells of the matrix (you should make the following assignments Bi,p = Bp,i = Fi for all valid i). 

-----Output-----
Print Q + 1 lines which contain N space-separated integers, Miron's initial array and Miron's array after each query.

-----Constraints-----
- 3 ≤ N ≤  1000 
- 1 ≤ Q ≤  1000 
- 0 ≤ Bi,j ≤  5000 
- 1 ≤ p ≤  n 
- 0 ≤ Fi ≤  5000 
- it's guaranteed there's always an answer

-----Example-----
Input:
3 2
0 1 2
1 0 1
2 1 0
1
0 4 3
2
4 0 7
Output:
0 -1 -2
0 -4 -3
0 -4 3

-----Explanation-----
Example case 1. Initially, sequence {0, 1, 2} is also suitable, but {0, -1, -2} is lexicografically smaller.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once upon a time in a kingdom far, far away… Okay, let’s start at the point where Ivan the Fool met Gorynych the Dragon. Ivan took out his magic sword and the battle began. First Gorynych had h heads and t tails. With each strike of the sword Ivan can either cut off several heads (from 1 to n, but not more than Gorynych has at the moment), or several tails (from 1 to m, but not more than Gorynych has at the moment). At the same time, horrible though it seems, Gorynych the Dragon can also grow new heads and tails. And the number of growing heads and tails is determined uniquely by the number of heads or tails cut by the current strike. When the total number of heads and tails exceeds R, Gorynych the Dragon strikes its final blow and destroys Ivan the Fool. That’s why Ivan aims to cut off all the dragon’s heads and tails as quickly as possible and win. The events can also develop in a third way: neither of the opponents can win over the other one and they will continue fighting forever.

The tale goes like this; easy to say, hard to do. Your task is to write a program that will determine the battle’s outcome. Consider that Ivan strikes consecutively. After each blow Gorynych grows a number of new heads and tails depending on the number of cut ones. Gorynych the Dragon is defeated if after the blow he loses all his heads and tails and can’t grow new ones. Ivan fights in the optimal way (fools are lucky), i.e. 

  * if Ivan can win, he wins having struck the least number of blows; 
  * if it is impossible to defeat Gorynych, but is possible to resist him for an infinitely long period of time, then that’s the strategy Ivan chooses; 
  * if Gorynych wins in any case, Ivan aims to resist him for as long as possible. 

Input

The first line contains three integers h, t and R (0 ≤ h, t, R ≤ 200, 0 < h + t ≤ R) which represent the initial numbers of Gorynych’s heads and tails and the largest total number of heads and tails with which Gorynych the Dragon does not yet attack. The next line contains integer n (1 ≤ n ≤ 200). The next n contain pairs of non-negative numbers "hi ti" which represent the number of heads and the number of tails correspondingly, that will grow if Gorynych has i heads (1 ≤ i ≤ n) cut. The next line contains an integer m (1 ≤ m ≤ 200) and then — the description of Gorynych’s behavior when his tails are cut off in the format identical to the one described above. All the numbers in the input file do not exceed 200. 

Output

Print "Ivan" (without quotes) in the first line if Ivan wins, or "Zmey" (that means a dragon in Russian) if Gorynych the Dragon wins. In the second line print a single integer which represents the number of blows Ivan makes. If the battle will continue forever, print in the first line "Draw".

Examples

Input

2 2 4
2
1 0
0 1
3
0 1
0 1
0 0


Output

Ivan
2


Input

2 2 4
1
0 1
1
1 0


Output

Draw


Input

2 2 5
1
1 1
1
3 0


Output

Zmey
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S as input. Delete the characters at odd indices of the string.
Example 1:
Input: S = "Geeks"
Output: "Ges" 
Explanation: Deleted "e" at index 1
and "k" at index 3.
Example 2:
Input: S = "GeeksforGeeks"
Output: "GesoGes"
Explanation: Deleted e, k, f, r, e
k at index 1, 3, 5, 7, 9, 11.
Your Task:  
You dont need to read input or print anything. Complete the function delAlternate() which takes S as input parameter and returns the final string after deletion of characters at odd indices.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints:
1<= |S| <=1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N non-negative integers: A_1, A_2, ..., A_N.
Consider painting at least one and at most N-1 integers among them in red, and painting the rest in blue.
Let the beauty of the painting be the \mbox{XOR} of the integers painted in red, plus the \mbox{XOR} of the integers painted in blue.
Find the maximum possible beauty of the painting.What is \mbox{XOR}?

The bitwise \mbox{XOR} x_1 \oplus x_2 \oplus \ldots \oplus x_n of n non-negative integers x_1, x_2, \ldots, x_n is defined as follows:

 -  When x_1 \oplus x_2 \oplus \ldots \oplus x_n is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if the number of integers among x_1, x_2, \ldots, x_n whose binary representations have 1 in the 2^k's place is odd, and 0 if that count is even. 
For example, 3 \oplus 5 = 6.


-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 10^5
 - 0 \leq A_i < 2^{60}\ (1 \leq i \leq N)

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print the maximum possible beauty of the painting.

-----Sample Input-----
3
3 6 5

-----Sample Output-----
12

If we paint 3, 6, 5 in blue, red, blue, respectively, the beauty will be (6) + (3 \oplus 5) = 12.
There is no way to paint the integers resulting in greater beauty than 12, so the answer is 12.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Kleofáš and the n-thlon

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kleofáš is participating in an *n*-thlon - a tournament consisting of *n* different competitions in *n* different disciplines (numbered 1 through *n*). There are *m* participants in the *n*-thlon and each of them participates in all competitions.

In each of these *n* competitions, the participants are given ranks from 1 to *m* in such a way that no two participants are given the same rank - in other words, the ranks in each competition form a permutation of numbers from 1 to *m*. The score of a participant in a competition is equal to his/her rank in it.

The overall score of each participant is computed as the sum of that participant's scores in all competitions.

The overall rank of each participant is equal to 1<=+<=*k*, where *k* is the number of participants with strictly smaller overall score.

The *n*-thlon is over now, but the results haven't been published yet. Kleofáš still remembers his ranks in each particular competition; however, he doesn't remember anything about how well the other participants did. Therefore, Kleofáš would like to know his expected overall rank.

All competitors are equally good at each discipline, so all rankings (permutations of ranks of everyone except Kleofáš) in each competition are equiprobable.

Input Specification:
The first line of the input contains two space-separated integers *n* (1<=≤<=*n*<=≤<=100) and *m* (1<=≤<=*m*<=≤<=1000) — the number of competitions and the number of participants respectively.

Then, *n* lines follow. The *i*-th of them contains one integer *x**i* (1<=≤<=*x**i*<=≤<=*m*) — the rank of Kleofáš in the *i*-th competition.

Output Specification:
Output a single real number – the expected overall rank of Kleofáš. Your answer will be considered correct if its relative or absolute error doesn't exceed 10<=-<=9.

Namely: let's assume that your answer is *a*, and the answer of the jury is *b*. The checker program will consider your answer correct, if .

Demo Input:
['4 10\n2\n1\n2\n1\n', '5 5\n1\n2\n3\n4\n5\n', '3 6\n2\n4\n2\n']

Demo Output:
['1.0000000000000000\n', '2.7500000000000000\n', '1.6799999999999999\n']

Note:
In the first sample, Kleofáš has overall score 6. Nobody else can have overall score less than 6 (but it's possible for one other person to have overall score 6 as well), so his overall rank must be 1.

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

Joey and Chandler got bored of playing foosball, so they thought of trying something new.As Joey is very intelligent so he invented a new game to play. The rules are as follows. First, they get a set of n distinct integers. And then they take turns to make the following moves. During each move, either Joey or Chandler (the player whose turn is the current) can choose two distinct integers x and y from the set, such that the set doesn't contain their absolute difference |x-y|. Then this player adds integer |x-y| to the set and gets |x-y| points.
If the current player has no valid move, he loses the game. The question is who will finally win the game if both players play optimally. Remember that as Joey invented the game so he always moves first.

Input
The first line contains an integer t - the number of test cases,For each test case First line contains  an integer n — the initial number of elements in the set. The second line contains n distinct space-separated integers a1,a2,...,an  — the elements of the set.
Constraints:

 t ≤ 10
 2 ≤ n ≤ 100
 1 ≤ ai ≤ 10^9

Output:

Print a single line with the winner's name and the total sum of points of both players. If Joey wins print "Joey"(without quotes) and total points separated by space, otherwise print "Chandler"(without quotes) and total points separated by space.

SAMPLE INPUT
2
2
1 2
2
5 3

SAMPLE OUTPUT
Chandler 0
Joey 7

Explanation

Test Case 1:
Joey can not make a starting move so Chandler wins the game.Both players have no points.

Test Case 2:
Joey can get 2 points and 2 will be added to set so new set will be 5 3 2
Chandler can get 1 point and 1 will be added to set so new set will be 5 3 2 1
joey can get 4 points and 4 will be added to set so new set will be 5 3 2 1 4
Then there is no Possible move so Joey wins the game and total points of both players are 2+1+4=7 points

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer K > 2, with prime
factorization:

K = p1^a1 * p2^a2 ... * pn^an

Compute the following:

S = a1*p1 + a2*p2 ... + an*pn.


Input
A list of 
Output
For each integer compute the super factor
sum and output it on a single line.

Example

Input:
6
7
Output:
5
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A set of points on a plane is called good, if for any two points at least one of the three conditions is true:

  * those two points lie on same horizontal line; 
  * those two points lie on same vertical line; 
  * the rectangle, with corners in these two points, contains inside or on its borders at least one point of the set, other than these two. We mean here a rectangle with sides parallel to coordinates' axes, the so-called bounding box of the two points.



You are given a set consisting of n points on a plane. Find any good superset of the given set whose size would not exceed 2·105 points.

Input

The first line contains an integer n (1 ≤ n ≤ 104) — the number of points in the initial set. Next n lines describe the set's points. Each line contains two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — a corresponding point's coordinates. It is guaranteed that all the points are different.

Output

Print on the first line the number of points m (n ≤ m ≤ 2·105) in a good superset, print on next m lines the points. The absolute value of the points' coordinates should not exceed 109. Note that you should not minimize m, it is enough to find any good superset of the given set, whose size does not exceed 2·105.

All points in the superset should have integer coordinates.

Examples

Input

2
1 1
2 2


Output

3
1 1
2 2
1 2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mishka is a little polar bear. As known, little bears loves spending their free time playing dice for chocolates. Once in a wonderful sunny morning, walking around blocks of ice, Mishka met her friend Chris, and they started playing the game.

Rules of the game are very simple: at first number of rounds *n* is defined. In every round each of the players throws a cubical dice with distinct numbers from 1 to 6 written on its faces. Player, whose value after throwing the dice is greater, wins the round. In case if player dice values are equal, no one of them is a winner.

In average, player, who won most of the rounds, is the winner of the game. In case if two players won the same number of rounds, the result of the game is draw.

Mishka is still very little and can't count wins and losses, so she asked you to watch their game and determine its result. Please help her!

Input Specification:
The first line of the input contains single integer *n* *n* (1<=≤<=*n*<=≤<=100) — the number of game rounds.

The next *n* lines contains rounds description. *i*-th of them contains pair of integers *m**i* and *c**i* (1<=≤<=*m**i*,<=<=*c**i*<=≤<=6) — values on dice upper face after Mishka's and Chris' throws in *i*-th round respectively.

Output Specification:
If Mishka is the winner of the game, print "Mishka" (without quotes) in the only line.

If Chris is the winner of the game, print "Chris" (without quotes) in the only line.

If the result of the game is draw, print "Friendship is magic!^^" (without quotes) in the only line.

Demo Input:
['3\n3 5\n2 1\n4 2\n', '2\n6 1\n1 6\n', '3\n1 5\n3 3\n2 2\n']

Demo Output:
['Mishka', 'Friendship is magic!^^', 'Chris']

Note:
In the first sample case Mishka loses the first round, but wins second and third rounds and thus she is the winner of the game.

In the second sample case Mishka wins the first round, Chris wins the second round, and the game ends with draw with score 1:1.

In the third sample case Chris wins the first round, but there is no winner of the next two rounds. The winner of the game is Chris.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has a checkered sheet of paper of size n × m. Polycarp painted some of cells with black, the others remained white. Inspired by Malevich's "Black Square", Polycarp wants to paint minimum possible number of white cells with black so that all black cells form a square.

You are to determine the minimum possible number of cells needed to be painted black so that the black cells form a black square with sides parallel to the painting's sides. All the cells that do not belong to the square should be white. The square's side should have positive length.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the sizes of the sheet.

The next n lines contain m letters 'B' or 'W' each — the description of initial cells' colors. If a letter is 'B', then the corresponding cell is painted black, otherwise it is painted white.


-----Output-----

Print the minimum number of cells needed to be painted black so that the black cells form a black square with sides parallel to the painting's sides. All the cells that do not belong to the square should be white. If it is impossible, print -1.


-----Examples-----
Input
5 4
WWWW
WWWB
WWWB
WWBB
WWWW

Output
5

Input
1 2
BB

Output
-1

Input
3 3
WWW
WWW
WWW

Output
1



-----Note-----

In the first example it is needed to paint 5 cells — (2, 2), (2, 3), (3, 2), (3, 3) and (4, 2). Then there will be a square with side equal to three, and the upper left corner in (2, 2).

In the second example all the cells are painted black and form a rectangle, so it's impossible to get a square.

In the third example all cells are colored white, so it's sufficient to color any cell black.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob’s green thumb has recently gotten him a job as a gardener at a local park. Along with caring for all the plants in the garden, he was also given the responsibility of completely redesigning the park with all new equipment and green spaces.

Unfortunately for Bob, he’s not as good at financing as he is at gardening, and may have messed up. In one area of the garden, he has a courtyard in the shape of a perfect square. In the process of designing the courtyard, he spent so much money on fertilizer and grass seed that he had to buy cheap sprinklers.

When the time came to install the sprinklers, Bob found out that the sprinklers don’t all rotate the same amount, and not all of the grass is getting water. Assuming that each sprinkler can spray water infinitely far, help Bob determine the proportion of the courtyard that is watered by the sprinklers.

-----Input-----
The input consists of a single line containing four real numbers $a$, $b$, $c$, and $d$ ($0\leq a, b, c, d\leq 90$) representing the sizes of four angles in degrees. The number $a$ represents the angle that the bottom right sprinkler rotates from the right wall; similarly, $b$ is the angle that the top right sprinkler rotates from the top wall, $c$ is the angle that the top left sprinkler rotates from the left wall, and $d$ is the angle that the bottom left sprinkler rotates from the bottom wall. All numbers will be given with no more than $3$ digits after the decimal point.

-----Output-----
Output the proportion of the area of the courtyard that is watered by the sprinklers as a real number. Your answer will be considered correct if it is within $10^{-6}$ of the correct answer.

-----Examples-----
Sample Input:
45 45 0 0
Sample Output:
0.75

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