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

# Problem
There are $$$n$$$ points on the plane, $$$(x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)$$$.

You need to place an isosceles triangle with two sides on the coordinate axis to cover all points (a point is covered if it lies inside the triangle or on the side of the triangle). Calculate the minimum length of the shorter side of the triangle.

## Input Format
First line contains one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i,y_i \leq 10^9$$$).

## Output Format
Print the minimum length of the shorter side of the triangle. It can be proved that it's always an integer.

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

## Note
Illustration for the first example:

Illustration for the second 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 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 set of all integers from $$$l$$$ to $$$r$$$ inclusive, $$$l < r$$$, $$$(r - l + 1) \le 3 \cdot 10^5$$$ and $$$(r - l)$$$ is always odd.

You want to split these numbers into exactly $$$\frac{r - l + 1}{2}$$$ pairs in such a way that for each pair $$$(i, j)$$$ the greatest common divisor of $$$i$$$ and $$$j$$$ is equal to $$$1$$$. Each number should appear in exactly one of the pairs.

Print the resulting pairs or output that no solution exists. If there are multiple solutions, print any of them.

## Input Format
The only line contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le 10^{18}$$$, $$$r - l + 1 \le 3 \cdot 10^5$$$, $$$(r - l)$$$ is odd).

## Output Format
If any solution exists, print "YES" in the first line. Each of the next $$$\frac{r - l + 1}{2}$$$ lines should contain some pair of integers. GCD of numbers in each pair should be equal to $$$1$$$. All $$$(r - l + 1)$$$ numbers should be pairwise distinct and should have values from $$$l$$$ to $$$r$$$ inclusive.

If there are multiple solutions, print any of them.

If there exists no solution, print "NO".

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

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
Vasya has a multiset $$$s$$$ consisting of $$$n$$$ integer numbers. Vasya calls some number $$$x$$$ nice if it appears in the multiset exactly once. For example, multiset $$$\{1, 1, 2, 3, 3, 3, 4\}$$$ contains nice numbers $$$2$$$ and $$$4$$$.

Vasya wants to split multiset $$$s$$$ into two multisets $$$a$$$ and $$$b$$$ (one of which may be empty) in such a way that the quantity of nice numbers in multiset $$$a$$$ would be the same as the quantity of nice numbers in multiset $$$b$$$ (the quantity of numbers to appear exactly once in multiset $$$a$$$ and the quantity of numbers to appear exactly once in multiset $$$b$$$).

## Input Format
The first line contains a single integer $$$n~(2 \le n \le 100)$$$.

The second line contains $$$n$$$ integers $$$s_1, s_2, \dots s_n~(1 \le s_i \le 100)$$$ — the multiset $$$s$$$.

## Output Format
If there exists no split of $$$s$$$ to satisfy the given requirements, then print "NO" in the first line.

Otherwise print "YES" in the first line.

The second line should contain a string, consisting of $$$n$$$ characters. $$$i$$$-th character should be equal to 'A' if the $$$i$$$-th element of multiset $$$s$$$ goes to multiset $$$a$$$ and 'B' if if the $$$i$$$-th element of multiset $$$s$$$ goes to multiset $$$b$$$. Elements are numbered from $$$1$$$ to $$$n$$$ in the order they are given in the input.

If there exist multiple solutions, then print any of them.

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

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 grid, consisting of $$$2$$$ rows and $$$n$$$ columns. Each cell of this grid should be colored either black or white.

Two cells are considered neighbours if they have a common border and share the same color. Two cells $$$A$$$ and $$$B$$$ belong to the same component if they are neighbours, or if there is a neighbour of $$$A$$$ that belongs to the same component with $$$B$$$.

Let's call some bicoloring beautiful if it has exactly $$$k$$$ components.

Count the number of beautiful bicolorings. The number can be big enough, so print the answer modulo $$$998244353$$$.

## Input Format
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 1000$$$, $$$1 \le k \le 2n$$$) — the number of columns in a grid and the number of components required.

## Output Format
Print a single integer — the number of beautiful bicolorings modulo $$$998244353$$$.

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

## Note
One of possible bicolorings in sample $$$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
Vasya owns three big integers — $$$a, l, r$$$. Let's define a partition of $$$x$$$ such a sequence of strings $$$s_1, s_2, \dots, s_k$$$ that $$$s_1 + s_2 + \dots + s_k = x$$$, where $$$+$$$ is a concatanation of strings. $$$s_i$$$ is the $$$i$$$-th element of the partition. For example, number $$$12345$$$ has the following partitions: ["1", "2", "3", "4", "5"], ["123", "4", "5"], ["1", "2345"], ["12345"] and lots of others.

Let's call some partition of $$$a$$$ beautiful if each of its elements contains no leading zeros.

Vasya want to know the number of beautiful partitions of number $$$a$$$, which has each of $$$s_i$$$ satisfy the condition $$$l \le s_i \le r$$$. Note that the comparison is the integer comparison, not the string one.

Help Vasya to count the amount of partitions of number $$$a$$$ such that they match all the given requirements. The result can be rather big, so print it modulo $$$998244353$$$.

## Input Format
The first line contains a single integer $$$a~(1 \le a \le 10^{1000000})$$$.

The second line contains a single integer $$$l~(0 \le l \le 10^{1000000})$$$.

The third line contains a single integer $$$r~(0 \le r \le 10^{1000000})$$$.

It is guaranteed that $$$l \le r$$$.

It is also guaranteed that numbers $$$a, l, r$$$ contain no leading zeros.

## Output Format
Print a single integer — the amount of partitions of number $$$a$$$ such that they match all the given requirements modulo $$$998244353$$$.

## Examples
```input
135
1
15
```
```output
2
```
-----
```input
10000
0
9
```
```output
1
```

## Note
In the first test case, there are two good partitions $$$13+5$$$ and $$$1+3+5$$$.

In the second test case, there is one good partition $$$1+0+0+0+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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There is a card game called "Durak", which means "Fool" in Russian. The game is quite popular in the countries that used to form USSR. The problem does not state all the game's rules explicitly — you can find them later yourselves if you want.

To play durak you need a pack of 36 cards. Each card has a suit ("S", "H", "D" and "C") and a rank (in the increasing order "6", "7", "8", "9", "T", "J", "Q", "K" and "A"). At the beginning of the game one suit is arbitrarily chosen as trump.

The players move like that: one player puts one or several of his cards on the table and the other one should beat each of them with his cards.

A card beats another one if both cards have similar suits and the first card has a higher rank then the second one. Besides, a trump card can beat any non-trump card whatever the cards’ ranks are. In all other cases you can not beat the second card with the first one.

You are given the trump suit and two different cards. Determine whether the first one beats the second one or not.

## Input Format
The first line contains the tramp suit. It is "S", "H", "D" or "C".

The second line contains the description of the two different cards. Each card is described by one word consisting of two symbols. The first symbol stands for the rank ("6", "7", "8", "9", "T", "J", "Q", "K" and "A"), and the second one stands for the suit ("S", "H", "D" and "C").

## Output Format
Print "YES" (without the quotes) if the first cards beats the second one. Otherwise, print "NO" (also without the quotes).

## Examples
```input
H
QH 9S
```
```output
YES
```
-----
```input
S
8D 6D
```
```output
YES
```
-----
```input
C
7H AS
```
```output
NO
```

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
Vasya is choosing a laptop. The shop has n laptops to all tastes.

Vasya is interested in the following properties: processor speed, ram and hdd. Vasya is a programmer and not a gamer which is why he is not interested in all other properties.

If all three properties of a laptop are strictly less than those properties of some other laptop, then the first laptop is considered outdated by Vasya. Among all laptops Vasya does not consider outdated, he chooses the cheapest one.

There are very many laptops, which is why Vasya decided to write a program that chooses the suitable laptop. However, Vasya doesn't have his own laptop yet and he asks you to help him.

## Input Format
The first line contains number n (1 ≤ n ≤ 100).

Then follow n lines. Each describes a laptop as speed ram hdd cost. Besides,

- speed, ram, hdd and cost are integers
- 1000 ≤ speed ≤ 4200 is the processor's speed in megahertz
- 256 ≤ ram ≤ 4096 the RAM volume in megabytes
- 1 ≤ hdd ≤ 500 is the HDD in gigabytes
- 100 ≤ cost ≤ 1000 is price in tugriks

All laptops have different prices.

## Output Format
Print a single number — the number of a laptop Vasya will choose. The laptops are numbered with positive integers from 1 to n in the order in which they are given in the input data.

## Examples
```input
5
2100 512 150 200
2000 2048 240 350
2300 1024 200 320
2500 2048 80 300
2000 512 180 150
```
```output
4
```

## Note
In the third sample Vasya considers the first and fifth laptops outdated as all of their properties cannot match those of the third laptop. The fourth one is the cheapest among the laptops that are left. Thus, Vasya chooses the fourth laptop.

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
Lavrenty, a baker, is going to make several buns with stuffings and sell them.

Lavrenty has n grams of dough as well as m different stuffing types. The stuffing types are numerated from 1 to m. Lavrenty knows that he has ai grams left of the i-th stuffing. It takes exactly bi grams of stuffing i and ci grams of dough to cook a bun with the i-th stuffing. Such bun can be sold for di tugriks.

Also he can make buns without stuffings. Each of such buns requires c0 grams of dough and it can be sold for d0 tugriks. So Lavrenty can cook any number of buns with different stuffings or without it unless he runs out of dough and the stuffings. Lavrenty throws away all excess material left after baking.

Find the maximum number of tugriks Lavrenty can earn.

## Input Format
The first line contains 4 integers n, m, c0 and d0 (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10, 1 ≤ c0, d0 ≤ 100). Each of the following m lines contains 4 integers. The i-th line contains numbers ai, bi, ci and di (1 ≤ ai, bi, ci, di ≤ 100).

## Output Format
Print the only number — the maximum number of tugriks Lavrenty can earn.

## Examples
```input
10 2 2 1
7 3 2 100
12 3 1 10
```
```output
241
```
-----
```input
100 1 25 50
15 5 20 10
```
```output
200
```

## Note
To get the maximum number of tugriks in the first sample, you need to cook 2 buns with stuffing 1, 4 buns with stuffing 2 and a bun without any stuffing.

In the second sample Lavrenty should cook 4 buns without stuffings.

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
The Galaxy contains n planets, there are many different living creatures inhabiting each planet. And each creature can get into troubles! Space rescuers know it perfectly well and they are always ready to help anyone who really needs help. All you need to do is call for them.

Now the space rescuers plan to build the largest in the history of the Galaxy rescue station; however, the rescue station's location is yet to be determined. As some cases are real emergencies, the rescuers want to find such a point in the Galaxy from which it would be possible to get to the remotest planet in the minimum possible time. In other words, the rescuers need such point in the space that the distance between it and the planet remotest from it was minimal (if we compare this point with all other possible points in the space). Unfortunately, the rescuers can't sole this problem.

As the planets are quite remote from each other, they can be considered as points in Euclidean three-dimensional space. The distance between points (xi, yi, zi) and (xj, yj, zj) can be calculated by the formula $$p = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2}$$. The rescue station can be positioned in any point in the space. It can also coincide with some planet.

Galaxy is in danger! Save the space rescuers and find the required point for them.

## Input Format
The first line of the input file contains integer n — the number of planets (1 ≤ N ≤ 100). Each of the following n lines contains information about the planets. The i-th line contains three integers xi, yi, zi — the coordinates of the i-th planet ( - 104 ≤ xi, yi, zi ≤ 104, 1 ≤ i ≤ n). No two planets coincide.

## Output Format
Print on the first line of the output file three space-separated real numbers x0, y0, z0 — the coordinates for the future base. If there are several solutions, you are allowed to print any of them. The answer will be accepted if the distance from this point to the remotest planet will differ from the juries' variant in no more than 10 - 6 in absolute or relative value.

## Examples
```input
5
5 0 0
-5 0 0
0 3 4
4 -3 0
2 2 -2
```
```output
0.000 0.000 0.000
```

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
Let's call a string a phone number if it has length 11 and fits the pattern "8xxxxxxxxxx", where each "x" is replaced by a digit.

For example, "80123456789" and "80000000000" are phone numbers, while "8012345678" and "79000000000" are not.

You have $$$n$$$ cards with digits, and you want to use them to make as many phone numbers as possible. Each card must be used in at most one phone number, and you don't have to use all cards. The phone numbers do not necessarily have to be distinct.

## Input Format
The first line contains an integer $$$n$$$ — the number of cards with digits that you have ($$$1 \leq n \leq 100$$$).

The second line contains a string of $$$n$$$ digits (characters "0", "1", ..., "9") $$$s_1, s_2, \ldots, s_n$$$. The string will not contain any other characters, such as leading or trailing spaces.

## Output Format
If at least one phone number can be made from these cards, output the maximum number of phone numbers that can be made. Otherwise, output 0.

## Examples
```input
11
00000000008
```
```output
1
```
-----
```input
22
0011223344556677889988
```
```output
2
```
-----
```input
11
31415926535
```
```output
0
```

## Note
In the first example, one phone number, "8000000000", can be made from these cards.

In the second example, you can make two phone numbers from the cards, for example, "80123456789" and "80123456789".

In the third example you can't make any phone number from the given cards.

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
You are given a positive integer $$$n$$$.

Let $$$S(x)$$$ be sum of digits in base 10 representation of $$$x$$$, for example, $$$S(123) = 1 + 2 + 3 = 6$$$, $$$S(0) = 0$$$.

Your task is to find two integers $$$a, b$$$, such that $$$0 \leq a, b \leq n$$$, $$$a + b = n$$$ and $$$S(a) + S(b)$$$ is the largest possible among all such pairs.

## Input Format
The only line of input contains an integer $$$n$$$ $$$(1 \leq n \leq 10^{12})$$$.

## Output Format
Print largest $$$S(a) + S(b)$$$ among all pairs of integers $$$a, b$$$, such that $$$0 \leq a, b \leq n$$$ and $$$a + b = n$$$.

## Examples
```input
35
```
```output
17
```
-----
```input
10000000000
```
```output
91
```

## Note
In the first example, you can choose, for example, $$$a = 17$$$ and $$$b = 18$$$, so that $$$S(17) + S(18) = 1 + 7 + 1 + 8 = 17$$$. It can be shown that it is impossible to get a larger answer.

In the second test example, you can choose, for example, $$$a = 5000000001$$$ and $$$b = 4999999999$$$, with $$$S(5000000001) + S(4999999999) = 91$$$. It can be shown that it is impossible to get a larger answer.

Now solve the problem and return the code.