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
Monocarp and Bicarp live in Berland, where every bus ticket consists of $$$n$$$ digits ($$$n$$$ is an even number). During the evening walk Monocarp and Bicarp found a ticket where some of the digits have been erased. The number of digits that have been erased is even.

Monocarp and Bicarp have decided to play a game with this ticket. Monocarp hates happy tickets, while Bicarp collects them. A ticket is considered happy if the sum of the first $$$\frac{n}{2}$$$ digits of this ticket is equal to the sum of the last $$$\frac{n}{2}$$$ digits.

Monocarp and Bicarp take turns (and Monocarp performs the first of them). During each turn, the current player must replace any erased digit with any digit from $$$0$$$ to $$$9$$$. The game ends when there are no erased digits in the ticket.

If the ticket is happy after all erased digits are replaced with decimal digits, then Bicarp wins. Otherwise, Monocarp wins. You have to determine who will win if both players play optimally.

## Input Format
The first line contains one even integer $$$n$$$ $$$(2 \le n \le 2 \cdot 10^{5})$$$ — the number of digits in the ticket.

The second line contains a string of $$$n$$$ digits and "?" characters — the ticket which Monocarp and Bicarp have found. If the $$$i$$$-th character is "?", then the $$$i$$$-th digit is erased. Note that there may be leading zeroes. The number of "?" characters is even.

## Output Format
If Monocarp wins, print "Monocarp" (without quotes). Otherwise print "Bicarp" (without quotes).

## Examples
```input
4
0523
```
```output
Bicarp
```
-----
```input
2
??
```
```output
Bicarp
```
-----
```input
8
?054??0?
```
```output
Bicarp
```
-----
```input
6
???00?
```
```output
Monocarp
```

## Note
Since there is no question mark in the ticket in the first example, the winner is determined before the game even starts, and it is Bicarp.

In the second example, Bicarp also wins. After Monocarp chooses an erased digit and replaces it with a new one, Bicap can choose another position with an erased digit and replace it with the same digit, so the ticket is happy.

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
Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

One day Petya was delivered a string s, containing only digits. He needs to find a string that

- represents a lucky number without leading zeroes,
- is not empty,
- is contained in s as a substring the maximum number of times.

Among all the strings for which the three conditions given above are fulfilled, Petya only needs the lexicographically minimum one. Find this string for Petya.

## Input Format
The single line contains a non-empty string s whose length can range from 1 to 50, inclusive. The string only contains digits. The string can contain leading zeroes.

## Output Format
In the only line print the answer to Petya's problem. If the sought string does not exist, print "-1" (without quotes).

## Examples
```input
047
```
```output
4
```
-----
```input
16
```
```output
-1
```
-----
```input
472747
```
```output
7
```

## Note
The lexicographical comparison of strings is performed by the < operator in the modern programming languages. String x is lexicographically less than string y either if x is a prefix of y, or exists such i (1 ≤ i ≤ min(|x|, |y|)), that xi < yi and for any j (1 ≤ j < i) xj = yj. Here |a| denotes the length of string a.

In the first sample three conditions are fulfilled for strings "4", "7" and "47". The lexicographically minimum one is "4".

In the second sample s has no substrings which are lucky numbers.

In the third sample the three conditions are only fulfilled for string "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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integers $$$x$$$ and $$$y$$$ (it is guaranteed that $$$x > y$$$). You may choose any prime integer $$$p$$$ and subtract it any number of times from $$$x$$$. Is it possible to make $$$x$$$ equal to $$$y$$$?

Recall that a prime number is a positive integer that has exactly two positive divisors: $$$1$$$ and this integer itself. The sequence of prime numbers starts with $$$2$$$, $$$3$$$, $$$5$$$, $$$7$$$, $$$11$$$.

Your program should solve $$$t$$$ independent test cases.

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

Then $$$t$$$ lines follow, each describing a test case. Each line contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le y < x \le 10^{18}$$$).

## Output Format
For each test case, print YES if it is possible to choose a prime number $$$p$$$ and subtract it any number of times from $$$x$$$ so that $$$x$$$ becomes equal to $$$y$$$. Otherwise, print NO.

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
100 98
42 32
1000000000000000000 1
41 40
```
```output
YES
YES
YES
NO
```

## Note
In the first test of the example you may choose $$$p = 2$$$ and subtract it once.

In the second test of the example you may choose $$$p = 5$$$ and subtract it twice. Note that you cannot choose $$$p = 7$$$, subtract it, then choose $$$p = 3$$$ and subtract it again.

In the third test of the example you may choose $$$p = 3$$$ and subtract it $$$333333333333333333$$$ times.

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 playing a game where your character should overcome different obstacles. The current problem is to come down from a cliff. The cliff has height $$$h$$$, and there is a moving platform on each height $$$x$$$ from $$$1$$$ to $$$h$$$.

Each platform is either hidden inside the cliff or moved out. At first, there are $$$n$$$ moved out platforms on heights $$$p_1, p_2, \dots, p_n$$$. The platform on height $$$h$$$ is moved out (and the character is initially standing there).

If you character is standing on some moved out platform on height $$$x$$$, then he can pull a special lever, which switches the state of two platforms: on height $$$x$$$ and $$$x - 1$$$. In other words, the platform you are currently standing on will hide in the cliff and the platform one unit below will change it state: it will hide if it was moved out or move out if it was hidden. In the second case, you will safely land on it. Note that this is the only way to move from one platform to another.

Your character is quite fragile, so it can safely fall from the height no more than $$$2$$$. In other words falling from the platform $$$x$$$ to platform $$$x - 2$$$ is okay, but falling from $$$x$$$ to $$$x - 3$$$ (or lower) is certain death.

Sometimes it's not possible to come down from the cliff, but you can always buy (for donate currency) several magic crystals. Each magic crystal can be used to change the state of any single platform (except platform on height $$$h$$$, which is unaffected by the crystals). After being used, the crystal disappears.

What is the minimum number of magic crystal you need to buy to safely land on the $$$0$$$ ground level?

## Input Format
The first line contains one integer $$$q$$$ ($$$1 \le q \le 100$$$) — the number of queries. Each query contains two lines and is independent of all other queries.

The first line of each query contains two integers $$$h$$$ and $$$n$$$ ($$$1 \le h \le 10^9$$$, $$$1 \le n \le \min(h, 2 \cdot 10^5)$$$) — the height of the cliff and the number of moved out platforms.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$h = p_1 > p_2 > \dots > p_n \ge 1$$$) — the corresponding moved out platforms in the descending order of their heights.

The sum of $$$n$$$ over all queries does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each query print one integer — the minimum number of magic crystals you have to spend to safely come down on the ground level (with height $$$0$$$).

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

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
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 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 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 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
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 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
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 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: 512.0 MB

# Problem
There is a string $$$s$$$ of lowercase English letters. A cursor is positioned on one of the characters. The cursor can be moved with the following operation: choose a letter $$$c$$$ and a direction (left or right). The cursor is then moved to the closest occurence of $$$c$$$ in the chosen direction. If there is no letter $$$c$$$ in that direction, the cursor stays in place. For example, if $$$s = \mathtt{abaab}$$$ with the cursor on the second character ($$$\mathtt{a[b]aab}$$$), then:

- moving to the closest letter $$$\mathtt{a}$$$ to the left places the cursor on the first character ($$$\mathtt{[a]baab}$$$);
- moving to the closest letter $$$\mathtt{a}$$$ to the right places the cursor the third character ($$$\mathtt{ab[a]ab}$$$);
- moving to the closest letter $$$\mathtt{b}$$$ to the right places the cursor on the fifth character ($$$\mathtt{abaa[b]}$$$);
- any other operation leaves the cursor in place.

Let $$$\mathrm{dist}(i, j)$$$ be the smallest number of operations needed to move the cursor from the $$$i$$$-th character to the $$$j$$$-th character. Compute $$$\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$$$.

## Input Format
The only line contains a non-empty string $$$s$$$ of at most $$$10^5$$$ lowercase English letters.

## Output Format
Print a single integer $$$\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$$$.

## Examples
```input
abcde
```
```output
20
```
-----
```input
abacaba
```
```output
58
```

## Note
In the first sample case, $$$\mathrm{dist}(i, j) = 0$$$ for any pair $$$i = j$$$, and $$$1$$$ for all other pairs.

Now solve the problem and return the code.