vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Edogawa Conan got tired of solving cases, and invited his friend, Professor Agasa, over. They decided to play a game of cards. Conan has n cards, and the i-th card has a number a_{i} written on it.

They take turns playing, starting with Conan. In each turn, the player chooses a card and removes it. Also, he removes all cards having a number strictly lesser than the number on the chosen card. Formally, if the player chooses the i-th card, he removes that card and removes the j-th card for all j such that a_{j} < a_{i}.

A player loses if he cannot make a move on his turn, that is, he loses if there are no cards left. Predict the outcome of the game, assuming both players play optimally.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of cards Conan has. 

The next line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5), where a_{i} is the number on the i-th card.


-----Output-----

If Conan wins, print "Conan" (without quotes), otherwise print "Agasa" (without quotes).


-----Examples-----
Input
3
4 5 7

Output
Conan

Input
2
1 1

Output
Agasa



-----Note-----

In the first example, Conan can just choose the card having number 7 on it and hence remove all the cards. After that, there are no cards left on Agasa's turn.

In the second example, no matter which card Conan chooses, there will be one one card left, which Agasa can choose. After that, there are no cards left when it becomes Conan's turn again.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In an attempt to escape the Mischievous Mess Makers' antics, Farmer John has abandoned his farm and is traveling to the other side of Bovinia. During the journey, he and his k cows have decided to stay at the luxurious Grand Moo-dapest Hotel. The hotel consists of n rooms located in a row, some of which are occupied.

Farmer John wants to book a set of k + 1 currently unoccupied rooms for him and his cows. He wants his cows to stay as safe as possible, so he wishes to minimize the maximum distance from his room to the room of his cow. The distance between rooms i and j is defined as |j - i|. Help Farmer John protect his cows by calculating this minimum possible distance.


-----Input-----

The first line of the input contains two integers n and k (1 ≤ k < n ≤ 100 000) — the number of rooms in the hotel and the number of cows travelling with Farmer John.

The second line contains a string of length n describing the rooms. The i-th character of the string will be '0' if the i-th room is free, and '1' if the i-th room is occupied. It is guaranteed that at least k + 1 characters of this string are '0', so there exists at least one possible choice of k + 1 rooms for Farmer John and his cows to stay in.


-----Output-----

Print the minimum possible distance between Farmer John's room and his farthest cow.


-----Examples-----
Input
7 2
0100100

Output
2

Input
5 1
01010

Output
2

Input
3 2
000

Output
1



-----Note-----

In the first sample, Farmer John can book room 3 for himself, and rooms 1 and 4 for his cows. The distance to the farthest cow is 2. Note that it is impossible to make this distance 1, as there is no block of three consecutive unoccupied rooms.

In the second sample, Farmer John can book room 1 for himself and room 3 for his single cow. The distance between him and his cow is 2.

In the third sample, Farmer John books all three available rooms, taking the middle room for himself so that both cows are next to him. His distance from the farthest cow is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
PolandBall lives in a forest with his family. There are some trees in the forest. Trees are undirected acyclic graphs with k vertices and k - 1 edges, where k is some integer. Note that one vertex is a valid tree.

There is exactly one relative living in each vertex of each tree, they have unique ids from 1 to n. For each Ball i we know the id of its most distant relative living on the same tree. If there are several such vertices, we only know the value of the one with smallest id among those.

How many trees are there in the forest?

Input

The first line contains single integer n (1 ≤ n ≤ 104) — the number of Balls living in the forest.

The second line contains a sequence p1, p2, ..., pn of length n, where (1 ≤ pi ≤ n) holds and pi denotes the most distant from Ball i relative living on the same tree. If there are several most distant relatives living on the same tree, pi is the id of one with the smallest id.

It's guaranteed that the sequence p corresponds to some valid forest.

Hacking: To hack someone, you should provide a correct forest as a test. The sequence p will be calculated according to the forest and given to the solution you try to hack as input. Use the following format:

In the first line, output the integer n (1 ≤ n ≤ 104) — the number of Balls and the integer m (0 ≤ m < n) — the total number of edges in the forest. Then m lines should follow. The i-th of them should contain two integers ai and bi and represent an edge between vertices in which relatives ai and bi live. For example, the first sample is written as follows:
    
    
      
    5 3  
    1 2  
    3 4  
    4 5  
    

Output

You should output the number of trees in the forest where PolandBall lives.

Interaction

From the technical side, this problem is interactive. However, it should not affect you (except hacking) since there is no interaction.

Examples

Input

5
2 1 5 3 3

Output

2

Input

1
1


Output

1

Note

In the first sample testcase, possible forest is: 1-2 3-4-5. 

There are 2 trees overall.

In the second sample testcase, the only possible graph is one vertex and no edges. Therefore, there is only one tree.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya decided to learn to play chess. Classic chess doesn't seem interesting to him, so he plays his own sort of chess.

The queen is the piece that captures all squares on its vertical, horizontal and diagonal lines. If the cell is located on the same vertical, horizontal or diagonal line with queen, and the cell contains a piece of the enemy color, the queen is able to move to this square. After that the enemy's piece is removed from the board. The queen cannot move to a cell containing an enemy piece if there is some other piece between it and the queen. 

There is an n × n chessboard. We'll denote a cell on the intersection of the r-th row and c-th column as (r, c). The square (1, 1) contains the white queen and the square (1, n) contains the black queen. All other squares contain green pawns that don't belong to anyone.

The players move in turns. The player that moves first plays for the white queen, his opponent plays for the black queen.

On each move the player has to capture some piece with his queen (that is, move to a square that contains either a green pawn or the enemy queen). The player loses if either he cannot capture any piece during his move or the opponent took his queen during the previous move. 

Help Vasya determine who wins if both players play with an optimal strategy on the board n × n.


-----Input-----

The input contains a single number n (2 ≤ n ≤ 10^9) — the size of the board.


-----Output-----

On the first line print the answer to problem — string "white" or string "black", depending on who wins if the both players play optimally. 

If the answer is "white", then you should also print two integers r and c representing the cell (r, c), where the first player should make his first move to win. If there are multiple such cells, print the one with the minimum r. If there are still multiple squares, print the one with the minimum c.


-----Examples-----
Input
2

Output
white
1 2

Input
3

Output
black



-----Note-----

In the first sample test the white queen can capture the black queen at the first move, so the white player wins.

In the second test from the statement if the white queen captures the green pawn located on the central vertical line, then it will be captured by the black queen during the next move. So the only move for the white player is to capture the green pawn located at (2, 1). 

Similarly, the black queen doesn't have any other options but to capture the green pawn located at (2, 3), otherwise if it goes to the middle vertical line, it will be captured by the white queen.

During the next move the same thing happens — neither the white, nor the black queen has other options rather than to capture green pawns situated above them. Thus, the white queen ends up on square (3, 1), and the black queen ends up on square (3, 3). 

In this situation the white queen has to capture any of the green pawns located on the middle vertical line, after that it will be captured by the black queen. Thus, the player who plays for the black queen wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A `bouncy number` is a positive integer whose digits neither increase nor decrease. For example, 1235 is an increasing number, 5321 is a decreasing number, and 2351 is a bouncy number. By definition, all numbers under 100 are non-bouncy, and 101 is the first bouncy number.

Determining if a number is bouncy is easy, but counting all bouncy numbers with N digits can be challenging for large values of N. To complete this kata, you must write a function that takes a number N and return the count of bouncy numbers with N digits. For example, a "4 digit" number includes zero-padded, smaller numbers, such as 0001, 0002, up to 9999.

For clarification, the bouncy numbers between 100 and 125 are: 101, 102, 103, 104, 105, 106, 107, 108, 109, 120, and 121.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For given two circles $c1$ and $c2$, print the coordinates of the cross points of them.

Constraints

* The given circle have at least one cross point and have different center coordinates.
* $-10,000 \leq c1x, c1y, c2x, c2y \leq 10,000$
* $1 \leq c1r, c2r \leq 10,000$

Input

The input is given in the following format.

$c1x\; c1y\; c1r$
$c2x\; c2y\; c2r$


$c1x$, $c1y$ and $c1r$ represent the coordinate and radius of the first circle. $c2x$, $c2y$ and $c2r$ represent the coordinate and radius of the second circle. All input values are given in integers.

Output

Print the coordinates ($x1$, $y1$) and ($x2$, $y2$) of the cross points $p1$ and $p2$ respectively in the following rules.

* If there is one cross point, print two coordinates with the same values.
* Print the coordinate with smaller $x$ first. In case of a tie, print the coordinate with smaller $y$ first.



The output values should be in a decimal fraction with an error less than 0.000001.

Examples

Input

0 0 2
2 0 2


Output

1.00000000 -1.73205080 1.00000000 1.73205080


Input

0 0 2
0 3 1


Output

0.00000000 2.00000000 0.00000000 2.00000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads.

The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number of roads that begins in the city equals to the number of roads that ends in it.

Input

The first line contains a positive integer t (1 ≤ t ≤ 200) — the number of testsets in the input.

Each of the testsets is given in the following way. The first line contains two integers n and m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and the number of roads in Berland. 

The next m lines contain the description of roads in Berland. Each line contains two integers u and v (1 ≤ u, v ≤ n) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities.

It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200.

Pay attention that for hacks, you can only use tests consisting of one testset, so t should be equal to one.

Output

For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it.

In the next m lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once. 

Example

Input

2
5 5
2 1
4 5
2 3
1 3
3 5
7 2
3 7
4 2


Output

3
1 3
3 5
5 4
3 2
2 1
3
2 4
3 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Little Pony and Harmony Chest

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Princess Twilight went to Celestia and Luna's old castle to research the chest from the Elements of Harmony.

A sequence of positive integers *b**i* is harmony if and only if for every two elements of the sequence their greatest common divisor equals 1. According to an ancient book, the key of the chest is a harmony sequence *b**i* which minimizes the following expression:

You are given sequence *a**i*, help Princess Twilight to find the key.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=100) — the number of elements of the sequences *a* and *b*. The next line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=30).

Output Specification:
Output the key — sequence *b**i* that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.

Demo Input:
['5\n1 1 1 1 1\n', '5\n1 6 4 2 8\n']

Demo Output:
['1 1 1 1 1 ', '1 5 3 1 8 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Artem is building a new robot. He has a matrix $a$ consisting of $n$ rows and $m$ columns. The cell located on the $i$-th row from the top and the $j$-th column from the left has a value $a_{i,j}$ written in it. 

If two adjacent cells contain the same value, the robot will break. A matrix is called good if no two adjacent cells contain the same value, where two cells are called adjacent if they share a side. 

Artem wants to increment the values in some cells by one to make $a$ good.

More formally, find a good matrix $b$ that satisfies the following condition —   For all valid ($i,j$), either $b_{i,j} = a_{i,j}$ or $b_{i,j} = a_{i,j}+1$. 

For the constraints of this problem, it can be shown that such a matrix $b$ always exists. If there are several such tables, you can output any of them. Please note that you do not have to minimize the number of increments.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10$). Description of the test cases follows.

The first line of each test case contains two integers $n, m$ ($1 \le n \le 100$, $1 \le m \le 100$)  — the number of rows and columns, respectively.

The following $n$ lines each contain $m$ integers. The $j$-th integer in the $i$-th line is $a_{i,j}$ ($1 \leq a_{i,j} \leq 10^9$).


-----Output-----

For each case, output $n$ lines each containing $m$ integers. The $j$-th integer in the $i$-th line is $b_{i,j}$.


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

Output
1 2
5 6
7 8
2 1
4 3
2 4
3 2



-----Note-----

In all the cases, you can verify that no two adjacent cells have the same value and that $b$ is the same as $a$ with some values incremented by one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The mole family recently decided to dig a new tunnel network. The layout, which has already been decided, consists of chambers and bidirectional tunnels connecting them, forming a connected graph. Mother mole wants to use the opportunity to teach her two mole kids how to dig a tunnel network. 

As an initial quick demonstration, mother mole is going to start by digging out a few of the chambers and tunnels, in the form of a non-self-intersecting path in the planned tunnel network. She will then divide the remaining chambers between the two mole kids, making sure that each mole kid has to dig out the same number of chambers, or else one of the mole kids will become sad. (The tunnels are much easier to dig out, and thus of no concern.) The kids may work on their assigned chambers in any order they like.

Since the mole kids do not have much experience with digging tunnel networks, mother mole realises one issue with her plan: if there is a tunnel between a pair of chambers that are assigned to different mole kids, there is a risk of an accident during the excavation of that tunnel if the other mole kid happens to be digging in the connecting chamber at the same time.

Help mother mole decide which path to use for her initial demonstration, and how to divide the remaining chambers evenly, so that no tunnel connects a pair of chambers assigned to different mole kids. The initial path must consist of at least one chamber and must not visit a chamber more than once.

-----Input-----
The input consists of:
 - One line with two integers $c$ and $t$ ($1 \leq c \leq 2 \cdot 10^5$, $0 \leq t \leq 2 \cdot 10^5$), the number of chambers and tunnels in the planned tunnel network.
 - $t$ lines, each containing two integers $a$ and $b$ ($1 \leq a,b \leq c$, $a \neq b$), describing a bidirectional tunnel between chambers $a$ and $b$.

The chambers are numbered from $1$ to $c$. There is at most one tunnel between any pair of chambers, and there exists a path in the network between any pair of chambers.

-----Output-----
First output two integers $p$ and $s$, the number of chambers on the path in mother mole’s initial demonstration and the number of chambers each mole kid has to dig out. Then output a line containing the $p$ chambers in mother mole’s initial path, in the order that she digs them out. Then output two more lines, each containing the $s$ chambers that the respective mole kid has to dig out, in any order.

The input is chosen such that there exists at least one valid solution. If there are multiple valid solutions, you may output any one of them.

-----Examples-----
Sample Input 1:
3 2
3 1
2 1
Sample Output 1:
3 0
3 1 2

Sample Input 2:
4 3
1 3
2 3
3 4
Sample Output 2:
2 1
3 4
2
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Being a responsible young adult, you have decided to start planning for retirement. Doing some back-of-the-envelope calculations, you figured out you need at least $M$ euros to retire comfortably.

You are currently broke, but fortunately a generous gazillionaire friend has offered to lend you an arbitrary amount of money (as much as you need), without interest, to invest in the stock market. After making some profit you will then return the original sum to your friend, leaving you with the remainder.

Available to you are $n$ investment opportunities, the $i$-th of which costs $c_ i$ euros. You also used your computer science skills to predict that the $i$-th investment will earn you $p_ i$ euros per day. What is the minimum number of days you need before you can pay back your friend and retire? You can only invest once in each investment opportunity, but you can invest in as many different investment opportunities as you like.

For example, consider the first sample. If you buy only the second investment (which costs $15$ euros) you will earn $p_2 = 10$ euros per day. After two days you will have earned $20$ euros, exactly enough to pay off your friend (from whom you borrowed $15$ euros) and retire with the remaining profit ($5$ euros). There is no way to make a net amount of $5$ euros in a single day, so two days is the fastest possible.

-----Input-----
 - The first line contains the number of investment options $1 \leq n \leq 10^5$ and the minimum amount of money you need to retire $1 \leq M \leq 10^9$.
 - Then, $n$ lines follow. Each line $i$ has two integers: the daily profit of this investment ${1 \leq p_ i \leq 10^9}$ and its initial cost $1 \leq c_ i \leq 10^9$.

-----Output-----
Print the minimum number of days needed to recoup your investments and retire with at least $M$ euros, if you follow an optimal investment strategy.

-----Examples-----
Sample Input 1:
2 5
4 10
10 15
Sample Output 1:
2

Sample Input 2:
4 10
1 8
3 12
4 17
10 100
Sample Output 2:
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your work is to write a method that takes a value and an index, and returns the value with the bit at given index flipped.

The bits are numbered from the least significant bit (index 1).

Example:
```python
flip_bit(15, 4) == 7 # 15 in binary is 1111, after flipping 4th bit, it becomes 0111, i.e. 7
flip_bit(15, 5) == 31 # 15 in binary is 1111, 5th bit is 0, after flipping, it becomes 11111, i.e., 31
```
Note : index number can be out of number's range : e.g number is 3 (it has 2 bits) and index number is 8(for C# this number is up to 31) -> result will be 131 

See more examples in test classes

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$ consisting of $n$ integers.

In one move, you can choose some index $i$ ($1 \le i \le n - 2$) and shift the segment $[a_i, a_{i + 1}, a_{i + 2}]$ cyclically to the right (i.e. replace the segment $[a_i, a_{i + 1}, a_{i + 2}]$ with $[a_{i + 2}, a_i, a_{i + 1}]$). 

Your task is to sort the initial array by no more than $n^2$ such operations or say that it is impossible to do that.

You have to answer $t$ independent test cases.


-----Input-----

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

The first line of the test case contains one integer $n$ ($3 \le n \le 500$) — the length of $a$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 500$), where $a_i$ is the $i$-th element $a$.

It is guaranteed that the sum of $n$ does not exceed $500$.


-----Output-----

For each test case, print the answer: -1 on the only line if it is impossible to sort the given array using operations described in the problem statement, or the number of operations $ans$ on the first line and $ans$ integers $idx_1, idx_2, \dots, idx_{ans}$ ($1 \le idx_i \le n - 2$), where $idx_i$ is the index of left border of the segment for the $i$-th operation. You should print indices in order of performing operations.


-----Example-----
Input
5
5
1 2 3 4 5
5
5 4 3 2 1
8
8 4 5 2 3 6 7 3
7
5 2 1 6 4 7 3
6
1 2 3 3 6 4

Output
0

6
3 1 3 2 2 3 
13
2 1 1 6 4 2 4 3 3 4 4 6 6 
-1
4
3 3 4 4

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