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
On a random day, Neko found $$$n$$$ treasure chests and $$$m$$$ keys. The $$$i$$$-th chest has an integer $$$a_i$$$ written on it and the $$$j$$$-th key has an integer $$$b_j$$$ on it. Neko knows those chests contain the powerful mysterious green Grapes, thus Neko wants to open as many treasure chests as possible.

The $$$j$$$-th key can be used to unlock the $$$i$$$-th chest if and only if the sum of the key number and the chest number is an odd number. Formally, $$$a_i + b_j \equiv 1 \pmod{2}$$$. One key can be used to open at most one chest, and one chest can be opened at most once.

Find the maximum number of chests Neko can open.

## Input Format
The first line contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$) — the number of chests and the number of keys.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the numbers written on the treasure chests.

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$) — the numbers written on the keys.

## Output Format
Print the maximum number of chests you can open.

## Examples
```input
5 4
9 14 6 2 11
8 4 7 20
```
```output
3
```
-----
```input
5 1
2 4 6 8 10
5
```
```output
1
```
-----
```input
1 4
10
20 30 40 50
```
```output
0
```

## Note
In the first example, one possible way to unlock $$$3$$$ chests is as follows:

- Use first key to unlock the fifth chest,
- Use third key to unlock the second chest,
- Use fourth key to unlock the first chest.

In the second example, you can use the only key to unlock any single chest (note that one key can't be used twice).

In the third example, no key can unlock the given chest.

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
Neko loves divisors. During the latest number theory lesson, he got an interesting exercise from his math teacher.

Neko has two integers $$$a$$$ and $$$b$$$. His goal is to find a non-negative integer $$$k$$$ such that the least common multiple of $$$a+k$$$ and $$$b+k$$$ is the smallest possible. If there are multiple optimal integers $$$k$$$, he needs to choose the smallest one.

Given his mathematical talent, Neko had no trouble getting Wrong Answer on this problem. Can you help him solve it?

## Input Format
The only line contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$).

## Output Format
Print the smallest non-negative integer $$$k$$$ ($$$k \ge 0$$$) such that the lowest common multiple of $$$a+k$$$ and $$$b+k$$$ is the smallest possible.

If there are many possible integers $$$k$$$ giving the same value of the least common multiple, print the smallest one.

## Examples
```input
6 10
```
```output
2
```
-----
```input
21 31
```
```output
9
```
-----
```input
5 10
```
```output
0
```

## Note
In the first test, one should choose $$$k = 2$$$, as the least common multiple of $$$6 + 2$$$ and $$$10 + 2$$$ is $$$24$$$, which is the smallest least common multiple possible.

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
Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, he went overboard and put an entire bag of catnip into the toys...

It took Neko an entire day to turn back to normal. Neko reported to Aki that he saw a lot of weird things, including a trie of all correct bracket sequences of length $$$2n$$$.

The definition of correct bracket sequence is as follows:

- The empty sequence is a correct bracket sequence,
- If $$$s$$$ is a correct bracket sequence, then $$$(\,s\,)$$$ is a correct bracket sequence,
- If $$$s$$$ and $$$t$$$ are a correct bracket sequence, then $$$st$$$ is also a correct bracket sequence.

For example, the strings "(())", "()()" form a correct bracket sequence, while ")(" and "((" not.

Aki then came up with an interesting problem: What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie? Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

## Input Format
The only line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$).

## Output Format
Print exactly one integer — the size of the maximum matching in the trie. Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

## Examples
```input
1
```
```output
1
```
-----
```input
2
```
```output
3
```
-----
```input
3
```
```output
9
```

## Note
The pictures below illustrate tries in the first two examples (for clarity, the round brackets are replaced with angle brackets). The maximum matching is highlighted with blue.

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

# Problem
This problem is same as the previous one, but has larger constraints.

Aki is playing a new video game. In the video game, he will control Neko, the giant cat, to fly between planets in the Catniverse.

There are $$$n$$$ planets in the Catniverse, numbered from $$$1$$$ to $$$n$$$. At the beginning of the game, Aki chooses the planet where Neko is initially located. Then Aki performs $$$k - 1$$$ moves, where in each move Neko is moved from the current planet $$$x$$$ to some other planet $$$y$$$ such that:

- Planet $$$y$$$ is not visited yet.
- $$$1 \leq y \leq x + m$$$ (where $$$m$$$ is a fixed constant given in the input)

This way, Neko will visit exactly $$$k$$$ different planets. Two ways of visiting planets are called different if there is some index $$$i$$$ such that, the $$$i$$$-th planet visited in the first way is different from the $$$i$$$-th planet visited in the second way.

What is the total number of ways to visit $$$k$$$ planets this way? Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

## Input Format
The only line contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le k \le \min(n, 12)$$$, $$$1 \le m \le 4$$$) — the number of planets in the Catniverse, the number of planets Neko needs to visit and the said constant $$$m$$$.

## Output Format
Print exactly one integer — the number of different ways Neko can visit exactly $$$k$$$ planets. Since the answer can be quite large, print it modulo $$$10^9 + 7$$$.

## Examples
```input
3 3 1
```
```output
4
```
-----
```input
4 2 1
```
```output
9
```
-----
```input
5 5 4
```
```output
120
```
-----
```input
100 1 2
```
```output
100
```

## Note
In the first example, there are $$$4$$$ ways Neko can visit all the planets:

- $$$1 \rightarrow 2 \rightarrow 3$$$
- $$$2 \rightarrow 3 \rightarrow 1$$$
- $$$3 \rightarrow 1 \rightarrow 2$$$
- $$$3 \rightarrow 2 \rightarrow 1$$$

In the second example, there are $$$9$$$ ways Neko can visit exactly $$$2$$$ planets:

- $$$1 \rightarrow 2$$$
- $$$2 \rightarrow 1$$$
- $$$2 \rightarrow 3$$$
- $$$3 \rightarrow 1$$$
- $$$3 \rightarrow 2$$$
- $$$3 \rightarrow 4$$$
- $$$4 \rightarrow 1$$$
- $$$4 \rightarrow 2$$$
- $$$4 \rightarrow 3$$$

In the third example, with $$$m = 4$$$, Neko can visit all the planets in any order, so there are $$$5! = 120$$$ ways Neko can visit all the planets.

In the fourth example, Neko only visit exactly $$$1$$$ planet (which is also the planet he initially located), and there are $$$100$$$ ways to choose the starting planet for Neko.

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
The three friends, Kuro, Shiro, and Katie, met up again! It's time for a party...

What the cats do when they unite? Right, they have a party. Since they wanted to have as much fun as possible, they invited all their friends. Now $$$n$$$ cats are at the party, sitting in a circle and eating soup. The rules are simple: anyone having finished their soup leaves the circle.

Katie suddenly notices that whenever a cat leaves, the place where she was sitting becomes an empty space, which means the circle is divided into smaller continuous groups of cats sitting next to each other. At the moment Katie observes, there are $$$m$$$ cats who left the circle. This raises a question for Katie: what is the maximum possible number of groups the circle is divided into at the moment?

Could you help her with this curiosity?

You can see the examples and their descriptions with pictures in the "Note" section.

## Input Format
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 1000$$$, $$$0 \leq m \leq n$$$) — the initial number of cats at the party and the number of cats who left the circle at the moment Katie observes, respectively.

## Output Format
Print a single integer — the maximum number of groups of cats at the moment Katie observes.

## Examples
```input
7 4
```
```output
3
```
-----
```input
6 2
```
```output
2
```
-----
```input
3 0
```
```output
1
```
-----
```input
2 2
```
```output
0
```

## Note
In the first example, originally there are $$$7$$$ cats sitting as shown below, creating a single group:

At the observed moment, $$$4$$$ cats have left the table. Suppose the cats $$$2$$$, $$$3$$$, $$$5$$$ and $$$7$$$ have left, then there are $$$3$$$ groups remaining. It is possible to show that it is the maximum possible number of groups remaining.

In the second example, there are $$$6$$$ cats sitting as shown below:

At the observed moment, $$$2$$$ cats have left the table. Suppose the cats numbered $$$3$$$ and $$$6$$$ left, then there will be $$$2$$$ groups remaining ($$$\{1, 2\}$$$ and $$$\{4, 5\}$$$). It is impossible to have more than $$$2$$$ groups of cats remaining.

In the third example, no cats have left, so there is $$$1$$$ group consisting of all cats.

In the fourth example, all cats have left the circle, so there are $$$0$$$ groups.

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
This problem is same as the next one, but has smaller constraints.

Shiro's just moved to the new house. She wants to invite all friends of her to the house so they can play monopoly. However, her house is too small, so she can only invite one friend at a time.

For each of the $$$n$$$ days since the day Shiro moved to the new house, there will be exactly one cat coming to the Shiro's house. The cat coming in the $$$i$$$-th day has a ribbon with color $$$u_i$$$. Shiro wants to know the largest number $$$x$$$, such that if we consider the streak of the first $$$x$$$ days, it is possible to remove exactly one day from this streak so that every ribbon color that has appeared among the remaining $$$x - 1$$$ will have the same number of occurrences.

For example, consider the following sequence of $$$u_i$$$: $$$[2, 2, 1, 1, 5, 4, 4, 5]$$$. Then $$$x = 7$$$ makes a streak, since if we remove the leftmost $$$u_i = 5$$$, each ribbon color will appear exactly twice in the prefix of $$$x - 1$$$ days. Note that $$$x = 8$$$ doesn't form a streak, since you must remove exactly one day.

Since Shiro is just a cat, she is not very good at counting and needs your help finding the longest streak.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the total number of days.

The second line contains $$$n$$$ integers $$$u_1, u_2, \ldots, u_n$$$ ($$$1 \leq u_i \leq 10$$$) — the colors of the ribbons the cats wear.

## Output Format
Print a single integer $$$x$$$ — the largest possible streak of days.

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

## Note
In the first example, we can choose the longest streak of $$$13$$$ days, since upon removing the last day out of the streak, all of the remaining colors $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$ will have the same number of occurrences of $$$3$$$. Note that the streak can also be $$$10$$$ days (by removing the $$$10$$$-th day from this streak) but we are interested in the longest streak.

In the fourth example, if we take the streak of the first $$$6$$$ days, we can remove the third day from this streak then all of the remaining colors $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ and $$$5$$$ will occur exactly once.

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
This problem is same as the previous one, but has larger constraints.

Shiro's just moved to the new house. She wants to invite all friends of her to the house so they can play monopoly. However, her house is too small, so she can only invite one friend at a time.

For each of the $$$n$$$ days since the day Shiro moved to the new house, there will be exactly one cat coming to the Shiro's house. The cat coming in the $$$i$$$-th day has a ribbon with color $$$u_i$$$. Shiro wants to know the largest number $$$x$$$, such that if we consider the streak of the first $$$x$$$ days, it is possible to remove exactly one day from this streak so that every ribbon color that has appeared among the remaining $$$x - 1$$$ will have the same number of occurrences.

For example, consider the following sequence of $$$u_i$$$: $$$[2, 2, 1, 1, 5, 4, 4, 5]$$$. Then $$$x = 7$$$ makes a streak, since if we remove the leftmost $$$u_i = 5$$$, each ribbon color will appear exactly twice in the prefix of $$$x - 1$$$ days. Note that $$$x = 8$$$ doesn't form a streak, since you must remove exactly one day.

Since Shiro is just a cat, she is not very good at counting and needs your help finding the longest streak.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the total number of days.

The second line contains $$$n$$$ integers $$$u_1, u_2, \ldots, u_n$$$ ($$$1 \leq u_i \leq 10^5$$$) — the colors of the ribbons the cats wear.

## Output Format
Print a single integer $$$x$$$ — the largest possible streak of days.

## Examples
```input
13
1 1 1 2 2 2 3 3 3 4 4 4 5
```
```output
13
```
-----
```input
5
10 100 20 200 1
```
```output
5
```
-----
```input
1
100000
```
```output
1
```
-----
```input
7
3 2 1 1 4 5 1
```
```output
6
```
-----
```input
6
1 1 1 2 2 2
```
```output
5
```

## Note
In the first example, we can choose the longest streak of $$$13$$$ days, since upon removing the last day out of the streak, all of the remaining colors $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$ will have the same number of occurrences of $$$3$$$. Note that the streak can also be $$$10$$$ days (by removing the $$$10$$$-th day from this streak) but we are interested in the longest streak.

In the fourth example, if we take the streak of the first $$$6$$$ days, we can remove the third day from this streak then all of the remaining colors $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ and $$$5$$$ will occur exactly once.

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
During a normal walk in the forest, Katie has stumbled upon a mysterious code! However, the mysterious code had some characters unreadable. She has written down this code as a string $$$c$$$ consisting of lowercase English characters and asterisks ("*"), where each of the asterisks denotes an unreadable character. Excited with her discovery, Katie has decided to recover the unreadable characters by replacing each asterisk with arbitrary lowercase English letter (different asterisks might be replaced with different letters).

Katie has a favorite string $$$s$$$ and a not-so-favorite string $$$t$$$ and she would love to recover the mysterious code so that it has as many occurrences of $$$s$$$ as possible and as little occurrences of $$$t$$$ as possible. Formally, let's denote $$$f(x, y)$$$ as the number of occurrences of $$$y$$$ in $$$x$$$ (for example, $$$f(aababa, ab) = 2$$$). Katie wants to recover the code $$$c'$$$ conforming to the original $$$c$$$, such that $$$f(c', s) - f(c', t)$$$ is largest possible. However, Katie is not very good at recovering codes in general, so she would like you to help her out.

## Input Format
The first line contains string $$$c$$$ ($$$1 \leq |c| \leq 1000$$$) — the mysterious code . It is guaranteed that $$$c$$$ consists of lowercase English characters and asterisks "*" only.

The second and third line contain strings $$$s$$$ and $$$t$$$ respectively ($$$1 \leq |s|, |t| \leq 50$$$, $$$s \neq t$$$). It is guaranteed that $$$s$$$ and $$$t$$$ consist of lowercase English characters only.

## Output Format
Print a single integer — the largest possible value of $$$f(c', s) - f(c', t)$$$ of the recovered code.

## Examples
```input
*****
katie
shiro
```
```output
1
```
-----
```input
caat
caat
a
```
```output
-1
```
-----
```input
*a*
bba
b
```
```output
0
```
-----
```input
***
cc
z
```
```output
2
```

## Note
In the first example, for $$$c'$$$ equal to "katie" $$$f(c', s) = 1$$$ and $$$f(c', t) = 0$$$, which makes $$$f(c', s) - f(c', t) = 1$$$ which is the largest possible.

In the second example, the only $$$c'$$$ conforming to the given $$$c$$$ is "caat". The corresponding $$$f(c', s) - f(c', t) = 1 - 2 = -1$$$.

In the third example, there are multiple ways to recover the code such that $$$f(c', s) - f(c', t)$$$ is largest possible, for example "aaa", "aac", or even "zaz". The value of $$$f(c', s) - f(c', t) = 0$$$ for all of these recovered codes.

In the fourth example, the optimal recovered code $$$c'$$$ would be "ccc". The corresponding $$$f(c', s) - f(c', t) = 2$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an integer $$$n$$$ and an integer $$$k$$$.

In one step you can do one of the following moves:

- decrease $$$n$$$ by $$$1$$$;
- divide $$$n$$$ by $$$k$$$ if $$$n$$$ is divisible by $$$k$$$.

For example, if $$$n = 27$$$ and $$$k = 3$$$ you can do the following steps: $$$27 \rightarrow 26 \rightarrow 25 \rightarrow 24 \rightarrow 8 \rightarrow 7 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$$$.

You are asked to calculate the minimum number of steps to reach $$$0$$$ from $$$n$$$.

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

The only line of each query contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$2 \le k \le 10^{18}$$$).

## Output Format
For each query print the minimum number of steps to reach $$$0$$$ from $$$n$$$ in single line.

## Examples
```input
2
59 3
1000000000000000000 10
```
```output
8
19
```

## Note
Steps for the first test case are: $$$59 \rightarrow 58 \rightarrow 57 \rightarrow 19 \rightarrow 18 \rightarrow 6 \rightarrow 2 \rightarrow 1 \rightarrow 0$$$.

In the second test case you have to divide $$$n$$$ by $$$k$$$ $$$18$$$ times and then decrease $$$n$$$ by $$$1$$$.

Now solve the problem and return the code.