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
You have $$$n \times n$$$ square grid and an integer $$$k$$$. Put an integer in each cell while satisfying the conditions below.

- All numbers in the grid should be between $$$1$$$ and $$$k$$$ inclusive.
- Minimum number of the $$$i$$$-th row is $$$1$$$ ($$$1 \le i \le n$$$).
- Minimum number of the $$$j$$$-th column is $$$1$$$ ($$$1 \le j \le n$$$).

Find the number of ways to put integers in the grid. Since the answer can be very large, find the answer modulo $$$(10^{9} + 7)$$$.

These are the examples of valid and invalid grid when $$$n=k=2$$$.

## Input Format
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 250$$$, $$$1 \le k \le 10^{9}$$$).

## Output Format
Print the answer modulo $$$(10^{9} + 7)$$$.

## Examples
```input
2 2
```
```output
7
```
-----
```input
123 456789
```
```output
689974806
```

## Note
In the first example, following $$$7$$$ cases are possible.

In the second example, make sure you print the answer modulo $$$(10^{9} + 7)$$$.

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 an integer $$$n$$$. Let's define following tree generation as McDic's generation:

1. Make a complete and full binary tree of $$$2^{n} - 1$$$ vertices. Complete and full binary tree means a tree that exactly one vertex is a root, all leaves have the same depth (distance from the root), and all non-leaf nodes have exactly two child nodes.
2. Select a non-root vertex $$$v$$$ from that binary tree.
3. Remove $$$v$$$ from tree and make new edges between $$$v$$$'s parent and $$$v$$$'s direct children. If $$$v$$$ has no children, then no new edges will be made.

You have a tree. Determine if this tree can be made by McDic's generation. If yes, then find the parent vertex of removed vertex in tree.

## Input Format
The first line contains integer $$$n$$$ ($$$2 \le n \le 17$$$).

The $$$i$$$-th of the next $$$2^{n} - 3$$$ lines contains two integers $$$a_{i}$$$ and $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le 2^{n} - 2$$$) — meaning there is an edge between $$$a_{i}$$$ and $$$b_{i}$$$. It is guaranteed that the given edges form a tree.

## Output Format
Print two lines.

In the first line, print a single integer — the number of answers. If given tree cannot be made by McDic's generation, then print $$$0$$$.

In the second line, print all possible answers in ascending order, separated by spaces. If the given tree cannot be made by McDic's generation, then don't print anything.

## Examples
```input
4
1 2
1 3
2 4
2 5
3 6
3 13
3 14
4 7
4 8
5 9
5 10
6 11
6 12
```
```output
1
3
```
-----
```input
2
1 2
```
```output
2
1 2
```
-----
```input
3
1 2
2 3
3 4
4 5
5 6
```
```output
0
```

## Note
In the first example, $$$3$$$ is the only possible answer.

In the second example, there are $$$2$$$ possible answers.

In the third example, the tree can't be generated by McDic's generation.

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 string $$$s$$$ consisting of lowercase Latin letters and $$$q$$$ queries for this string.

Recall that the substring $$$s[l; r]$$$ of the string $$$s$$$ is the string $$$s_l s_{l + 1} \dots s_r$$$. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

There are two types of queries:

- $$$1~ pos~ c$$$ ($$$1 \le pos \le |s|$$$, $$$c$$$ is lowercase Latin letter): replace $$$s_{pos}$$$ with $$$c$$$ (set $$$s_{pos} := c$$$);
- $$$2~ l~ r$$$ ($$$1 \le l \le r \le |s|$$$): calculate the number of distinct characters in the substring $$$s[l; r]$$$.

## Input Format
The first line of the input contains one string $$$s$$$ consisting of no more than $$$10^5$$$ lowercase Latin letters.

The second line of the input contains one integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

The next $$$q$$$ lines contain queries, one per line. Each query is given in the format described in the problem statement. It is guaranteed that there is at least one query of the second type.

## Output Format
For each query of the second type print the answer for it — the number of distinct characters in the required substring in this query.

## Examples
```input
abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7
```
```output
3
1
2
```
-----
```input
dfcbbcfeeedbaea
15
1 6 e
1 4 b
2 6 14
1 7 b
1 12 c
2 6 8
2 1 6
1 7 c
1 2 f
1 10 a
2 7 9
1 10 a
1 14 b
1 1 f
2 1 11
```
```output
5
2
5
2
6
```

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 string $$$s$$$ consisting only of first $$$20$$$ lowercase Latin letters ('a', 'b', ..., 't').

Recall that the substring $$$s[l; r]$$$ of the string $$$s$$$ is the string $$$s_l s_{l + 1} \dots s_r$$$. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

You can perform the following operation no more than once: choose some substring $$$s[l; r]$$$ and reverse it (i.e. the string $$$s_l s_{l + 1} \dots s_r$$$ becomes $$$s_r s_{r - 1} \dots s_l$$$).

Your goal is to maximize the length of the maximum substring of $$$s$$$ consisting of distinct (i.e. unique) characters.

The string consists of distinct characters if no character in this string appears more than once. For example, strings "abcde", "arctg" and "minecraft" consist of distinct characters but strings "codeforces", "abacaba" do not consist of distinct characters.

## Input Format
The only line of the input contains one string $$$s$$$ consisting of no more than $$$10^6$$$ characters 'a', 'b', ..., 't' (first $$$20$$$ lowercase Latin letters).

## Output Format
Print one integer — the maximum possible length of the maximum substring of $$$s$$$ consisting of distinct characters after reversing no more than one its substring.

## Examples
```input
abacaba
```
```output
3
```
-----
```input
abcdecdf
```
```output
6
```
-----
```input
aabbcc
```
```output
3
```
-----
```input
abcdeefc
```
```output
6
```

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 $$$a$$$ coins of value $$$n$$$ and $$$b$$$ coins of value $$$1$$$. You always pay in exact change, so you want to know if there exist such $$$x$$$ and $$$y$$$ that if you take $$$x$$$ ($$$0 \le x \le a$$$) coins of value $$$n$$$ and $$$y$$$ ($$$0 \le y \le b$$$) coins of value $$$1$$$, then the total value of taken coins will be $$$S$$$.

You have to answer $$$q$$$ independent test cases.

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

The only line of the test case contains four integers $$$a$$$, $$$b$$$, $$$n$$$ and $$$S$$$ ($$$1 \le a, b, n, S \le 10^9$$$) — the number of coins of value $$$n$$$, the number of coins of value $$$1$$$, the value $$$n$$$ and the required total value.

## Output Format
For the $$$i$$$-th test case print the answer on it — YES (without quotes) if there exist such $$$x$$$ and $$$y$$$ that if you take $$$x$$$ coins of value $$$n$$$ and $$$y$$$ coins of value $$$1$$$, then the total value of taken coins will be $$$S$$$, and NO otherwise.

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

## Examples
```input
4
1 2 3 4
1 2 3 6
5 2 6 27
3 3 5 18
```
```output
YES
NO
NO
YES
```

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 are given two strings $$$s$$$ and $$$t$$$ both of length $$$n$$$ and both consisting of lowercase Latin letters.

In one move, you can choose any length $$$len$$$ from $$$1$$$ to $$$n$$$ and perform the following operation:

- Choose any contiguous substring of the string $$$s$$$ of length $$$len$$$ and reverse it;
- at the same time choose any contiguous substring of the string $$$t$$$ of length $$$len$$$ and reverse it as well.

Note that during one move you reverse exactly one substring of the string $$$s$$$ and exactly one substring of the string $$$t$$$.

Also note that borders of substrings you reverse in $$$s$$$ and in $$$t$$$ can be different, the only restriction is that you reverse the substrings of equal length. For example, if $$$len=3$$$ and $$$n=5$$$, you can reverse $$$s[1 \dots 3]$$$ and $$$t[3 \dots 5]$$$, $$$s[2 \dots 4]$$$ and $$$t[2 \dots 4]$$$, but not $$$s[1 \dots 3]$$$ and $$$t[1 \dots 2]$$$.

Your task is to say if it is possible to make strings $$$s$$$ and $$$t$$$ equal after some (possibly, empty) sequence of moves.

You have to answer $$$q$$$ independent test cases.

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

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$s$$$ and $$$t$$$.

The second line of the test case contains one string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.

The third line of the test case contains one string $$$t$$$ consisting of $$$n$$$ lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

## Output Format
For each test case, print the answer on it — "YES" (without quotes) if it is possible to make strings $$$s$$$ and $$$t$$$ equal after some (possibly, empty) sequence of moves and "NO" otherwise.

## Examples
```input
4
4
abcd
abdc
5
ababa
baaba
4
asdf
asdg
4
abcd
badc
```
```output
NO
YES
NO
YES
```

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 three piles of candies: red, green and blue candies:

- the first pile contains only red candies and there are $$$r$$$ candies in it,
- the second pile contains only green candies and there are $$$g$$$ candies in it,
- the third pile contains only blue candies and there are $$$b$$$ candies in it.

Each day Tanya eats exactly two candies of different colors. She is free to choose the colors of eaten candies: the only restriction that she can't eat two candies of the same color in a day.

Find the maximal number of days Tanya can eat candies? Each day she needs to eat exactly two candies.

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

Each test case is given as a separate line of the input. It contains three integers $$$r$$$, $$$g$$$ and $$$b$$$ ($$$1 \le r, g, b \le 10^8$$$) — the number of red, green and blue candies, respectively.

## Output Format
Print $$$t$$$ integers: the $$$i$$$-th printed integer is the answer on the $$$i$$$-th test case in the input.

## Examples
```input
6
1 1 1
1 2 1
4 1 1
7 4 10
8 1 4
8 2 8
```
```output
1
2
2
10
5
9
```

## Note
In the first example, Tanya can eat candies for one day only. She can eat any pair of candies this day because all of them have different colors.

In the second example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and green and blue candies on the second day.

In the third example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and red and blue candies on the second day. Note, that two red candies will remain uneaten.

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 PIN code is a string that consists of exactly $$$4$$$ digits. Examples of possible PIN codes: 7013, 0000 and 0990. Please note that the PIN code can begin with any digit, even with 0.

Polycarp has $$$n$$$ ($$$2 \le n \le 10$$$) bank cards, the PIN code of the $$$i$$$-th card is $$$p_i$$$.

Polycarp has recently read a recommendation that it is better to set different PIN codes on different cards. Thus he wants to change the minimal number of digits in the PIN codes of his cards so that all $$$n$$$ codes would become different.

Formally, in one step, Polycarp picks $$$i$$$-th card ($$$1 \le i \le n$$$), then in its PIN code $$$p_i$$$ selects one position (from $$$1$$$ to $$$4$$$), and changes the digit in this position to any other. He needs to change the minimum number of digits so that all PIN codes become different.

Polycarp quickly solved this problem. Can you solve it?

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

The first line of each of $$$t$$$ test sets contains a single integer $$$n$$$ ($$$2 \le n \le 10$$$) — the number of Polycarp's bank cards. The next $$$n$$$ lines contain the PIN codes $$$p_1, p_2, \dots, p_n$$$ — one per line. The length of each of them is $$$4$$$. All PIN codes consist of digits only.

## Output Format
Print the answers to $$$t$$$ test sets. The answer to each set should consist of a $$$n + 1$$$ lines

In the first line print $$$k$$$ — the least number of changes to make all PIN codes different. In the next $$$n$$$ lines output the changed PIN codes in the order corresponding to their appearance in the input. If there are several optimal answers, print any of them.

## Examples
```input
3
2
1234
0600
2
1337
1337
4
3139
3139
3139
3139
```
```output
0
1234
0600
1
1337
1237
3
3139
3138
3939
6139
```

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
On the well-known testing system MathForces, a draw of $$$n$$$ rating units is arranged. The rating will be distributed according to the following algorithm: if $$$k$$$ participants take part in this event, then the $$$n$$$ rating is evenly distributed between them and rounded to the nearest lower integer, At the end of the drawing, an unused rating may remain — it is not given to any of the participants.

For example, if $$$n = 5$$$ and $$$k = 3$$$, then each participant will recieve an $$$1$$$ rating unit, and also $$$2$$$ rating units will remain unused. If $$$n = 5$$$, and $$$k = 6$$$, then none of the participants will increase their rating.

Vasya participates in this rating draw but does not have information on the total number of participants in this event. Therefore, he wants to know what different values of the rating increment are possible to get as a result of this draw and asks you for help.

For example, if $$$n=5$$$, then the answer is equal to the sequence $$$0, 1, 2, 5$$$. Each of the sequence values (and only them) can be obtained as $$$\lfloor n/k \rfloor$$$ for some positive integer $$$k$$$ (where $$$\lfloor x \rfloor$$$ is the value of $$$x$$$ rounded down): $$$0 = \lfloor 5/7 \rfloor$$$, $$$1 = \lfloor 5/5 \rfloor$$$, $$$2 = \lfloor 5/2 \rfloor$$$, $$$5 = \lfloor 5/1 \rfloor$$$.

Write a program that, for a given $$$n$$$, finds a sequence of all possible rating increments.

## Input Format
The first line contains integer number $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each line contains an integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the total number of the rating units being drawn.

## Output Format
Output the answers for each of $$$t$$$ test cases. Each answer should be contained in two lines.

In the first line print a single integer $$$m$$$ — the number of different rating increment values that Vasya can get.

In the following line print $$$m$$$ integers in ascending order — the values of possible rating increments.

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

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
Balph is learning to play a game called Buma. In this game, he is given a row of colored balls. He has to choose the color of one new ball and the place to insert it (between two balls, or to the left of all the balls, or to the right of all the balls).

When the ball is inserted the following happens repeatedly: if some segment of balls of the same color became longer as a result of a previous action and its length became at least $$$3$$$, then all the balls of this segment are eliminated.

Consider, for example, a row of balls 'AAABBBWWBB'. Suppose Balph chooses a ball of color 'W' and the place to insert it after the sixth ball, i. e. to the left of the two 'W's. After Balph inserts this ball, the balls of color 'W' are eliminated, since this segment was made longer and has length $$$3$$$ now, so the row becomes 'AAABBBBB'. The balls of color 'B' are eliminated now, because the segment of balls of color 'B' became longer and has length $$$5$$$ now. Thus, the row becomes 'AAA'. However, none of the balls are eliminated now, because there is no elongated segment.

Help Balph count the number of possible ways to choose a color of a new ball and a place to insert it that leads to the elimination of all the balls.

## Input Format
The only line contains a non-empty string of uppercase English letters of length at most $$$3 \cdot 10^5$$$. Each letter represents a ball with the corresponding color.

## Output Format
Output the number of ways to choose a color and a position of a new ball in order to eliminate all the balls.

## Examples
```input
BBWWBB
```
```output
3
```
-----
```input
BWWB
```
```output
0
```
-----
```input
BBWBB
```
```output
0
```
-----
```input
OOOWWW
```
```output
0
```
-----
```input
WWWOOOOOOWWW
```
```output
7
```

Now solve the problem and return the code.