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
Monocarp has decided to buy a new TV set and hang it on the wall in his flat. The wall has enough free space so Monocarp can buy a TV set with screen width not greater than $$$a$$$ and screen height not greater than $$$b$$$. Monocarp is also used to TV sets with a certain aspect ratio: formally, if the width of the screen is $$$w$$$, and the height of the screen is $$$h$$$, then the following condition should be met: $$$\frac{w}{h} = \frac{x}{y}$$$.

There are many different TV sets in the shop. Monocarp is sure that for any pair of positive integers $$$w$$$ and $$$h$$$ there is a TV set with screen width $$$w$$$ and height $$$h$$$ in the shop.

Monocarp isn't ready to choose the exact TV set he is going to buy. Firstly he wants to determine the optimal screen resolution. He has decided to try all possible variants of screen size. But he must count the number of pairs of positive integers $$$w$$$ and $$$h$$$, beforehand, such that $$$(w \le a)$$$, $$$(h \le b)$$$ and $$$(\frac{w}{h} = \frac{x}{y})$$$.

In other words, Monocarp wants to determine the number of TV sets having aspect ratio $$$\frac{x}{y}$$$, screen width not exceeding $$$a$$$, and screen height not exceeding $$$b$$$. Two TV sets are considered different if they have different screen width or different screen height.

## Input Format
The first line contains four integers $$$a$$$, $$$b$$$, $$$x$$$, $$$y$$$ ($$$1 \le a, b, x, y \le 10^{18}$$$) — the constraints on the screen width and height, and on the aspect ratio.

## Output Format
Print one integer — the number of different variants to choose TV screen width and screen height so that they meet the aforementioned constraints.

## Examples
```input
17 15 5 3
```
```output
3
```
-----
```input
14 16 7 22
```
```output
0
```
-----
```input
4 2 6 4
```
```output
1
```
-----
```input
1000000000000000000 1000000000000000000 999999866000004473 999999822000007597
```
```output
1000000063
```

## Note
In the first example, there are $$$3$$$ possible variants: $$$(5, 3)$$$, $$$(10, 6)$$$, $$$(15, 9)$$$.

In the second example, there is no TV set meeting the constraints.

In the third example, there is only one variant: $$$(3, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Monocarp has drawn a tree (an undirected connected acyclic graph) and then has given each vertex an index. All indices are distinct numbers from $$$1$$$ to $$$n$$$. For every edge $$$e$$$ of this tree, Monocarp has written two numbers: the maximum indices of the vertices of the two components formed if the edge $$$e$$$ (and only this edge) is erased from the tree.

Monocarp has given you a list of $$$n - 1$$$ pairs of numbers. He wants you to provide an example of a tree that will produce the said list if this tree exists. If such tree does not exist, say so.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 1\,000$$$) — the number of vertices in the tree.

Each of the next $$$n-1$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ each ($$$1 \le a_i < b_i \le n$$$) — the maximal indices of vertices in the components formed if the $$$i$$$-th edge is removed.

## Output Format
If there is no such tree that can produce the given list of pairs, print "NO" (without quotes).

Otherwise print "YES" (without quotes) in the first line and the edges of the tree in the next $$$n - 1$$$ lines. Each of the last $$$n - 1$$$ lines should contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$) — vertices connected by an edge.

Note: The numeration of edges doesn't matter for this task. Your solution will be considered correct if your tree produces the same pairs as given in the input file (possibly reordered). That means that you can print the edges of the tree you reconstructed in any order.

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

## Note
Possible tree from the first example. Dotted lines show edges you need to remove to get appropriate pairs.

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 tube which is reflective inside represented as two non-coinciding, but parallel to $$$Ox$$$ lines. Each line has some special integer points — positions of sensors on sides of the tube.

You are going to emit a laser ray in the tube. To do so, you have to choose two integer points $$$A$$$ and $$$B$$$ on the first and the second line respectively (coordinates can be negative): the point $$$A$$$ is responsible for the position of the laser, and the point $$$B$$$ — for the direction of the laser ray. The laser ray is a ray starting at $$$A$$$ and directed at $$$B$$$ which will reflect from the sides of the tube (it doesn't matter if there are any sensors at a reflection point or not). A sensor will only register the ray if the ray hits exactly at the position of the sensor.

Examples of laser rays. Note that image contains two examples. The $$$3$$$ sensors (denoted by black bold points on the tube sides) will register the blue ray but only $$$2$$$ will register the red.

Calculate the maximum number of sensors which can register your ray if you choose points $$$A$$$ and $$$B$$$ on the first and the second lines respectively.

## Input Format
The first line contains two integers $$$n$$$ and $$$y_1$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le y_1 \le 10^9$$$) — number of sensors on the first line and its $$$y$$$ coordinate.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — $$$x$$$ coordinates of the sensors on the first line in the ascending order.

The third line contains two integers $$$m$$$ and $$$y_2$$$ ($$$1 \le m \le 10^5$$$, $$$y_1 < y_2 \le 10^9$$$) — number of sensors on the second line and its $$$y$$$ coordinate.

The fourth line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \le b_i \le 10^9$$$) — $$$x$$$ coordinates of the sensors on the second line in the ascending order.

## Output Format
Print the only integer — the maximum number of sensors which can register the ray.

## Examples
```input
3 1
1 5 6
1 3
3
```
```output
3
```

## Note
One of the solutions illustrated on the image by pair $$$A_2$$$ and $$$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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
Buber is a Berland technology company that specializes in waste of investor's money. Recently Buber decided to transfer its infrastructure to a cloud. The company decided to rent CPU cores in the cloud for $$$n$$$ consecutive days, which are numbered from $$$1$$$ to $$$n$$$. Buber requires $$$k$$$ CPU cores each day.

The cloud provider offers $$$m$$$ tariff plans, the $$$i$$$-th tariff plan is characterized by the following parameters:

- $$$l_i$$$ and $$$r_i$$$ — the $$$i$$$-th tariff plan is available only on days from $$$l_i$$$ to $$$r_i$$$, inclusive,
- $$$c_i$$$ — the number of cores per day available for rent on the $$$i$$$-th tariff plan,
- $$$p_i$$$ — the price of renting one core per day on the $$$i$$$-th tariff plan.

Buber can arbitrarily share its computing core needs between the tariff plans. Every day Buber can rent an arbitrary number of cores (from 0 to $$$c_i$$$) on each of the available plans. The number of rented cores on a tariff plan can vary arbitrarily from day to day.

Find the minimum amount of money that Buber will pay for its work for $$$n$$$ days from $$$1$$$ to $$$n$$$. If on a day the total number of cores for all available tariff plans is strictly less than $$$k$$$, then this day Buber will have to work on fewer cores (and it rents all the available cores), otherwise Buber rents exactly $$$k$$$ cores this day.

## Input Format
The first line of the input contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n,k \le 10^6, 1 \le m \le 2\cdot10^5$$$) — the number of days to analyze, the desired daily number of cores, the number of tariff plans.

The following $$$m$$$ lines contain descriptions of tariff plans, one description per line. Each line contains four integers $$$l_i$$$, $$$r_i$$$, $$$c_i$$$, $$$p_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$1 \le c_i, p_i \le 10^6$$$), where $$$l_i$$$ and $$$r_i$$$ are starting and finishing days of the $$$i$$$-th tariff plan, $$$c_i$$$ — number of cores, $$$p_i$$$ — price of a single core for daily rent on the $$$i$$$-th tariff plan.

## Output Format
Print a single integer number — the minimal amount of money that Buber will pay.

## Examples
```input
5 7 3
1 4 5 3
1 3 5 2
2 5 10 1
```
```output
44
```
-----
```input
7 13 5
2 3 10 7
3 5 10 10
1 2 10 6
4 5 10 9
3 4 10 8
```
```output
462
```
-----
```input
4 100 3
3 3 2 5
1 1 3 2
2 4 4 4
```
```output
64
```

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
Berhattan is the capital of Berland. There are $$$n$$$ streets running parallel in the east-west direction (horizontally), and there are $$$m$$$ avenues running parallel in the south-north direction (vertically). Each street intersects with each avenue, forming a crossroad. So in total there are $$$n \cdot m$$$ crossroads in Berhattan.

Recently, the government has changed in Berland. The new government wants to name all avenues and all streets after heroes of revolution.

The special committee prepared the list of $$$k$$$ names. Only these names can be used as new names for streets and avenues. Each name can be used at most once.

The members of committee want to name streets and avenues in the way that minimizes inconvenience for residents. They believe that if street and avenue names start with the same letter, then their crossroad will be inconvenient. Hence only the first letter of each name matters.

Given first letters of $$$k$$$ names, find $$$C$$$ — minimal possible number of inconvenient crossroads in Berhattan after the naming process.

## Input Format
Input contains one or several test cases to process. The first line contains $$$t$$$ ($$$1 \le t \le 30000$$$) — the number of test cases. Solve test cases separately, test cases are completely independent and do not affect each other.

The description of $$$t$$$ test cases follows. Each test case starts with line with space-separated numbers $$$n, m, k$$$ ($$$1 \le n,m \le 30000$$$; $$$n+m \le k \le 2\cdot10^5$$$) — the number of streets, number of avenues and the number of names in the committee's list, respectively.

The the second line of each test case contains a string of $$$k$$$ uppercase English letters. $$$i$$$-th letter of the string is the first letter of $$$i$$$-th name from the committee's list.

It's guaranteed that the sum of numbers $$$n$$$ from all test cases is not greater than $$$30000$$$. Similarly, the sum of numbers $$$m$$$ from all test cases is not greater than $$$30000$$$. The sum of numbers $$$k$$$ from all test cases is not greater than $$$2\cdot10^5$$$.

## Output Format
For each test case print single number $$$C$$$ in the separate line — minimal possible number of inconvenient crossroads in Berhattan after the naming process.

## Examples
```input
2
2 3 9
EEZZEEZZZ
2 7 9
EEZZEEZZZ
```
```output
0
4
```
-----
```input
2
4 4 8
CZBBCZBC
1 1 4
TTCT
```
```output
1
0
```

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

# Problem
Berland has $$$n$$$ cities, some of which are connected by roads. Each road is bidirectional, connects two distinct cities and for each two cities there's at most one road connecting them.

The president of Berland decided to split country into $$$r$$$ states in such a way that each city will belong to exactly one of these $$$r$$$ states.

After this split each road will connect either cities of the same state or cities of the different states. Let's call roads that connect two cities of the same state "inner" roads.

The president doesn't like odd people, odd cities and odd numbers, so he wants this split to be done in such a way that each city would have even number of "inner" roads connected to it.

Please help president to find smallest possible $$$r$$$ for which such a split exists.

## Input Format
The input contains one or several test cases. The first input line contains a single integer number $$$t$$$ — number of test cases. Then, $$$t$$$ test cases follow. Solve test cases separately, test cases are completely independent and do not affect each other.

Then $$$t$$$ blocks of input data follow. Each block starts from empty line which separates it from the remaining input data. The second line of each block contains two space-separated integers $$$n$$$, $$$m$$$ ($$$1 \le n \le 2000$$$, $$$0 \le m \le 10000$$$) — the number of cities and number of roads in the Berland. Each of the next $$$m$$$ lines contains two space-separated integers — $$$x_i$$$, $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$), which denotes that the $$$i$$$-th road connects cities $$$x_i$$$ and $$$y_i$$$. Each pair of cities are connected by at most one road.

Sum of values $$$n$$$ across all test cases doesn't exceed $$$2000$$$. Sum of values $$$m$$$ across all test cases doesn't exceed $$$10000$$$.

## Output Format
For each test case first print a line containing a single integer $$$r$$$ — smallest possible number of states for which required split is possible. In the next line print $$$n$$$ space-separated integers in range from $$$1$$$ to $$$r$$$, inclusive, where the $$$j$$$-th number denotes number of state for the $$$j$$$-th city. If there are multiple solutions, print any.

## Examples
```input
2
5 3
1 2
2 5
1 5
6 5
1 2
2 3
3 4
4 2
4 1
```
```output
1
1 1 1 1 1
2
2 1 1 1 1 1
```

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
Little Sofia is in fourth grade. Today in the geometry lesson she learned about segments and squares. On the way home, she decided to draw $$$n$$$ squares in the snow with a side length of $$$1$$$. For simplicity, we assume that Sofia lives on a plane and can draw only segments of length $$$1$$$, parallel to the coordinate axes, with vertices at integer points.

In order to draw a segment, Sofia proceeds as follows. If she wants to draw a vertical segment with the coordinates of the ends $$$(x, y)$$$ and $$$(x, y+1)$$$. Then Sofia looks if there is already a drawn segment with the coordinates of the ends $$$(x', y)$$$ and $$$(x', y+1)$$$ for some $$$x'$$$. If such a segment exists, then Sofia quickly draws a new segment, using the old one as a guideline. If there is no such segment, then Sofia has to take a ruler and measure a new segment for a long time. Same thing happens when Sofia wants to draw a horizontal segment, but only now she checks for the existence of a segment with the same coordinates $$$x$$$, $$$x+1$$$ and the differing coordinate $$$y$$$.

For example, if Sofia needs to draw one square, she will have to draw two segments using a ruler:

After that, she can draw the remaining two segments, using the first two as a guide:

If Sofia needs to draw two squares, she will have to draw three segments using a ruler:

After that, she can draw the remaining four segments, using the first three as a guide:

Sofia is in a hurry, so she wants to minimize the number of segments that she will have to draw with a ruler without a guide. Help her find this minimum number.

## Input Format
The only line of input contains a single integer $$$n$$$ ($$$1 \le n \le 10^{9}$$$), the number of squares that Sofia wants to draw.

## Output Format
Print single integer, the minimum number of segments that Sofia will have to draw with a ruler without a guide in order to draw $$$n$$$ squares in the manner described above.

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

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
Andrey received a postcard from Irina. It contained only the words "Hello, Andrey!", and a strange string consisting of lowercase Latin letters, snowflakes and candy canes. Andrey thought that this string is an encrypted message, and decided to decrypt it.

Andrey noticed that snowflakes and candy canes always stand after the letters, so he supposed that the message was encrypted as follows. Candy cane means that the letter before it can be removed, or can be left. A snowflake means that the letter before it can be removed, left, or repeated several times.

For example, consider the following string:

This string can encode the message «happynewyear». For this, candy canes and snowflakes should be used as follows:

- candy cane 1: remove the letter w,
- snowflake 1: repeat the letter p twice,
- candy cane 2: leave the letter n,
- snowflake 2: remove the letter w,
- snowflake 3: leave the letter e.

Please note that the same string can encode different messages. For example, the string above can encode «hayewyar», «happpppynewwwwwyear», and other messages.

Andrey knows that messages from Irina usually have a length of $$$k$$$ letters. Help him to find out if a given string can encode a message of $$$k$$$ letters, and if so, give an example of such a message.

## Input Format
The first line contains the string received in the postcard. The string consists only of lowercase Latin letters, as well as the characters «*» and «?», meaning snowflake and candy cone, respectively. These characters can only appear immediately after the letter. The length of the string does not exceed $$$200$$$.

The second line contains an integer number $$$k$$$ ($$$1 \leq k \leq 200$$$), the required message length.

## Output Format
Print any message of length $$$k$$$ that the given string can encode, or «Impossible» if such a message does not exist.

## Examples
```input
hw?ap*yn?eww*ye*ar
12
```
```output
happynewyear
```
-----
```input
ab?a
2
```
```output
aa
```
-----
```input
ab?a
3
```
```output
aba
```
-----
```input
ababb
5
```
```output
ababb
```
-----
```input
ab?a
1
```
```output
Impossible
```

Now solve the problem and return the code.