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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
You want to plant trees in a square lawn of size $$$n \times n$$$ whose corners have Cartesian coordinates $$$(0, 0)$$$, $$$(n, 0)$$$, $$$(0, n)$$$, and $$$(n, n)$$$. Trees can only be planted at locations with integer coordinates. Every tree will grow roots within a disk of radius $$$r$$$ centered at the location where the tree was planted; such disks must be fully contained in the lawn (possibly touching the boundary of the lawn) and can only intersect each other on their boundaries.

Find a configuration that maximizes the number of trees.

## Input Format
The first and only line contains an integer $$$n$$$ ($$$1 \leq n \leq 20$$$) and a real number $$$r$$$ ($$$0 < r \leq n/2$$$) — the length of the sides of the lawn, and the radius of the disks where each tree will grow roots. The real number $$$r$$$ is given in decimal notation with at least $$$1$$$ and at most $$$3$$$ digits after the decimal point.

## Output Format
In the first line, print the maximum number $$$m$$$ of trees that can be planted.

In the next $$$m$$$ lines, print a configuration that maximizes the number of trees. Specifically, in the $$$(i+1)$$$-th line, print two integers $$$x$$$ and $$$y$$$ — the coordinates of the location where the $$$i$$$-th tree should be planted. You can print the trees in any order.

If there are multiple solutions, print any of them.

## Examples
```input
6 1.241
```
```output
2
4 2
2 4
```
-----
```input
9 2.0
```
```output
4
2 2
7 2
2 6
6 6
```

## Note
For the first sample, the sample output is shown in the following figure. Note that this is not the only configuration that maximizes the number of trees.

For the second sample, the sample output is shown in the following figure. Note that this is not the only configuration that maximizes the number of trees.

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
Deep within a forest lies an ancient tree, home to $$$n$$$ ants living in $$$n$$$ tiny houses, indexed from $$$1$$$ to $$$n$$$, connected by the branches of the tree.

Once a year, all the ants need to gather to watch the EUC. For this, all ants move along the $$$n-1$$$ branches of the tree they live on to meet at the home of one ant.

However, this year the ants could not agree on where to meet and need your help to gather up. You can tell all the ants currently at house $$$u$$$ to move to house $$$v$$$ if there is a branch directly connecting those two houses. However, the ants ignore your command if there are fewer ants gathered in house $$$v$$$ than in house $$$u$$$, i.e., if it would be easier for the ants from house $$$v$$$ to move. This even holds true if no ant at all is currently in house $$$v$$$. You can give this kind of commands as many times as you want.

Is it possible for you to gather all the ants in a single house?

## Input Format
The first line contains one integer $$$n$$$ ($$$1\leq n\leq 200\,000$$$) — the number of ant homes.

Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1\leq u, v\leq n$$$) — there is a branch directly connecting the house $$$u$$$ and house $$$v$$$. It is guaranteed that every ant can reach the house of any other ant just by following the branches of the tree.

## Output Format
Print $$$\texttt{YES}$$$ if it is possible to gather all the ants in a single house. Otherwise, print $$$\texttt{NO}$$$.

## Examples
```input
7
5 1
3 2
4 6
3 6
7 1
1 3
```
```output
YES
```
-----
```input
5
1 4
4 2
3 2
5 3
```
```output
NO
```
-----
```input
6
4 5
5 6
6 1
2 6
3 2
```
```output
YES
```

## Note
In the first sample, you can gather all the ants at house $$$3$$$ as follows:

- You tell to the ant at house $$$4$$$ to move to house $$$6$$$.
- You tell to the ant at house $$$2$$$ to move to house $$$3$$$.
- You tell to the two ants at house $$$6$$$ to move to house $$$3$$$ (which already contains two ants).
- You tell to the ant at house $$$5$$$ to move to house $$$1$$$.
- You tell to the ant at house $$$7$$$ to move to house $$$1$$$ (which already contains two ants).
- You tell to the three ants at house $$$1$$$ to move to house $$$3$$$ (which already contains four ants).

In the second sample, it is impossible to gather all the ants in a single house.

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: 5.0 seconds
Memory limit: 1024.0 MB

# Problem
You just created a new character in your favourite role-playing game and now have to decide how to skill him.

The two skill attributes to be chosen are: damage per hit and hits per second. Damage per hit is the amount of damage you deal with a single hit, while hits per second is the number of hits you can make in one second. Initially, both skill attributes are set at $$$0$$$. You have $$$k$$$ skill points to distribute as you want; in other words, you can choose the values of the two skills so that they are positive integers with sum at most $$$k$$$.

The tutorial of the game (the boring part you want to finish as soon as possible) consists of $$$n$$$ monsters to be killed one after the other. The $$$i$$$-th monster has $$$h_i$$$ health points, i.e., it dies after you have inflicted at least $$$h_i$$$ damage.

How can you assign the two skill attributes to minimize the time necessary to kill all the $$$n$$$ monsters?

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq n\leq200\,000$$$, $$$2\leq k\leq200\,000$$$) — the number of enemies and the number of skill points.

The second line contains $$$n$$$ integers $$$h_i$$$ ($$$1\leq h_i\leq10^{13}$$$) — the health of the $$$i$$$th enemy.

## Output Format
Print two positive integers $$$x$$$ and $$$y$$$ ($$$1\le x, y$$$ and $$$x+y\le k$$$) — the number of skill points you want to invest in damage per hit and hits per second. If there are multiple optimal solutions, print any of them.

## Examples
```input
1 7
14
```
```output
3 4
```
-----
```input
4 9
1 2 3 4
```
```output
4 5
```
-----
```input
5 13
3 4 5 6 7
```
```output
7 6
```

## Note
In the first sample, there is only one monster and you have $$$7$$$ skill points to distribute. If you make $$$3$$$ damage per hit, you will need $$$5$$$ hits to kill it. If you do $$$4$$$ hits per second, you will need $$$1.25$$$ seconds to beat the monster. There is no way to beat the monster faster than this.

In the second sample, you will need one hit for each monster and a total time of $$$0.8$$$ seconds if you distribute $$$4$$$ skill points on damage per hit and the remaining $$$5$$$ points on hits per second.

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: 512.0 MB

# Problem
You are the developer of a dating app which ignores gender completely. The app has $$$n$$$ users, indexed from $$$1$$$ to $$$n$$$. Each user's profile features a list of the activities they enjoy doing. There are $$$m$$$ possible activities, indexed from $$$1$$$ to $$$m$$$.

A match between two users is good if they share at least one activity and, at the same time, both of them like at least one activity that the other user does not like.

Find a good match if it exists.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 200\,000$$$, $$$1 \leq m \leq 10^6$$$) — the number of users and the number of activities.

Each of the following $$$n$$$ lines contains a number $$$k_i$$$ ($$$0 \leq k_i \leq m$$$) — the number of activities that user $$$i$$$ likes — followed by $$$k_i$$$ distinct integers from $$$1$$$ to $$$m$$$ — the activities user $$$i$$$ likes.

It is guaranteed that $$$k_1+k_2+\cdots+k_n$$$ does not exceed $$$10^6$$$.

## Output Format
Print $$$\texttt{YES}$$$ if a good match exists. Otherwise, print $$$\texttt{NO}$$$.

If a good match exists, on the next line print two integers — the indexes of two users that make a match.

## Examples
```input
3 5
3 1 2 4
5 1 2 3 4 5
2 1 5
```
```output
YES
3 1
```
-----
```input
3 3
1 1
1 2
3 2 3 1
```
```output
NO
```

## Note
In the first sample, users $$$1$$$ and $$$3$$$ form a match, because they share activity $$$1$$$, and, furthermore, user $$$3$$$ likes activity $$$5$$$ (which user $$$1$$$ does not like) and user $$$1$$$ likes activity $$$4$$$ (which user $$$3$$$ does not like). Note that users $$$1$$$ and $$$2$$$, as well as users $$$2$$$ and $$$3$$$, do not form a match, as there is no activity that users $$$1$$$ or $$$3$$$ like, and user $$$2$$$ doesn't like.

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
You are given $$$n$$$ disks in the plane. The center of each disk has integer coordinates, and the radius of each disk is a positive integer. No two disks overlap in a region of positive area, but it is possible for disks to be tangent to each other.

Your task is to determine whether it is possible to change the radii of the disks in such a way that:

- Disks that were tangent to each other remain tangent to each other.
- No two disks overlap in a region of positive area.
- The sum of all radii strictly decreases.

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

The next $$$n$$$ lines contain three integers each. The $$$i$$$-th of such lines contains $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$), and $$$r_i$$$ ($$$1 \leq r_i \leq 10^9$$$) — the coordinates of the center, and the radius, of the $$$i$$$-th disk.

## Output Format
Print $$$\texttt{YES}$$$ if it is possible to change the radii in the desired manner. Otherwise, print $$$\texttt{NO}$$$.

## Examples
```input
5
0 2 1
0 0 1
4 -3 4
11 0 3
11 5 2
```
```output
YES
```
-----
```input
4
2 2 2
7 2 3
7 7 2
2 7 3
```
```output
NO
```

## Note
In the first sample, one can decrease the radii of the first and third disk by $$$0.5$$$, and increase the radius of the second disk by $$$0.5$$$. This way, the sum of all radii decreases by $$$0.5$$$. The situation before and after changing the radii is depicted below.

First sample (left) and a valid way to change the radii of the disks (right).

In the second sample, depicted below, there is no way to change the radii of the disks in the desired manner.

Second sample.

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
There are $$$n$$$ lamps numbered $$$1$$$ to $$$n$$$ lined up in a row, initially turned off. You can perform the following operation any number of times (possibly zero):

- Choose two non-adjacent$$${}^\dagger$$$ lamps that are currently turned off, then turn them on.

Determine whether you can reach configuration $$$s$$$, where $$$s_i = 1$$$ means the $$$i$$$-th lamp is turned on, and $$$s_i = 0$$$ otherwise.

$$${}^\dagger$$$ Only lamp $$$i$$$ and $$$i + 1$$$ are adjacent for all $$$1 \le i < n$$$. Note that lamp $$$n$$$ and $$$1$$$ are not adjacent when $$$n \ne 2$$$.

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 50$$$) — the number of lamps.

The second line of each test case contains a binary string $$$s$$$ of size $$$n$$$ — the final desired configuration.

## Output Format
For each test case, print on one line "YES" if we can reach the configuration $$$s$$$ via applying the given operation any number of times. Otherwise, print "NO".

## Examples
```input
5
10
1101010110
10
1001001110
6
000000
1
1
12
111111111111
```
```output
YES
NO
YES
NO
YES
```

## Note
In the first test case, the sequence of operation could have been as follows (note that initially $$$s$$$ is all zero): $$$\mathtt{0000000000} \to \mathtt{\color{red}{1}0000000\color{red}{1}0} \to \mathtt{1\color{red}{1}00000\color{red}{1}10} \to \mathtt{110\color{red}{1}0\color{red}{1}0110}$$$.

In the third test case, we don't have to do any operation.

In the fourth test case, we cannot do any operation, but we need the first lamp to be on. Therefore, it is impossible to achieve the desired state.

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
You are given a permutation $$$p$$$ of size $$$n$$$, as well as a non-negative integer $$$k$$$. You need to construct a permutation $$$q$$$ of size $$$n$$$ such that $$$\operatorname{inv}(q) + \operatorname{inv}(q \cdot p) = k {}^\dagger {}^\ddagger$$$, or determine if it is impossible to do so.

$$${}^\dagger$$$ For two permutations $$$p$$$ and $$$q$$$ of the same size $$$n$$$, the permutation $$$w = q \cdot p$$$ is such that $$$w_i = q_{p_i}$$$ for all $$$1 \le i \le n$$$.

$$${}^\ddagger$$$ For a permutation $$$p$$$ of size $$$n$$$, the function $$$\operatorname{inv}(p)$$$ returns the number of inversions of $$$p$$$, i.e. the number of pairs of indices $$$1 \le i < j \le n$$$ such that $$$p_i > p_j$$$.

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5, 0 \le k \le n(n - 1)$$$) — the size of $$$p$$$ and the target number of inversions.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i$$$'s are pairwise distinct) — the given permutation $$$p$$$.

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

## Output Format
For each test case, print on one line "YES" if there exists a permutation $$$q$$$ that satisfies the given condition, or "NO" if there is no such permutation.

If the answer is "YES", on the second line, print $$$n$$$ integers $$$q_1, q_2, \ldots, q_n$$$ that represent such a satisfactory permutation $$$q$$$. If there are multiple such $$$q$$$'s, print any of them.

## Examples
```input
5
3 4
2 3 1
5 5
2 3 5 1 4
6 11
5 1 2 3 4 6
9 51
3 1 4 2 5 6 7 8 9
1 0
1
```
```output
YES
3 2 1
NO
NO
YES
1 5 9 8 7 6 4 3 2
YES
1
```

## Note
In the first test case, we have $$$q \cdot p = [2, 1, 3]$$$, $$$\operatorname{inv}(q) = 3$$$, and $$$\operatorname{inv}(q \cdot p) = 1$$$.

In the fourth test case, we have $$$q \cdot p = [9, 1, 8, 5, 7, 6, 4, 3, 2]$$$, $$$\operatorname{inv}(q) = 24$$$, and $$$\operatorname{inv}(q \cdot p) = 27$$$.

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
The price of one yogurt at the "Vosmiorochka" store is $$$a$$$ burles, but there is a promotion where you can buy two yogurts for $$$b$$$ burles.

Maxim needs to buy exactly $$$n$$$ yogurts. When buying two yogurts, he can choose to buy them at the regular price or at the promotion price.

What is the minimum amount of burles Maxim should spend to buy $$$n$$$ yogurts?

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

The first and only line of each test case contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$1 \le n \le 100$$$, $$$1 \le a, b \le 30$$$) — the number of yogurts Maxim wants to buy, the price for one yogurt, and the price for two yogurts on promotion.

## Output Format
For each test case, print in a separate line the minimum cost of buying $$$n$$$ yogurts at "Vosmiorochka".

## Examples
```input
4
2 5 9
3 5 9
3 5 11
4 5 11
```
```output
9
14
15
20
```

## Note
In the third test case of the example, it is more advantageous to buy three yogurts for $$$15$$$ burles than two for $$$11$$$ and one for $$$5$$$.

In the fourth test case of the example, you need to buy four yogurts, each for $$$5$$$ burles.

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
A progressive square of size $$$n$$$ is an $$$n \times n$$$ matrix. Maxim chooses three integers $$$a_{1,1}$$$, $$$c$$$, and $$$d$$$ and constructs a progressive square according to the following rules:

$$$$$$a_{i+1,j} = a_{i,j} + c$$$$$$

$$$$$$a_{i,j+1} = a_{i,j} + d$$$$$$

For example, if $$$n = 3$$$, $$$a_{1,1} = 1$$$, $$$c=2$$$, and $$$d=3$$$, then the progressive square looks as follows:

$$$$$$ \begin{pmatrix} 1 & 4 & 7 \\ 3 & 6 & 9 \\ 5 & 8 & 11 \end{pmatrix} $$$$$$

Last month Maxim constructed a progressive square and remembered the values of $$$n$$$, $$$c$$$, and $$$d$$$. Recently, he found an array $$$b$$$ of $$$n^2$$$ integers in random order and wants to make sure that these elements are the elements of that specific square.

It can be shown that for any values of $$$n$$$, $$$a_{1,1}$$$, $$$c$$$, and $$$d$$$, there exists exactly one progressive square that satisfies all the rules.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le {10} ^ 4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$c$$$, and $$$d$$$ ($$$2 \le n \le 500$$$, $$$1 \le c, d \le 10^6$$$) — the size of the square and the values of $$$c$$$ and $$$d$$$ as described in the statement.

The second line of each test case contains $$$n \cdot n$$$ integers $$$b_1, b_2, \dots, b_{n \cdot n}$$$ ($$$1 \le b_i \le 10^9$$$) — the elements found by Maxim.

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

## Output Format
For each test case, output "YES" in a separate line if a progressive square for the given $$$n$$$, $$$c$$$, and $$$d$$$ can be constructed from the array elements $$$a$$$, otherwise output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

## Examples
```input
5
3 2 3
3 9 6 5 7 1 10 4 8
3 2 3
3 9 6 5 7 1 11 4 8
2 100 100
400 300 400 500
3 2 3
3 9 6 6 5 1 11 4 8
4 4 4
15 27 7 19 23 23 11 15 7 3 19 23 11 15 11 15
```
```output
NO
YES
YES
NO
NO
```

Now solve the problem and return the code.