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
The Dogeforces company has $$$k$$$ employees. Each employee, except for lower-level employees, has at least $$$2$$$ subordinates. Lower-level employees have no subordinates. Each employee, except for the head of the company, has exactly one direct supervisor. The head of the company is a direct or indirect supervisor of all employees. It is known that in Dogeforces, each supervisor receives a salary strictly more than all his subordinates.

The full structure of the company is a secret, but you know the number of lower-level employees and for each pair of lower-level employees, the salary of their common supervisor is known (if there are several such supervisors, then the supervisor with the minimum salary). You have to restore the structure of the company.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 500$$$) — the number of lower-level employees.

This is followed by $$$n$$$ lines, where $$$i$$$-th line contains $$$n$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,n}$$$ ($$$1 \le a_{i,j} \le 5000$$$) — salary of the common supervisor of employees with numbers $$$i$$$ and $$$j$$$. It is guaranteed that $$$a_{i,j} = a_{j,i}$$$. Note that $$$a_{i,i}$$$ is equal to the salary of the $$$i$$$-th employee.

## Output Format
In the first line, print a single integer $$$k$$$ — the number of employees in the company.

In the second line, print $$$k$$$ integers $$$c_1, c_2, \dots, c_k$$$, where $$$c_i$$$ is the salary of the employee with the number $$$i$$$.

In the third line, print a single integer $$$r$$$ — the number of the employee who is the head of the company.

In the following $$$k-1$$$ lines, print two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le k$$$) — the number of the employee and his direct supervisor.

Note that the lower-level employees have numbers from $$$1$$$ to $$$n$$$, and for the rest of the employees, you have to assign numbers from $$$n+1$$$ to $$$k$$$. If there are several correct company structures, you can print any of them.

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

## Note
One of the possible structures 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
You are given a directed graph consisting of $$$n$$$ vertices. Each directed edge (or arc) labeled with a single character. Initially, the graph is empty.

You should process $$$m$$$ queries with it. Each query is one of three types:

- "$$$+$$$ $$$u$$$ $$$v$$$ $$$c$$$" — add arc from $$$u$$$ to $$$v$$$ with label $$$c$$$. It's guaranteed that there is no arc $$$(u, v)$$$ in the graph at this moment;
- "$$$-$$$ $$$u$$$ $$$v$$$" — erase arc from $$$u$$$ to $$$v$$$. It's guaranteed that the graph contains arc $$$(u, v)$$$ at this moment;
- "$$$?$$$ $$$k$$$" — find the sequence of $$$k$$$ vertices $$$v_1, v_2, \dots, v_k$$$ such that there exist both routes $$$v_1 \to v_2 \to \dots \to v_k$$$ and $$$v_k \to v_{k - 1} \to \dots \to v_1$$$ and if you write down characters along both routes you'll get the same string. You can visit the same vertices any number of times.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$) — the number of vertices in the graph and the number of queries.

The next $$$m$$$ lines contain queries — one per line. Each query is one of three types:

- "$$$+$$$ $$$u$$$ $$$v$$$ $$$c$$$" ($$$1 \le u, v \le n$$$; $$$u \neq v$$$; $$$c$$$ is a lowercase Latin letter);
- "$$$-$$$ $$$u$$$ $$$v$$$" ($$$1 \le u, v \le n$$$; $$$u \neq v$$$);
- "$$$?$$$ $$$k$$$" ($$$2 \le k \le 10^5$$$).

It's guaranteed that you don't add multiple edges and erase only existing edges. Also, there is at least one query of the third type.

## Output Format
For each query of the third type, print YES if there exist the sequence $$$v_1, v_2, \dots, v_k$$$ described above, or NO otherwise.

## Examples
```input
3 11
+ 1 2 a
+ 2 3 b
+ 3 2 a
+ 2 1 b
? 3
? 2
- 2 1
- 3 2
+ 2 1 c
+ 3 2 d
? 5
```
```output
YES
NO
YES
```

## Note
In the first query of the third type $$$k = 3$$$, we can, for example, choose a sequence $$$[1, 2, 3]$$$, since $$$1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3$$$ and $$$3 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 1$$$.

In the second query of the third type $$$k = 2$$$, and we can't find sequence $$$p_1, p_2$$$ such that arcs $$$(p_1, p_2)$$$ and $$$(p_2, p_1)$$$ have the same characters.

In the third query of the third type, we can, for example, choose a sequence $$$[1, 2, 3, 2, 1]$$$, where $$$1 \xrightarrow{\text{a}} 2 \xrightarrow{\text{b}} 3 \xrightarrow{\text{d}} 2 \xrightarrow{\text{c}} 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: 8.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an undirected connected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. Your goal is to destroy all edges of the given graph.

You may choose any vertex as the starting one and begin walking from it along the edges. When you walk along an edge, you destroy it. Obviously, you cannot walk along an edge if it is destroyed.

You can perform the mode shift operation at most once during your walk, and this operation can only be performed when you are at some vertex (you cannot perform it while traversing an edge). After the mode shift, the edges you go through are deleted in the following way: the first edge after the mode shift is not destroyed, the second one is destroyed, the third one is not destroyed, the fourth one is destroyed, and so on. You cannot switch back to the original mode, and you don't have to perform this operation if you don't want to.

Can you destroy all the edges of the given graph?

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 3000$$$; $$$n - 1 \le m \le \min(\frac{n(n-1)}{2}, 3000$$$)) — the numbef of vertices and the number of edges in the graph.

Then $$$m$$$ lines follow, each containing two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — the endpoints of the $$$i$$$-th edge.

These edges form a connected undirected graph without multiple edges.

## Output Format
If it's impossible to destroy all of the edges, print 0.

Otherwise, print the sequence of your actions as follows. First, print $$$k$$$ — the number of actions ($$$k \le 2m + 2$$$). Then, print the sequence itself, consisting of $$$k$$$ integers. The first integer should be the index of the starting vertex. Then, each of the next integers should be either the index of the next vertex in your traversal, or $$$-1$$$ if you use mode shift. You are allowed to use mode shift at most once.

If there are multiple answers, print any of them.

## Examples
```input
3 3
1 2
2 3
3 1
```
```output
4
1 2 3 1
```
-----
```input
4 3
1 2
2 3
4 2
```
```output
8
2 -1 1 2 3 2 4 2
```
-----
```input
5 5
1 2
2 3
3 1
2 4
2 5
```
```output
9
2 3 1 2 -1 4 2 5 2
```
-----
```input
5 5
1 2
2 3
3 1
2 4
4 5
```
```output
8
5 4 2 3 1 -1 2 1
```
-----
```input
6 5
1 2
2 3
3 4
4 5
3 6
```
```output
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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A palindrome is a string that reads the same backward as forward. For example, the strings "z", "aaa", "aba", and "abccba" are palindromes, but "codeforces" and "ab" are not. You hate palindromes because they give you déjà vu.

There is a string $$$s$$$. You must insert exactly one character 'a' somewhere in $$$s$$$. If it is possible to create a string that is not a palindrome, you should find one example. Otherwise, you should report that it is impossible.

For example, suppose $$$s=$$$ "cbabc". By inserting an 'a', you can create "acbabc", "cababc", "cbaabc", "cbabac", or "cbabca". However "cbaabc" is a palindrome, so you must output one of the other options.

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

The only line of each test case contains a string $$$s$$$ consisting of lowercase English letters.

The total length of all strings does not exceed $$$3\cdot 10^5$$$.

## Output Format
For each test case, if there is no solution, output "NO".

Otherwise, output "YES" followed by your constructed string of length $$$|s|+1$$$ on the next line. If there are multiple solutions, you may print any.

You can print each letter of "YES" and "NO" in any case (upper or lower).

## Examples
```input
6
cbabc
ab
zza
ba
a
nutforajaroftuna
```
```output
YES
cbabac
YES
aab
YES
zaza
YES
baa
NO
YES
nutforajarofatuna
```

## Note
The first test case is described in the statement.

In the second test case, we can make either "aab" or "aba". But "aba" is a palindrome, so "aab" is the only correct answer.

In the third test case, "zaza" and "zzaa" are correct answers, but not "azza".

In the fourth test case, "baa" is the only correct answer.

In the fifth test case, we can only make "aa", which is a palindrome. So the answer is "NO".

In the sixth test case, "anutforajaroftuna" is a palindrome, but inserting 'a' elsewhere is valid.

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
You have $$$r$$$ red and $$$b$$$ blue beans. You'd like to distribute them among several (maybe, one) packets in such a way that each packet:

- has at least one red bean (or the number of red beans $$$r_i \ge 1$$$);
- has at least one blue bean (or the number of blue beans $$$b_i \ge 1$$$);
- the number of red and blue beans should differ in no more than $$$d$$$ (or $$$|r_i - b_i| \le d$$$)

Can you distribute all beans?

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

The first and only line of each test case contains three integers $$$r$$$, $$$b$$$, and $$$d$$$ ($$$1 \le r, b \le 10^9$$$; $$$0 \le d \le 10^9$$$) — the number of red and blue beans and the maximum absolute difference in each packet.

## Output Format
For each test case, if you can distribute all beans, print YES. Otherwise, print NO.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).

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

## Note
In the first test case, you can form one packet with $$$1$$$ red and $$$1$$$ blue bean. The absolute difference $$$|1 - 1| = 0 \le d$$$.

In the second test case, you can form two packets: $$$1$$$ red and $$$4$$$ blue beans in the first packet and $$$1$$$ red and $$$3$$$ blue beans in the second one.

In the third test case, since $$$b = 1$$$, you can form only one packet with $$$6$$$ red and $$$1$$$ blue beans. The absolute difference $$$|6 - 1| = 5 > d$$$.

In the fourth test case, since $$$d = 0$$$ so each packet should contain the same number of red and blue beans, but $$$r \neq b$$$.

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 $$$n \times m$$$ grid. You are standing at cell $$$(1, 1)$$$ and your goal is to finish at cell $$$(n, m)$$$.

You can move to the neighboring cells to the right or down. In other words, suppose you are standing at cell $$$(x, y)$$$. You can:

- move right to the cell $$$(x, y + 1)$$$ — it costs $$$x$$$ burles;
- move down to the cell $$$(x + 1, y)$$$ — it costs $$$y$$$ burles.

Can you reach cell $$$(n, m)$$$ spending exactly $$$k$$$ burles?

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

The first and only line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 100$$$; $$$0 \le k \le 10^4$$$) — the sizes of grid and the exact amount of money you need to spend.

## Output Format
For each test case, if you can reach cell $$$(n, m)$$$ spending exactly $$$k$$$ burles, print YES. Otherwise, print NO.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES are all recognized as positive answer).

## Examples
```input
6
1 1 0
2 2 2
2 2 3
2 2 4
1 4 3
100 100 10000
```
```output
YES
NO
YES
NO
YES
NO
```

## Note
In the first test case, you are already in the final cell, so you spend $$$0$$$ burles.

In the second, third and fourth test cases, there are two paths from $$$(1, 1)$$$ to $$$(2, 2)$$$: $$$(1, 1)$$$ $$$\rightarrow$$$ $$$(1, 2)$$$ $$$\rightarrow$$$ $$$(2, 2)$$$ or $$$(1, 1)$$$ $$$\rightarrow$$$ $$$(2, 1)$$$ $$$\rightarrow$$$ $$$(2, 2)$$$. Both costs $$$1 + 2 = 3$$$ burles, so it's the only amount of money you can spend.

In the fifth test case, there is the only way from $$$(1, 1)$$$ to $$$(1, 4)$$$ and it costs $$$1 + 1 + 1 = 3$$$ 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 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 two integer arrays $$$a$$$ and $$$b$$$ of length $$$n$$$.

You can reverse at most one subarray (continuous subsegment) of the array $$$a$$$.

Your task is to reverse such a subarray that the sum $$$\sum\limits_{i=1}^n a_i \cdot b_i$$$ is maximized.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^7$$$).

## Output Format
Print single integer — maximum possible sum after reversing at most one subarray (continuous subsegment) of $$$a$$$.

## Examples
```input
5
2 3 2 1 3
1 3 2 4 2
```
```output
29
```
-----
```input
2
13 37
2 4
```
```output
174
```
-----
```input
6
1 8 7 6 3 6
5 9 6 8 8 6
```
```output
235
```

## Note
In the first example, you can reverse the subarray $$$[4, 5]$$$. Then $$$a = [2, 3, 2, 3, 1]$$$ and $$$2 \cdot 1 + 3 \cdot 3 + 2 \cdot 2 + 3 \cdot 4 + 1 \cdot 2 = 29$$$.

In the second example, you don't need to use the reverse operation. $$$13 \cdot 2 + 37 \cdot 4 = 174$$$.

In the third example, you can reverse the subarray $$$[3, 5]$$$. Then $$$a = [1, 8, 3, 6, 7, 6]$$$ and $$$1 \cdot 5 + 8 \cdot 9 + 3 \cdot 6 + 6 \cdot 8 + 7 \cdot 8 + 6 \cdot 6 = 235$$$.

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
One day little Vasya found mom's pocket book. The book had n names of her friends and unusually enough, each name was exactly m letters long. Let's number the names from 1 to n in the order in which they are written.

As mom wasn't home, Vasya decided to play with names: he chose three integers i, j, k (1 ≤ i < j ≤ n, 1 ≤ k ≤ m), then he took names number i and j and swapped their prefixes of length k. For example, if we take names "CBDAD" and "AABRD" and swap their prefixes with the length of 3, the result will be names "AABAD" and "CBDRD".

You wonder how many different names Vasya can write instead of name number 1, if Vasya is allowed to perform any number of the described actions. As Vasya performs each action, he chooses numbers i, j, k independently from the previous moves and his choice is based entirely on his will. The sought number can be very large, so you should only find it modulo 1000000007 (109 + 7).

## Input Format
The first input line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of names and the length of each name, correspondingly. Then n lines contain names, each name consists of exactly m uppercase Latin letters.

## Output Format
Print the single number — the number of different names that could end up in position number 1 in the pocket book after the applying the procedures described above. Print the number modulo 1000000007 (109 + 7).

## Examples
```input
2 3
AAB
BAA
```
```output
4
```
-----
```input
4 5
ABABA
BCGDG
AAAAA
YABSA
```
```output
216
```

## Note
In the first sample Vasya can get the following names in the position number 1: "AAB", "AAA", "BAA" and "BAB".

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
One day Vasya got hold of a sheet of checkered paper n × m squares in size. Our Vasya adores geometrical figures, so he painted two rectangles on the paper. The rectangles' sides are parallel to the coordinates' axes, also the length of each side of each rectangle is no less than 3 squares and the sides are painted by the grid lines. The sides can also be part of the sheet of paper's edge. Then Vasya hatched all squares on the rectangles' frames.

Let's define a rectangle's frame as the set of squares inside the rectangle that share at least one side with its border.

A little later Vasya found a sheet of paper of exactly the same size and couldn't guess whether it is the same sheet of paper or a different one. So, he asked you to check whether the sheet of paper he had found contains two painted frames and nothing besides them.

Please note that the frames painted by Vasya can arbitrarily intersect, overlap or even completely coincide.

The coordinates on the sheet of paper are introduced in such a way that the X axis goes from top to bottom, the x coordinates of the squares' numbers take values from 1 to n and the Y axis goes from the left to the right and the y coordinates of the squares' numbers take values from 1 to m.

## Input Format
The first input line contains two integers n and m (3 ≤ n, m ≤ 1000) — the sizes of the sheet of paper Vasya found. Next n lines, each consisting of m symbols "." (dot) and "#" (number sign), describe the found sheet of paper. The symbol "#" represents a hatched square and the symbol "." represents a non-hatched square.

## Output Format
In the first line print the single word "YES" or "NO", meaning whether it is true that the found sheet of paper has two frames painted on it. If the answer is positive, then print in the second line 4 integers: the coordinates of the upper left and lower right corners of the first frame. In the third line print 4 integers: the coordinates of the upper left and the lower right corners of the second frame. If there are multiple answers, print any of them.

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

## Note
In the first sample there are two frames on the picture. The first one is:

The second one is:

In the second sample the painted figures are not frames. Note that the height and width of valid frames is no less than 3.

Now solve the problem and return the code.