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 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
The string $$$t_1t_2 \dots t_k$$$ is good if each letter of this string belongs to at least one palindrome of length greater than 1.

A palindrome is a string that reads the same backward as forward. For example, the strings A, BAB, ABBA, BAABBBAAB are palindromes, but the strings AB, ABBBAA, BBBA are not.

Here are some examples of good strings:

- $$$t$$$ = AABBB (letters $$$t_1$$$, $$$t_2$$$ belong to palindrome $$$t_1 \dots t_2$$$ and letters $$$t_3$$$, $$$t_4$$$, $$$t_5$$$ belong to palindrome $$$t_3 \dots t_5$$$);
- $$$t$$$ = ABAA (letters $$$t_1$$$, $$$t_2$$$, $$$t_3$$$ belong to palindrome $$$t_1 \dots t_3$$$ and letter $$$t_4$$$ belongs to palindrome $$$t_3 \dots t_4$$$);
- $$$t$$$ = AAAAA (all letters belong to palindrome $$$t_1 \dots t_5$$$);

You are given a string $$$s$$$ of length $$$n$$$, consisting of only letters A and B.

You have to calculate the number of good substrings of string $$$s$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the string $$$s$$$.

The second line contains the string $$$s$$$, consisting of letters A and B.

## Output Format
Print one integer — the number of good substrings of string $$$s$$$.

## Examples
```input
5
AABBB
```
```output
6
```
-----
```input
3
AAA
```
```output
3
```
-----
```input
7
AAABABB
```
```output
15
```

## Note
In the first test case there are six good substrings: $$$s_1 \dots s_2$$$, $$$s_1 \dots s_4$$$, $$$s_1 \dots s_5$$$, $$$s_3 \dots s_4$$$, $$$s_3 \dots s_5$$$ and $$$s_4 \dots s_5$$$.

In the second test case there are three good substrings: $$$s_1 \dots s_2$$$, $$$s_1 \dots s_3$$$ and $$$s_2 \dots s_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 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
You have a password which you often type — a string $$$s$$$ of length $$$n$$$. Every character of this string is one of the first $$$m$$$ lowercase Latin letters.

Since you spend a lot of time typing it, you want to buy a new keyboard.

A keyboard is a permutation of the first $$$m$$$ Latin letters. For example, if $$$m = 3$$$, then there are six possible keyboards: abc, acb, bac, bca, cab and cba.

Since you type your password with one finger, you need to spend time moving your finger from one password character to the next. The time to move from character $$$s_i$$$ to character $$$s_{i+1}$$$ is equal to the distance between these characters on keyboard. The total time you have to spend typing the password with a keyboard is called the slowness of this keyboard.

More formaly, the slowness of keyboard is equal to $$$\sum\limits_{i=2}^{n} |pos_{s_{i-1}} - pos_{s_i} |$$$, where $$$pos_x$$$ is position of letter $$$x$$$ in keyboard.

For example, if $$$s$$$ is aacabc and the keyboard is bac, then the total time of typing this password is $$$|pos_a - pos_a| + |pos_a - pos_c| + |pos_c - pos_a| + |pos_a - pos_b| + |pos_b - pos_c|$$$ = $$$|2 - 2| + |2 - 3| + |3 - 2| + |2 - 1| + |1 - 3|$$$ = $$$0 + 1 + 1 + 1 + 2 = 5$$$.

Before buying a new keyboard you want to know the minimum possible slowness that the keyboard can have.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5, 1 \le m \le 20$$$).

The second line contains the string $$$s$$$ consisting of $$$n$$$ characters. Each character is one of the first $$$m$$$ Latin letters (lowercase).

## Output Format
Print one integer – the minimum slowness a keyboard can have.

## Examples
```input
6 3
aacabc
```
```output
5
```
-----
```input
6 4
aaaaaa
```
```output
0
```
-----
```input
15 4
abacabadabacaba
```
```output
16
```

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

In the second test case the slowness of any keyboard is $$$0$$$.

In the third test case one of the most suitable keyboards is bacd.

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
Ujan needs some rest from cleaning, so he started playing with infinite sequences. He has two integers $$$n$$$ and $$$k$$$. He creates an infinite sequence $$$s$$$ by repeating the following steps.

1. Find $$$k$$$ smallest distinct positive integers that are not in $$$s$$$. Let's call them $$$u_{1}, u_{2}, \ldots, u_{k}$$$ from the smallest to the largest.
2. Append $$$u_{1}, u_{2}, \ldots, u_{k}$$$ and $$$\sum_{i=1}^{k} u_{i}$$$ to $$$s$$$ in this order.
3. Go back to the first step.

Ujan will stop procrastinating when he writes the number $$$n$$$ in the sequence $$$s$$$. Help him find the index of $$$n$$$ in $$$s$$$. In other words, find the integer $$$x$$$ such that $$$s_{x} = n$$$. It's possible to prove that all positive integers are included in $$$s$$$ only once.

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

Each of the following $$$t$$$ lines contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$2 \le k \le 10^{6}$$$), the number to be found in the sequence $$$s$$$ and the parameter used to create the sequence $$$s$$$.

## Output Format
In each of the $$$t$$$ lines, output the answer for the corresponding test case.

## Examples
```input
2
10 2
40 5
```
```output
11
12
```

## Note
In the first sample, $$$s = (1, 2, 3, 4, 5, 9, 6, 7, 13, 8, 10, 18, \ldots)$$$. $$$10$$$ is the $$$11$$$-th number here, so the answer is $$$11$$$.

In the second sample, $$$s = (1, 2, 3, 4, 5, 15, 6, 7, 8, 9, 10, 40, \ldots)$$$.

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
Ujan has finally cleaned up his house and now wants to decorate the interior. He decided to place a beautiful carpet that would really tie the guest room together.

He is interested in carpets that are made up of polygonal patches such that each side of a patch is either a side of another (different) patch, or is an exterior side of the whole carpet. In other words, the carpet can be represented as a planar graph, where each patch corresponds to a face of the graph, each face is a simple polygon. The perimeter of the carpet is the number of the exterior sides.

Ujan considers a carpet beautiful if it consists of $$$f$$$ patches, where the $$$i$$$-th patch has exactly $$$a_i$$$ sides, and the perimeter is the smallest possible. Find an example of such a carpet, so that Ujan can order it!

## Input Format
The first line of input contains a single integer $$$f$$$ ($$$1 \leq f \leq 10^5$$$), the number of patches in the carpet.

The next line contains $$$f$$$ integers $$$a_1, \ldots, a_f$$$ ($$$3 \leq a_i \leq 3\cdot 10^5$$$), the number of sides of the patches. The total number of the sides of the patches $$$a_1 + \ldots + a_f$$$ does not exceed $$$3\cdot10^5$$$.

## Output Format
Output the description of the carpet as a graph.

First, output a single integer $$$n$$$ ($$$3 \leq n \leq 3 \cdot 10^5$$$), the total number of vertices in your graph (the vertices must be numbered from $$$1$$$ to $$$n$$$).

Then output $$$f$$$ lines containing the description of the faces. The $$$i$$$-th line should describe the $$$i$$$-th face and contain $$$a_i$$$ distinct integers $$$v_{i,1}, \ldots, v_{i,a_i}$$$ ($$$1 \leq v_{i,j} \leq n$$$), which means that the vertices $$$v_{i,j}$$$ and $$$v_{i,(j \bmod{a_i})+1}$$$ are connected by an edge for any $$$1 \leq j \leq a_i$$$.

The graph should be planar and satisfy the restrictions described in the problem statement. Its perimeter should be the smallest possible. There should be no double edges or self-loops in the graph. The graph should be connected. Note that a solution always exists; if there are multiple solutions, output any of them.

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

## Note
In the first sample, the two triangular faces are connected by a single edge, which results in the minimum perimeter $$$4$$$.

The figure shows one possible configuration for the second sample. The minimum perimeter in this case is $$$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 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
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 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
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 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: 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.
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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Esports is a form of competitive sports using video games. Dota 2 is one of the most popular competitive video games in Esports. Recently, a new video game Dota 3 was released. In Dota 3 a player can buy some relics for their hero. Relics are counters that track hero's actions and statistics in a game.

Gloria likes to play Dota 3, so she wants to buy all $$$n$$$ available relics for her favorite hero.

Relics can be bought using an in-game currency called shards. Each relic has its own price — $$$c_i$$$ shards for the $$$i$$$-th relic. A player can buy a relic using one of the following options:

- Pay $$$c_i$$$ shards to buy the $$$i$$$-th relic;
- Pay $$$x$$$ shards and randomly get one of all $$$n$$$ relics. The probability of getting a relic is the same for all $$$n$$$ relics. If a duplicate relic is received, then the relic is recycled and $$$\frac{x}{2}$$$ shards are given back to the player.

Gloria wants to buy all $$$n$$$ relics. Help her minimize the expected number of shards she spends to buy all the relics.

## Input Format
The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 100$$$; $$$1 \le x \le 10\,000$$$) — the number of relics and the cost to receive a random relic.

The second line consists of $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$x \le c_i \le 10\,000$$$; $$$\sum{c_i} \le 10\,000$$$) — the prices of $$$n$$$ relics.

## Output Format
Print a single real number — the minimum expected number of shards that Gloria must spend to buy all the relics.

The absolute or relative error should not exceed $$$10^{-9}$$$.

## Examples
```input
2 20
25 100
```
```output
47.50000000000000000
```
-----
```input
4 30
60 50 60 80
```
```output
171.25000000000000000
```

## Note
In the first example, the optimal strategy is to randomly get one of the two relics paying $$$20$$$ shards. Then there are two scenarios.

The first one happens if Gloria receives the first relic. Then she keeps getting random relics until she obtains the second relic. The expected number of shards to spend in this scenario is $$$20 + 30 = 50$$$.

In the second scenario, Gloria initially gets the second relic. Then it is better to buy the first relic for $$$25$$$ shards, so the expected number of shards to spend in this scenario is $$$20 + 25 = 45$$$.

Thus, the expected number of shards to spend is $$$\frac{50 + 45}{2} = 47.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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Karl is developing a key storage service. Each user has a positive integer key.

Karl knows that storing keys in plain text is bad practice. So, instead of storing a key, he decided to store a fingerprint of a key. However, using some existing fingerprint algorithm looked too boring to him, so he invented his own one.

Karl's fingerprint is calculated by the following process: divide the given integer by 2, then divide the result by 3, then divide the result by 4, and so on, until we get a result that equals zero (we are speaking about integer division each time). The fingerprint is defined as the multiset of the remainders of these divisions.

For example, this is how Karl's fingerprint algorithm is applied to the key 11: 11 divided by 2 has remainder 1 and result 5, then 5 divided by 3 has remainder 2 and result 1, and 1 divided by 4 has remainder 1 and result 0. Thus, the key 11 produces the sequence of remainders $$$[1, 2, 1]$$$ and has the fingerprint multiset $$$\{1, 1, 2\}$$$.

Ksenia wants to prove that Karl's fingerprint algorithm is not very good. For example, she found that both keys 178800 and 123456 produce the fingerprint of $$$\{0, 0, 0, 0, 2, 3, 3, 4\}$$$. Thus, users are at risk of fingerprint collision with some commonly used and easy to guess keys like 123456.

Ksenia wants to make her words more persuasive. She wants to calculate the number of other keys that have the same fingerprint as the keys in the given list of some commonly used keys. Your task is to help her.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 50\,000$$$) — the number of commonly used keys to examine. Each of the next $$$t$$$ lines contains one integer $$$k_i$$$ ($$$1 \le k_i \le 10^{18}$$$) — the key itself.

## Output Format
For each of the keys print one integer — the number of other keys that have the same fingerprint.

## Examples
```input
3
1
11
123456
```
```output
0
1
127
```

## Note
The other key with the same fingerprint as 11 is 15. 15 produces a sequence of remainders $$$[1, 1, 2]$$$. So both numbers have the fingerprint multiset $$$\{1, 1, 2\}$$$.

Now solve the problem and return the code.