apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Stanley and Megan decided to shop in the "Crossmarket" grocery store, which can be represented as a matrix with $$$n$$$ rows and $$$m$$$ columns.

Stanley and Megan can move to an adjacent cell using $$$1$$$ unit of power. Two cells are considered adjacent if they share an edge. To speed up the shopping process, Megan brought her portals with her, and she leaves one in each cell she visits (if there is no portal yet). If a person (Stanley or Megan) is in a cell with a portal, that person can use $$$1$$$ unit of power to teleport to any other cell with a portal, including Megan's starting cell.

They decided to split up: Stanley will go from the upper-left cell (cell with coordinates $$$(1, 1)$$$) to the lower-right cell (cell with coordinates $$$(n, m)$$$), whilst Megan needs to get from the lower-left cell (cell with coordinates $$$(n, 1)$$$) to the upper-right cell (cell with coordinates $$$(1, m)$$$).

What is the minimum total energy needed for them both to do that?

Note that they can choose the time they move. Time does not affect energy.

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

The only line in the test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$).

## Output Format
For each test case print a single integer on a new line – the answer.

## Examples
```input
7
7 5
5 7
1 1
100000 100000
57 228
1 5
5 1
```
```output
15
15
0
299998
340
5
5
```

## Note
In the first test case they can stick to the following plan:

1. Megan (red circle) moves to the cell $$$(7, 3)$$$. Then she goes to the cell $$$(1, 3)$$$, and Stanley (blue circle) does the same.
2. Stanley uses the portal in that cell (cells with portals are grey) to get to the cell $$$(7, 3)$$$. Then he moves to his destination — cell $$$(7, 5)$$$.
3. Megan also finishes her route and goes to the cell $$$(1, 5)$$$.

The total energy spent is $$$(2 + 6) + (2 + 1 + 2) + (2)= 15$$$, which is our final answer.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.5 seconds
Memory limit: 256.0 MB

# Problem
The Narrator has an integer array $$$a$$$ of length $$$n$$$, but he will only tell you the size $$$n$$$ and $$$q$$$ statements, each of them being three integers $$$i, j, x$$$, which means that $$$a_i \mid a_j = x$$$, where $$$|$$$ denotes the bitwise OR operation.

Find the lexicographically smallest array $$$a$$$ that satisfies all the statements.

An array $$$a$$$ is lexicographically smaller than an array $$$b$$$ of the same length if and only if the following holds:

- in the first position where $$$a$$$ and $$$b$$$ differ, the array $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.

## Input Format
In the first line you are given with two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$).

In the next $$$q$$$ lines you are given with three integers $$$i$$$, $$$j$$$, and $$$x$$$ ($$$1 \le i, j \le n$$$, $$$0 \le x < 2^{30}$$$) — the statements.

It is guaranteed that all $$$q$$$ statements hold for at least one array.

## Output Format
On a single line print $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — array $$$a$$$.

## Examples
```input
4 3
1 2 3
1 3 2
4 1 2
```
```output
0 3 2 2
```
-----
```input
1 0
```
```output
0
```
-----
```input
2 1
1 1 1073741823
```
```output
1073741823 0
```

## Note
In the first sample, these are all the arrays satisfying the statements:

- $$$[0, 3, 2, 2]$$$,
- $$$[2, 1, 0, 0]$$$,
- $$$[2, 1, 0, 2]$$$,
- $$$[2, 1, 2, 0]$$$,
- $$$[2, 1, 2, 2]$$$,
- $$$[2, 3, 0, 0]$$$,
- $$$[2, 3, 0, 2]$$$,
- $$$[2, 3, 2, 0]$$$,
- $$$[2, 3, 2, 2]$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Stanley lives in a country that consists of $$$n$$$ cities (he lives in city $$$1$$$). There are bidirectional roads between some of the cities, and you know how long it takes to ride through each of them. Additionally, there is a flight between each pair of cities, the flight between cities $$$u$$$ and $$$v$$$ takes $$$(u - v)^2$$$ time.

Stanley is quite afraid of flying because of watching "Sully: Miracle on the Hudson" recently, so he can take at most $$$k$$$ flights. Stanley wants to know the minimum time of a journey to each of the $$$n$$$ cities from the city $$$1$$$.

## Input Format
In the first line of input there are three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \leq n \leq 10^{5}$$$, $$$1 \leq m \leq 10^{5}$$$, $$$1 \leq k \leq 20$$$) — the number of cities, the number of roads, and the maximal number of flights Stanley can take.

The following $$$m$$$ lines describe the roads. Each contains three integers $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$1 \leq w \leq 10^{9}$$$) — the cities the road connects and the time it takes to ride through. Note that some pairs of cities may be connected by more than one road.

## Output Format
Print $$$n$$$ integers, $$$i$$$-th of which is equal to the minimum time of traveling to city $$$i$$$.

## Examples
```input
3 1 2
1 3 1
```
```output
0 1 1
```
-----
```input
4 3 1
1 2 3
2 4 5
3 4 7
```
```output
0 1 4 6
```
-----
```input
2 1 1
2 1 893746473
```
```output
0 1
```
-----
```input
5 5 2
2 1 33
1 5 93
5 3 48
2 3 21
4 2 1
```
```output
0 1 2 2 3
```

## Note
In the first sample, it takes no time to get to city 1; to get to city 2 it is possible to use a flight between 1 and 2, which will take 1 unit of time; to city 3 you can get via a road from city 1, which will take 1 unit of time.

In the second sample, it also takes no time to get to city 1. To get to city 2 Stanley should use a flight between 1 and 2, which will take 1 unit of time. To get to city 3 Stanley can ride between cities 1 and 2, which will take 3 units of time, and then use a flight between 2 and 3. To get to city 4 Stanley should use a flight between 1 and 2, then take a ride from 2 to 4, which will take 5 units of time.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Burenka and Tonya are playing an old Buryat game with a chip on a board of $$$n \times m$$$ cells.

At the beginning of the game, the chip is located in the lower left corner of the board. In one move, the player can move the chip to the right or up by any odd number of cells (but you cannot move the chip both to the right and up in one move). The one who cannot make a move loses.

Burenka makes the first move, the players take turns. Burenka really wants to win the game, but she is too lazy to come up with a strategy, so you are invited to solve the difficult task of finding it. Name the winner of the game (it is believed that Burenka and Tonya are masters of playing with chips, so they always move in the optimal way).

Chip's starting cell is green, the only cell from which chip can't move is red. if the chip is in the yellow cell, then blue cells are all options to move the chip in one move.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The following is a description of the input data sets.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^9$$$) — the dimensions of the game board.

## Output Format
For each test case print a single line — the name of the winner of the game ("Burenka" or "Tonya").

## Examples
```input
6
1 1
1 4
5 6
2 2
6 3
999999999 1000000000
```
```output
Tonya
Burenka
Burenka
Tonya
Burenka
Burenka
```

## Note
In the first case, Burenka has no move, so Tonya wins.

In the second case, Burenka can move $$$3$$$ cells to the right, after which Tony will not be able to make a move, which means that Burenka wins.

In the third case, Burenka can move $$$5$$$ squares to the right. Then we can say that we have a game on a board of $$$1 \times 5$$$ cells, and Tonya is the first player. In such game the second player wins, so in the original one Burenka will win.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A new entertainment has appeared in Buryatia — a mathematical circus! The magician shows two numbers to the audience — $$$n$$$ and $$$k$$$, where $$$n$$$ is even. Next, he takes all the integers from $$$1$$$ to $$$n$$$, and splits them all into pairs $$$(a, b)$$$ (each integer must be in exactly one pair) so that for each pair the integer $$$(a + k) \cdot b$$$ is divisible by $$$4$$$ (note that the order of the numbers in the pair matters), or reports that, unfortunately for viewers, such a split is impossible.

Burenka really likes such performances, so she asked her friend Tonya to be a magician, and also gave him the numbers $$$n$$$ and $$$k$$$.

Tonya is a wolf, and as you know, wolves do not perform in the circus, even in a mathematical one. Therefore, he asks you to help him. Let him know if a suitable splitting into pairs is possible, and if possible, then tell it.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The following is a description of the input data sets.

The single line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 10^9$$$, $$$n$$$ is even) — the number of integers and the number being added $$$k$$$.

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

## Output Format
For each test case, first output the string "YES" if there is a split into pairs, and "NO" if there is none.

If there is a split, then in the following $$$\frac{n}{2}$$$ lines output pairs of the split, in each line print $$$2$$$ numbers — first the integer $$$a$$$, then the integer $$$b$$$.

## Examples
```input
4
4 1
2 0
12 10
14 11
```
```output
YES
1 2
3 4
NO
YES
3 4
7 8
11 12
2 1
6 5
10 9
YES
1 2
3 4
5 6
7 8
9 10
11 12
13 14
```

## Note
In the first test case, splitting into pairs $$$(1, 2)$$$ and $$$(3, 4)$$$ is suitable, same as splitting into $$$(1, 4)$$$ and $$$(3, 2)$$$.

In the second test case, $$$(1 + 0) \cdot 2 = 1 \cdot (2 + 0) = 2$$$ is not divisible by $$$4$$$, so there is no partition.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The title is a reference to the very first Educational Round from our writers team, Educational Round 18.

There is a bag, containing colored balls. There are $$$n$$$ different colors of balls, numbered from $$$1$$$ to $$$n$$$. There are $$$\mathit{cnt}_i$$$ balls of color $$$i$$$ in the bag. The total amount of balls in the bag is odd (e. g. $$$\mathit{cnt}_1 + \mathit{cnt}_2 + \dots + \mathit{cnt}_n$$$ is odd).

In one move, you can choose two balls with different colors and take them out of the bag.

At some point, all the remaining balls in the bag will have the same color. That's when you can't make moves anymore.

Find any possible color of the remaining balls.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 20$$$) — the number of colors.

The second line contains $$$n$$$ integers $$$\mathit{cnt}_1, \mathit{cnt}_2, \dots, \mathit{cnt}_n$$$ ($$$1 \le \mathit{cnt}_i \le 100$$$) — the amount of balls of each color in the bag.

The total amount of balls in the bag is odd (e. g. $$$\mathit{cnt}_1 + \mathit{cnt}_2 + \dots + \mathit{cnt}_n$$$ is odd).

## Output Format
For each testcase, print a single integer — any possible color of the remaining balls, after you made some moves and can't make moves anymore.

## Examples
```input
3
3
1 1 1
1
9
2
4 7
```
```output
3
1
2
```

## Note
In the first testcase, your first and only move can be one of the following:

- take balls with colors $$$1$$$ and $$$2$$$;
- take balls with colors $$$1$$$ and $$$3$$$;
- take balls with colors $$$2$$$ and $$$3$$$.

After the move, exactly one ball will remain. Its color can be $$$3, 2$$$ or $$$1$$$ depending on the move.

In the second testcase, you can't make moves at all — there is only color of balls already. This color is $$$1$$$.

In the third testcase, you can keep removing one ball of color $$$1$$$ and one ball of color $$$2$$$ until there are no more balls of color $$$1$$$. At the end, three balls of color $$$2$$$ remain.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's define $$$f(x)$$$ for a positive integer $$$x$$$ as the length of the base-10 representation of $$$x$$$ without leading zeros. I like to call it a digital logarithm. Similar to a digital root, if you are familiar with that.

You are given two arrays $$$a$$$ and $$$b$$$, each containing $$$n$$$ positive integers. In one operation, you do the following:

1. pick some integer $$$i$$$ from $$$1$$$ to $$$n$$$;
2. assign either $$$f(a_i)$$$ to $$$a_i$$$ or $$$f(b_i)$$$ to $$$b_i$$$.

Two arrays are considered similar to each other if you can rearrange the elements in both of them, so that they are equal (e. g. $$$a_i = b_i$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$).

What's the smallest number of operations required to make $$$a$$$ and $$$b$$$ similar to each other?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of the testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in each of the arrays.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i < 10^9$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_j < 10^9$$$).

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each testcase, print the smallest number of operations required to make $$$a$$$ and $$$b$$$ similar to each other.

## Examples
```input
4
1
1
1000
4
1 2 3 4
3 1 4 2
3
2 9 3
1 100 9
10
75019 709259 5 611271314 9024533 81871864 9 3 6 4865
9503 2 371245467 6 7 37376159 8 364036498 52295554 169
```
```output
2
0
2
18
```

## Note
In the first testcase, you can apply the digital logarithm to $$$b_1$$$ twice.

In the second testcase, the arrays are already similar to each other.

In the third testcase, you can first apply the digital logarithm to $$$a_1$$$, then to $$$b_2$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Alice and Bob are playing a game. Initially, they are given a non-empty string $$$s$$$, consisting of lowercase Latin letters. The length of the string is even. Each player also has a string of their own, initially empty.

Alice starts, then they alternate moves. In one move, a player takes either the first or the last letter of the string $$$s$$$, removes it from $$$s$$$ and prepends (adds to the beginning) it to their own string.

The game ends when the string $$$s$$$ becomes empty. The winner is the player with a lexicographically smaller string. If the players' strings are equal, then it's a draw.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if there exists such position $$$i$$$ that $$$a_j = b_j$$$ for all $$$j < i$$$ and $$$a_i < b_i$$$.

What is the result of the game if both players play optimally (e. g. both players try to win; if they can't, then try to draw)?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

Each testcase consists of a single line — a non-empty string $$$s$$$, consisting of lowercase Latin letters. The length of the string $$$s$$$ is even.

The total length of the strings over all testcases doesn't exceed $$$2000$$$.

## Output Format
For each testcase, print the result of the game if both players play optimally. If Alice wins, print "Alice". If Bob wins, print "Bob". If it's a draw, print "Draw".

## Examples
```input
2
forces
abba
```
```output
Alice
Draw
```

## Note
One of the possible games Alice and Bob can play in the first testcase:

1. Alice picks the first letter in $$$s$$$: $$$s=$$$"orces", $$$a=$$$"f", $$$b=$$$"";
2. Bob picks the last letter in $$$s$$$: $$$s=$$$"orce", $$$a=$$$"f", $$$b=$$$"s";
3. Alice picks the last letter in $$$s$$$: $$$s=$$$"orc", $$$a=$$$"ef", $$$b=$$$"s";
4. Bob picks the first letter in $$$s$$$: $$$s=$$$"rc", $$$a=$$$"ef", $$$b=$$$"os";
5. Alice picks the last letter in $$$s$$$: $$$s=$$$"r", $$$a=$$$"cef", $$$b=$$$"os";
6. Bob picks the remaining letter in $$$s$$$: $$$s=$$$"", $$$a=$$$"cef", $$$b=$$$"ros".

Alice wins because "cef" < "ros". Neither of the players follows any strategy in this particular example game, so it doesn't show that Alice wins if both play optimally.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 6.0 seconds
Memory limit: 512.0 MB

# Problem
There are $$$n$$$ fishermen who have just returned from a fishing trip. The $$$i$$$-th fisherman has caught a fish of size $$$a_i$$$.

The fishermen will choose some order in which they are going to tell the size of the fish they caught (the order is just a permutation of size $$$n$$$). However, they are not entirely honest, and they may "increase" the size of the fish they have caught.

Formally, suppose the chosen order of the fishermen is $$$[p_1, p_2, p_3, \dots, p_n]$$$. Let $$$b_i$$$ be the value which the $$$i$$$-th fisherman in the order will tell to the other fishermen. The values $$$b_i$$$ are chosen as follows:

- the first fisherman in the order just honestly tells the actual size of the fish he has caught, so $$$b_1 = a_{p_1}$$$;
- every other fisherman wants to tell a value that is strictly greater than the value told by the previous fisherman, and is divisible by the size of the fish that the fisherman has caught. So, for $$$i > 1$$$, $$$b_i$$$ is the smallest integer that is both strictly greater than $$$b_{i-1}$$$ and divisible by $$$a_{p_i}$$$.

For example, let $$$n = 7$$$, $$$a = [1, 8, 2, 3, 2, 2, 3]$$$. If the chosen order is $$$p = [1, 6, 7, 5, 3, 2, 4]$$$, then:

- $$$b_1 = a_{p_1} = 1$$$;
- $$$b_2$$$ is the smallest integer divisible by $$$2$$$ and greater than $$$1$$$, which is $$$2$$$;
- $$$b_3$$$ is the smallest integer divisible by $$$3$$$ and greater than $$$2$$$, which is $$$3$$$;
- $$$b_4$$$ is the smallest integer divisible by $$$2$$$ and greater than $$$3$$$, which is $$$4$$$;
- $$$b_5$$$ is the smallest integer divisible by $$$2$$$ and greater than $$$4$$$, which is $$$6$$$;
- $$$b_6$$$ is the smallest integer divisible by $$$8$$$ and greater than $$$6$$$, which is $$$8$$$;
- $$$b_7$$$ is the smallest integer divisible by $$$3$$$ and greater than $$$8$$$, which is $$$9$$$.

You have to choose the order of fishermen in a way that yields the minimum possible $$$\sum\limits_{i=1}^{n} b_i$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of fishermen.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

## Output Format
Print one integer — the minimum possible value of $$$\sum\limits_{i=1}^{n} b_i$$$ you can obtain by choosing the order of fishermen optimally.

## Examples
```input
7
1 8 2 3 2 2 3
```
```output
33
```
-----
```input
10
5 6 5 6 5 6 5 6 5 6
```
```output
165
```

Now solve the problem and return the code.