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: 6.0 seconds
Memory limit: 512.0 MB

# Problem
You are given an array $$$[a_1, a_2, \dots, a_n]$$$, consisting of positive integers.

For every $$$i$$$ from $$$1$$$ to $$$n$$$, calculate $$$\sum \limits_{j=1}^{n} F(a_i + a_j)$$$, where $$$F(x)$$$ is the sum of digits of $$$x$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

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

## Output Format
Print $$$n$$$ integers. The $$$i$$$-th of them should be equal to $$$\sum \limits_{j=1}^{n} F(a_i + a_j)$$$.

## Examples
```input
4
1 3 3 7
```
```output
18 17 17 15
```
-----
```input
3
42 1337 999
```
```output
38 53 47
```

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
Consider the following problem.

You are given a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters, and an integer $$$k$$$ ($$$n$$$ is not divisible by $$$k$$$). Each letter is one of the first $$$c$$$ letters of the alphabet.

You apply the following operation until the length of the string is less than $$$k$$$: choose a contiguous substring of the string of length exactly $$$k$$$, remove it from the string and glue the resulting parts together without changing the order.

Let the resulting string of length smaller than $$$k$$$ be $$$t$$$. What is lexicographically smallest string $$$t$$$ that can obtained?

You are asked the inverse of this problem. Given two integers $$$n$$$ and $$$k$$$ ($$$n$$$ is not divisible by $$$k$$$) and a string $$$t$$$, consisting of ($$$n \bmod k$$$) lowercase Latin letters, count the number of strings $$$s$$$ that produce $$$t$$$ as the lexicographically smallest solution.

Print that number modulo $$$998\,244\,353$$$.

## Input Format
The first line contains three integers $$$n, k$$$ and $$$c$$$ ($$$1 \le n \le 10^6$$$; $$$2 \le k \le 10^6$$$; $$$1 \le c \le 26$$$; $$$n$$$ is not divisible by $$$k$$$) — the length of string $$$s$$$, the length of the substring that is being removed and the number of first letters from the alphabet.

The second line contains string $$$t$$$, consisting of exactly ($$$n \bmod k$$$) lowercase Latin letters. Each letter is one of the first $$$c$$$ letters of the alphabet.

## Output Format
Print a single integer — the number of strings $$$s$$$ that produce $$$t$$$ as the lexicographically smallest solution.

## Examples
```input
3 2 2
a
```
```output
6
```
-----
```input
5 3 3
bc
```
```output
15
```
-----
```input
34 12 26
codeforces
```
```output
988024123
```
-----
```input
5 3 1
aa
```
```output
1
```

## Note
The strings $$$s$$$ in the first example: "aaa", "aab", "aba", "abb", "baa", "bba".

The strings $$$s$$$ in the second example: "bcabc", "bcacc", "bcbbc", "bcbcc", "bccbc", "bcccc", "caabc", "cabbc", "cacbc", "cbabc", "cbbbc", "cbcbc", "ccabc", "ccbbc", "cccbc".

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: 4.0 seconds
Memory limit: 512.0 MB

# Problem
You are given a tree consisting of $$$n$$$ vertices. Some vertices of the tree are red, all other vertices are blue.

Each edge of the tree has a positive weight. Let's define $$$d(x, y)$$$ as the distance between the vertices $$$x$$$ and $$$y$$$, i. e. the sum of weights of edges belonging to the simple path between $$$x$$$ and $$$y$$$.

For each vertex, you have to choose an integer $$$v_i$$$. These integers should meet the following constraint: for every blue vertex $$$b$$$ and every red vertex $$$r$$$, $$$d(b, r) \ge v_b + v_r$$$.

You have to maximize the value of $$$\sum \limits_{i=1}^{n} v_i$$$.

Note that the values of $$$v_i$$$ are not necessarily positive.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 1$$$). If the $$$i$$$-th vertex is red, $$$c_i = 1$$$, otherwise $$$c_i = 0$$$.

Then $$$n-1$$$ lines follow. Each line contains three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$1 \le w_i \le 10^6$$$; $$$x_i \ne y_i$$$) denoting an edge between the vertices $$$x_i$$$ and $$$y_i$$$ which has weight $$$w_i$$$. These edges form a tree.

## Output Format
If the value of $$$\sum \limits_{i=1}^{n} v_i$$$ can be as big as possible, print Infinity. Otherwise, print one integer — the maximum possible value of $$$\sum \limits_{i=1}^{n} v_i$$$ you can get.

## Examples
```input
4
1 1 0 0
3 4 50
3 2 100
2 1 100
```
```output
350
```
-----
```input
6
0 1 0 1 0 1
1 2 1
1 4 1
1 6 1
6 5 100
6 3 100
```
```output
203
```
-----
```input
3
1 1 1
1 2 100
2 3 100
```
```output
Infinity
```

## Note
In the first example, you can assign $$$v_1 = 120, v_2 = 20, v_3 = 80, v_4 = 130$$$.

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
Monocarp is participating in a programming contest, which features $$$26$$$ problems, named from 'A' to 'Z'. The problems are sorted by difficulty. Moreover, it's known that Monocarp can solve problem 'A' in $$$1$$$ minute, problem 'B' in $$$2$$$ minutes, ..., problem 'Z' in $$$26$$$ minutes.

After the contest, you discovered his contest log — a string, consisting of uppercase Latin letters, such that the $$$i$$$-th letter tells which problem Monocarp was solving during the $$$i$$$-th minute of the contest. If Monocarp had spent enough time in total on a problem to solve it, he solved it. Note that Monocarp could have been thinking about a problem after solving it.

Given Monocarp's contest log, calculate the number of problems he solved during the contest.

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

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 500$$$) — the duration of the contest, in minutes.

The second line contains a string of length exactly $$$n$$$, consisting only of uppercase Latin letters, — Monocarp's contest log.

## Output Format
For each testcase, print a single integer — the number of problems Monocarp solved during the contest.

## Examples
```input
3
6
ACBCBC
7
AAAAFPC
22
FEADBBDFFEDFFFDHHHADCC
```
```output
3
1
4
```

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
Monocarp is practicing for a big contest. He plans to solve $$$n$$$ problems to make sure he's prepared. Each of these problems has a difficulty level: the first problem has a difficulty level of $$$1$$$, the second problem has a difficulty level of $$$2$$$, and so on, until the last ($$$n$$$-th) problem, which has a difficulty level of $$$n$$$.

Monocarp will choose some order in which he is going to solve all $$$n$$$ problems. Whenever he solves a problem which is more difficult than the last problem he solved, he gets excited because he feels like he's progressing. He doesn't get excited when he solves the first problem in his chosen order.

For example, if Monocarp solves the problems in the order $$$[3, \underline{5}, 4, 1, \underline{6}, 2]$$$, he gets excited twice (the corresponding problems are underlined).

Monocarp wants to get excited exactly $$$k$$$ times during his practicing session. Help him to choose the order in which he has to solve the problems!

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

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 50$$$; $$$0 \le k \le n - 1$$$).

## Output Format
For each test case, print $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$, denoting the order in which Monocarp should solve the problems. If there are multiple answers, print any of them.

It can be shown that under the constraints of the problem, the answer always exists.

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

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
BerSoft is the biggest IT corporation in Berland. There are $$$n$$$ employees at BerSoft company, numbered from $$$1$$$ to $$$n$$$.

The first employee is the head of the company, and he does not have any superiors. Every other employee $$$i$$$ has exactly one direct superior $$$p_i$$$.

Employee $$$x$$$ is considered to be a superior (direct or indirect) of employee $$$y$$$ if one of the following conditions holds:

- employee $$$x$$$ is the direct superior of employee $$$y$$$;
- employee $$$x$$$ is a superior of the direct superior of employee $$$y$$$.

The structure of BerSoft is organized in such a way that the head of the company is superior of every employee.

A programming competition is going to be held soon. Two-person teams should be created for this purpose. However, if one employee in a team is the superior of another, they are uncomfortable together. So, teams of two people should be created so that no one is the superior of the other. Note that no employee can participate in more than one team.

Your task is to calculate the maximum possible number of teams according to the aforementioned rules.

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of employees.

The second line contains $$$n-1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is the index of the direct superior of the $$$i$$$-th employee.

The sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single integer — the maximum possible number of teams according to the aforementioned rules.

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

## Note
In the first test case, team $$$(3, 4)$$$ can be created.

In the second test case, no team can be created, because there are only $$$2$$$ employees and one is the superior of another.

In the third test case, team $$$(2, 3)$$$ can be created.

In the fourth test case, teams $$$(2, 4)$$$, $$$(3, 5)$$$ and $$$(6, 7)$$$ can be created.

In the fifth test case, teams $$$(2, 3)$$$, $$$(6, 4)$$$ and $$$(5, 7)$$$ can be created.

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

# Problem
Jay managed to create a problem of difficulty $$$x$$$ and decided to make it the second problem for Codeforces Round #921.

But Yash fears that this problem will make the contest highly unbalanced, and the coordinator will reject it. So, he decided to break it up into a problemset of $$$n$$$ sub-problems such that the difficulties of all the sub-problems are a positive integer and their sum is equal to $$$x$$$.

The coordinator, Aleksey, defines the balance of a problemset as the GCD of the difficulties of all sub-problems in the problemset.

Find the maximum balance that Yash can achieve if he chooses the difficulties of the sub-problems optimally.

## Input Format
The first line of input contains a single integer $$$t$$$ ($$$1\leq t\leq 10^3$$$) denoting the number of test cases.

Each test case contains a single line of input containing two integers $$$x$$$ ($$$1\leq x\leq 10^8$$$) and $$$n$$$ ($$$1\leq n\leq x$$$).

## Output Format
For each test case, print a single line containing a single integer denoting the maximum balance of the problemset Yash can achieve.

## Examples
```input
3
10 3
5 5
420 69
```
```output
2
1
6
```

## Note
For the first test case, one possible way is to break up the problem of difficulty $$$10$$$ into a problemset having three problems of difficulties $$$4$$$, $$$2$$$ and $$$4$$$ respectively, giving a balance equal to $$$2$$$.

For the second test case, there is only one way to break up the problem of difficulty $$$5$$$ into a problemset of $$$5$$$ problems with each problem having a difficulty $$$1$$$ giving a balance equal to $$$1$$$.

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

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

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

Execution time limit: 4.0 seconds
Memory limit: 1024.0 MB

# Problem
You are given a binary string$$$^\dagger$$$ $$$s$$$ of length $$$n$$$.

A binary string $$$p$$$ of the same length $$$n$$$ is called good if for every $$$i$$$ ($$$1 \leq i \leq n$$$), there exist indices $$$l$$$ and $$$r$$$ such that:

- $$$1 \leq l \leq i \leq r \leq n$$$
- $$$s_i$$$ is a mode$$$^\ddagger$$$ of the string $$$p_lp_{l+1}\ldots p_r$$$

You are given another binary string $$$t$$$ of length $$$n$$$. Find the minimum Hamming distance$$$^\S$$$ between $$$t$$$ and any good string $$$g$$$.

$$$^\dagger$$$ A binary string is a string that only consists of characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

$$$^\ddagger$$$ Character $$$c$$$ is a mode of string $$$p$$$ of length $$$m$$$ if the number of occurrences of $$$c$$$ in $$$p$$$ is at least $$$\lceil \frac{m}{2} \rceil$$$. For example, $$$\mathtt{0}$$$ is a mode of $$$\mathtt{010}$$$, $$$\mathtt{1}$$$ is not a mode of $$$\mathtt{010}$$$, and both $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ are modes of $$$\mathtt{011010}$$$.

$$$^\S$$$ The Hamming distance of strings $$$a$$$ and $$$b$$$ of length $$$m$$$ is the number of indices $$$i$$$ such that $$$1 \leq i \leq m$$$ and $$$a_i \neq b_i$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^4$$$) — the length of the binary string $$$s$$$.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ consisting of characters 0 and 1.

The third line of each test case contains a binary string $$$t$$$ of length $$$n$$$ consisting of characters 0 and 1.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$, with the additional assurance that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^8$$$

## Output Format
For each test case, print the minimum Hamming distance between $$$t$$$ and any good string $$$g$$$.

## Examples
```input
3
3
000
000
4
0000
1111
6
111111
000100
```
```output
0
2
1
```

## Note
In the first test case, $$$g=\mathtt{000}$$$ is a good string which has Hamming distance $$$0$$$ from $$$t$$$.

In the second test case, $$$g=\mathtt{0011}$$$ is a good string which has Hamming distance $$$2$$$ from $$$t$$$. It can be proven that there are no good strings with Hamming distance less than $$$2$$$ from $$$t$$$.

In the third test case, $$$g=\mathtt{001100}$$$ is a good string which has Hamming distance $$$1$$$ from $$$t$$$.

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 contest contains $$$n$$$ problems and the difficulty of the $$$i$$$-th problem is expected to be at most $$$b_i$$$. There are already $$$n$$$ problem proposals and the difficulty of the $$$i$$$-th problem is $$$a_i$$$. Initially, both $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$ are sorted in non-decreasing order.

Some of the problems may be more difficult than expected, so the writers must propose more problems. When a new problem with difficulty $$$w$$$ is proposed, the most difficult problem will be deleted from the contest, and the problems will be sorted in a way that the difficulties are non-decreasing.

In other words, in each operation, you choose an integer $$$w$$$, insert it into the array $$$a$$$, sort array $$$a$$$ in non-decreasing order, and remove the last element from it.

Find the minimum number of new problems to make $$$a_i\le b_i$$$ for all $$$i$$$.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\le t\le 100$$$). The description of the test cases follows.

The first line of each test case contains only one positive integer $$$n$$$ ($$$1 \leq n \leq 100$$$), representing the number of problems.

The second line of each test case contains an array $$$a$$$ of length $$$n$$$ ($$$1\le a_1\le a_2\le\cdots\le a_n\le 10^9$$$).

The third line of each test case contains an array $$$b$$$ of length $$$n$$$ ($$$1\le b_1\le b_2\le\cdots\le b_n\le 10^9$$$).

## Output Format
For each test case, print an integer as your answer in a new line.

## Examples
```input
2
6
1000 1400 2000 2000 2200 2700
800 1200 1500 1800 2200 3000
6
4 5 6 7 8 9
1 2 3 4 5 6
```
```output
2
3
```

## Note
In the first test case:

- Propose a problem with difficulty $$$w=800$$$ and $$$a$$$ becomes $$$[800,1000,1400,2000,2000,2200]$$$.
- Propose a problem with difficulty $$$w=1800$$$ and $$$a$$$ becomes $$$[800,1000,1400,1800,2000,2000]$$$.

It can be proved that it's impossible to reach the goal by proposing fewer new problems.

In the second test case:

- Propose a problem with difficulty $$$w=1$$$ and $$$a$$$ becomes $$$[1,4,5,6,7,8]$$$.
- Propose a problem with difficulty $$$w=2$$$ and $$$a$$$ becomes $$$[1,2,4,5,6,7]$$$.
- Propose a problem with difficulty $$$w=3$$$ and $$$a$$$ becomes $$$[1,2,3,4,5,6]$$$.

It can be proved that it's impossible to reach the goal by proposing fewer new problems.

Now solve the problem and return the code.