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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Chouti was doing a competitive programming competition. However, after having all the problems accepted, he got bored and decided to invent some small games.

He came up with the following game. The player has a positive integer $$$n$$$. Initially the value of $$$n$$$ equals to $$$v$$$ and the player is able to do the following operation as many times as the player want (possibly zero): choose a positive integer $$$x$$$ that $$$x<n$$$ and $$$x$$$ is not a divisor of $$$n$$$, then subtract $$$x$$$ from $$$n$$$. The goal of the player is to minimize the value of $$$n$$$ in the end.

Soon, Chouti found the game trivial. Can you also beat the game?

## Input Format
The input contains only one integer in the first line: $$$v$$$ ($$$1 \le v \le 10^9$$$), the initial value of $$$n$$$.

## Output Format
Output a single integer, the minimum value of $$$n$$$ the player can get.

## Examples
```input
8
```
```output
1
```
-----
```input
1
```
```output
1
```

## Note
In the first example, the player can choose $$$x=3$$$ in the first turn, then $$$n$$$ becomes $$$5$$$. He can then choose $$$x=4$$$ in the second turn to get $$$n=1$$$ as the result. There are other ways to get this minimum. However, for example, he cannot choose $$$x=2$$$ in the first turn because $$$2$$$ is a divisor of $$$8$$$.

In the second example, since $$$n=1$$$ initially, the player can do nothing.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Chouti and his classmates are going to the university soon. To say goodbye to each other, the class has planned a big farewell party in which classmates, teachers and parents sang and danced.

Chouti remembered that $$$n$$$ persons took part in that party. To make the party funnier, each person wore one hat among $$$n$$$ kinds of weird hats numbered $$$1, 2, \ldots n$$$. It is possible that several persons wore hats of the same kind. Some kinds of hats can remain unclaimed by anyone.

After the party, the $$$i$$$-th person said that there were $$$a_i$$$ persons wearing a hat differing from his own.

It has been some days, so Chouti forgot all about others' hats, but he is curious about that. Let $$$b_i$$$ be the number of hat type the $$$i$$$-th person was wearing, Chouti wants you to find any possible $$$b_1, b_2, \ldots, b_n$$$ that doesn't contradict with any person's statement. Because some persons might have a poor memory, there could be no solution at all.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of persons in the party.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n-1$$$), the statements of people.

## Output Format
If there is no solution, print a single line "Impossible".

Otherwise, print "Possible" and then $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$).

If there are multiple answers, print any of them.

## Examples
```input
3
0 0 0
```
```output
Possible
1 1 1
```
-----
```input
5
3 3 2 2 2
```
```output
Possible
1 1 2 2 2
```
-----
```input
4
0 1 2 3
```
```output
Impossible
```

## Note
In the answer to the first example, all hats are the same, so every person will say that there were no persons wearing a hat different from kind $$$1$$$.

In the answer to the second example, the first and the second person wore the hat with type $$$1$$$ and all other wore a hat of type $$$2$$$.

So the first two persons will say there were three persons with hats differing from their own. Similarly, three last persons will say there were two persons wearing a hat different from their own.

In the third example, it can be shown that no solution exists.

In the first and the second example, other possible configurations are possible.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
On his free time, Chouti likes doing some housework. He has got one new task, paint some bricks in the yard.

There are $$$n$$$ bricks lined in a row on the ground. Chouti has got $$$m$$$ paint buckets of different colors at hand, so he painted each brick in one of those $$$m$$$ colors.

Having finished painting all bricks, Chouti was satisfied. He stood back and decided to find something fun with these bricks. After some counting, he found there are $$$k$$$ bricks with a color different from the color of the brick on its left (the first brick is not counted, for sure).

So as usual, he needs your help in counting how many ways could he paint the bricks. Two ways of painting bricks are different if there is at least one brick painted in different colors in these two ways. Because the answer might be quite big, you only need to output the number of ways modulo $$$998\,244\,353$$$.

## Input Format
The first and only line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n,m \leq 2000, 0 \leq k \leq n-1$$$) — the number of bricks, the number of colors, and the number of bricks, such that its color differs from the color of brick to the left of it.

## Output Format
Print one integer — the number of ways to color bricks modulo $$$998\,244\,353$$$.

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

## Note
In the first example, since $$$k=0$$$, the color of every brick should be the same, so there will be exactly $$$m=3$$$ ways to color the bricks.

In the second example, suppose the two colors in the buckets are yellow and lime, the following image shows all $$$4$$$ possible colorings.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Chouti was tired of the tedious homework, so he opened up an old programming problem he created years ago.

You are given a connected undirected graph with $$$n$$$ vertices and $$$m$$$ weighted edges. There are $$$k$$$ special vertices: $$$x_1, x_2, \ldots, x_k$$$.

Let's define the cost of the path as the maximum weight of the edges in it. And the distance between two vertexes as the minimum cost of the paths connecting them.

For each special vertex, find another special vertex which is farthest from it (in terms of the previous paragraph, i.e. the corresponding distance is maximum possible) and output the distance between them.

The original constraints are really small so he thought the problem was boring. Now, he raises the constraints and hopes you can solve it for him.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \leq k \leq n \leq 10^5$$$, $$$n-1 \leq m \leq 10^5$$$) — the number of vertices, the number of edges and the number of special vertices.

The second line contains $$$k$$$ distinct integers $$$x_1, x_2, \ldots, x_k$$$ ($$$1 \leq x_i \leq n$$$).

Each of the following $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ ($$$1 \leq u,v \leq n, 1 \leq w \leq 10^9$$$), denoting there is an edge between $$$u$$$ and $$$v$$$ of weight $$$w$$$. The given graph is undirected, so an edge $$$(u, v)$$$ can be used in the both directions.

The graph may have multiple edges and self-loops.

It is guaranteed, that the graph is connected.

## Output Format
The first and only line should contain $$$k$$$ integers. The $$$i$$$-th integer is the distance between $$$x_i$$$ and the farthest special vertex from it.

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

## Note
In the first example, the distance between vertex $$$1$$$ and $$$2$$$ equals to $$$2$$$ because one can walk through the edge of weight $$$2$$$ connecting them. So the distance to the farthest node for both $$$1$$$ and $$$2$$$ equals to $$$2$$$.

In the second example, one can find that distance between $$$1$$$ and $$$2$$$, distance between $$$1$$$ and $$$3$$$ are both $$$3$$$ and the distance between $$$2$$$ and $$$3$$$ is $$$2$$$.

The graph may have multiple edges between and self-loops, as in the first example.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Chouti is working on a strange math problem.

There was a sequence of $$$n$$$ positive integers $$$x_1, x_2, \ldots, x_n$$$, where $$$n$$$ is even. The sequence was very special, namely for every integer $$$t$$$ from $$$1$$$ to $$$n$$$, $$$x_1+x_2+...+x_t$$$ is a square of some integer number (that is, a perfect square).

Somehow, the numbers with odd indexes turned to be missing, so he is only aware of numbers on even positions, i.e. $$$x_2, x_4, x_6, \ldots, x_n$$$. The task for him is to restore the original sequence. Again, it's your turn to help him.

The problem setter might make mistakes, so there can be no possible sequence at all. If there are several possible sequences, you can output any.

## Input Format
The first line contains an even number $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line contains $$$\frac{n}{2}$$$ positive integers $$$x_2, x_4, \ldots, x_n$$$ ($$$1 \le x_i \le 2 \cdot 10^5$$$).

## Output Format
If there are no possible sequence, print "No".

Otherwise, print "Yes" and then $$$n$$$ positive integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le 10^{13}$$$), where $$$x_2, x_4, \ldots, x_n$$$ should be same as in input data. If there are multiple answers, print any.

Note, that the limit for $$$x_i$$$ is larger than for input data. It can be proved that in case there is an answer, there must be a possible sequence satisfying $$$1 \le x_i \le 10^{13}$$$.

## Examples
```input
6
5 11 44
```
```output
Yes
4 5 16 11 64 44
```
-----
```input
2
9900
```
```output
Yes
100 9900
```
-----
```input
6
314 1592 6535
```
```output
No
```

## Note
In the first example

- $$$x_1=4$$$
- $$$x_1+x_2=9$$$
- $$$x_1+x_2+x_3=25$$$
- $$$x_1+x_2+x_3+x_4=36$$$
- $$$x_1+x_2+x_3+x_4+x_5=100$$$
- $$$x_1+x_2+x_3+x_4+x_5+x_6=144$$$

In the second example, $$$x_1=100$$$, $$$x_1+x_2=10000$$$. They are all perfect squares. There're other answers possible. For example, $$$x_1=22500$$$ is another answer.

In the third example, it is possible to show, that no such sequence exists.

Now solve the problem and return the code.