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

# Problem
You are given $$$n$$$ strings $$$s_1, s_2, \dots, s_n$$$, consisting of lowercase Latin letters. Let $$$|x|$$$ be the length of string $$$x$$$.

Let a collapse $$$C(a, b)$$$ of two strings $$$a$$$ and $$$b$$$ be the following operation:

- if $$$a$$$ is empty, $$$C(a, b) = b$$$;
- if $$$b$$$ is empty, $$$C(a, b) = a$$$;
- if the last letter of $$$a$$$ is equal to the first letter of $$$b$$$, then $$$C(a, b) = C(a_{1,|a|-1}, b_{2,|b|})$$$, where $$$s_{l,r}$$$ is the substring of $$$s$$$ from the $$$l$$$-th letter to the $$$r$$$-th one;
- otherwise, $$$C(a, b) = a + b$$$, i. e. the concatenation of two strings.

Calculate $$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

Each of the next $$$n$$$ lines contains a string $$$s_i$$$ ($$$1 \le |s_i| \le 10^6$$$), consisting of lowercase Latin letters.

The total length of the strings doesn't exceed $$$10^6$$$.

## Output Format
Print a single integer — $$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$$$.

## Examples
```input
3
aba
ab
ba
```
```output
20
```
-----
```input
5
abab
babx
xab
xba
bab
```
```output
126
```

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
As you very well know, this year's funkiest numbers are so called triangular numbers (that is, integers that are representable as $$\frac{k(k+1)}{2}$$, where k is some positive integer), and the coolest numbers are those that are representable as a sum of two triangular numbers.

A well-known hipster Andrew adores everything funky and cool but unfortunately, he isn't good at maths. Given number n, help him define whether this number can be represented by a sum of two triangular numbers (not necessarily different)!

## Input Format
The first input line contains an integer n (1 ≤ n ≤ 109).

## Output Format
Print "YES" (without the quotes), if n can be represented as a sum of two triangular numbers, otherwise print "NO" (without the quotes).

## Examples
```input
256
```
```output
YES
```
-----
```input
512
```
```output
NO
```

## Note
In the first sample number $$256 = \frac{2\cdot3}{2} + \frac{22\cdot23}{2}$$.

In the second sample number 512 can not be represented as a sum of two triangular numbers.

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
In Berland the opposition is going to arrange mass walking on the boulevard. The boulevard consists of n tiles that are lain in a row and are numbered from 1 to n from right to left. The opposition should start walking on the tile number 1 and the finish on the tile number n. During the walk it is allowed to move from right to left between adjacent tiles in a row, and jump over a tile. More formally, if you are standing on the tile number i (i < n - 1), you can reach the tiles number i + 1 or the tile number i + 2 from it (if you stand on the tile number n - 1, you can only reach tile number n). We can assume that all the opposition movements occur instantaneously.

In order to thwart an opposition rally, the Berland bloody regime organized the rain. The tiles on the boulevard are of poor quality and they are rapidly destroyed in the rain. We know that the i-th tile is destroyed after ai days of rain (on day ai tile isn't destroyed yet, and on day ai + 1 it is already destroyed). Of course, no one is allowed to walk on the destroyed tiles! So the walk of the opposition is considered thwarted, if either the tile number 1 is broken, or the tile number n is broken, or it is impossible to reach the tile number n from the tile number 1 if we can walk on undestroyed tiles.

The opposition wants to gather more supporters for their walk. Therefore, the more time they have to pack, the better. Help the opposition to calculate how much time they still have and tell us for how many days the walk from the tile number 1 to the tile number n will be possible.

## Input Format
The first line contains integer n (1 ≤ n ≤ 103) — the boulevard's length in tiles.

The second line contains n space-separated integers ai — the number of days after which the i-th tile gets destroyed (1 ≤ ai ≤ 103).

## Output Format
Print a single number — the sought number of days.

## Examples
```input
4
10 3 5 10
```
```output
5
```
-----
```input
5
10 2 8 3 5
```
```output
5
```

## Note
In the first sample the second tile gets destroyed after day three, and the only path left is 1 → 3 → 4. After day five there is a two-tile gap between the first and the last tile, you can't jump over it.

In the second sample path 1 → 3 → 5 is available up to day five, inclusive. On day six the last tile is destroyed and the walk is thwarted.

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
You are given an array $$$a$$$ of $$$n$$$ integers. You must perform the following two operations on the array (the first, then the second):

1. Arbitrarily rearrange the elements of the array or leave the order of its elements unchanged.
2. Choose at most one contiguous segment of elements and replace the signs of all elements in this segment with their opposites. Formally, you can choose a pair of indices $$$l, r$$$ such that $$$1 \le l \le r \le n$$$ and assign $$$a_i = -a_i$$$ for all $$$l \le i \le r$$$ (negate elements). Note that you may choose not to select a pair of indices and leave all the signs of the elements unchanged.

What is the maximum sum of the array elements after performing these two operations (the first, then the second)?

## Input Format
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 50$$$) — the number of elements in array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-100 \le a_i \le 100$$$) — elements of the array.

## Output Format
For each test case, output the maximum sum of the array elements after sequentially performing the two given operations.

## Examples
```input
8
3
-2 3 -3
1
0
2
0 1
1
-99
4
10 -2 -3 7
5
-1 -2 -3 -4 -5
6
-41 22 -69 73 -15 -50
12
1 2 3 4 5 6 7 8 9 10 11 12
```
```output
8
0
1
99
22
15
270
78
```

## Note
In the first test case, you can first rearrange the array to get $$$[3,-2,-3]$$$ (operation 1), then choose $$$l = 2, r = 3$$$ and get the sum $$$3 + -((-2) + (-3)) = 8$$$ (operation 2).

In the second test case, you can do nothing in both operations and get the sum $$$0$$$.

In the third test case, you can do nothing in both operations and get the sum $$$0 + 1 = 1$$$.

In the fourth test case, you can first leave the order unchanged (operation 1), then choose $$$l = 1, r = 1$$$ and get the sum $$$-(-99) = 99$$$ (operation 2).

In the fifth test case, you can first leave the order unchanged (operation 1), then choose $$$l = 2, r = 3$$$ and get the sum $$$10 + -((-2) + (-3)) + 7 = 22$$$ (operation 2).

In the sixth test case, you can first leave the order unchanged (operation 1), then choose $$$l = 1, r = 5$$$ and get the sum $$$-((-1)+(-2)+(-3)+(-4)+(-5))=15$$$ (operation 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 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
You are given three positive integers $$$a$$$, $$$b$$$ and $$$l$$$ ($$$a,b,l>0$$$).

It can be shown that there always exists a way to choose non-negative (i.e. $$$\ge 0$$$) integers $$$k$$$, $$$x$$$, and $$$y$$$ such that $$$l = k \cdot a^x \cdot b^y$$$.

Your task is to find the number of distinct possible values of $$$k$$$ across all such ways.

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

The following $$$t$$$ lines contain three integers, $$$a$$$, $$$b$$$ and $$$l$$$ ($$$2 \le a, b \le 100$$$, $$$1 \le l \le 10^6$$$) — description of a test case.

## Output Format
Output $$$t$$$ lines, with the $$$i$$$-th ($$$1 \le i \le t$$$) line containing an integer, the answer to the $$$i$$$-th test case.

## Examples
```input
11
2 5 20
2 5 21
4 6 48
2 3 72
3 5 75
2 2 1024
3 7 83349
100 100 1000000
7 3 2
2 6 6
17 3 632043
```
```output
6
1
5
12
6
11
24
4
1
3
24
```

## Note
In the first test case, $$$a=2, b=5, l=20$$$. The possible values of $$$k$$$ (and corresponding $$$x,y$$$) are as follows:

- Choose $$$k = 1, x = 2, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 1 \cdot 2^2 \cdot 5^1 = 20 = l$$$.
- Choose $$$k = 2, x = 1, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 2 \cdot 2^1 \cdot 5^1 = 20 = l$$$.
- Choose $$$k = 4, x = 0, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 4 \cdot 2^0 \cdot 5^1 = 20 = l$$$.
- Choose $$$k = 5, x = 2, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 5 \cdot 2^2 \cdot 5^0 = 20 = l$$$.
- Choose $$$k = 10, x = 1, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 10 \cdot 2^1 \cdot 5^0 = 20 = l$$$.
- Choose $$$k = 20, x = 0, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 20 \cdot 2^0 \cdot 5^0 = 20 = l$$$.

In the second test case, $$$a=2, b=5, l=21$$$. Note that $$$l = 21$$$ is not divisible by either $$$a = 2$$$ or $$$b = 5$$$. Therefore, we can only set $$$x = 0, y = 0$$$, which corresponds to $$$k = 21$$$.

In the third test case, $$$a=4, b=6, l=48$$$. The possible values of $$$k$$$ (and corresponding $$$x,y$$$) are as follows:

- Choose $$$k = 2, x = 1, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 2 \cdot 4^1 \cdot 6^1 = 48 = l$$$.
- Choose $$$k = 3, x = 2, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 3 \cdot 4^2 \cdot 6^0 = 48 = l$$$.
- Choose $$$k = 8, x = 0, y = 1$$$. Then $$$k \cdot a^x \cdot b^y = 8 \cdot 4^0 \cdot 6^1 = 48 = l$$$.
- Choose $$$k = 12, x = 1, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 12 \cdot 4^1 \cdot 6^0 = 48 = l$$$.
- Choose $$$k = 48, x = 0, y = 0$$$. Then $$$k \cdot a^x \cdot b^y = 48 \cdot 4^0 \cdot 6^0 = 48 = l$$$.

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: 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 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
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 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: 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 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: 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.