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
A car number in Berland consists of exactly n digits. A number is called beautiful if it has at least k equal digits. Vasya wants to change the digits in his car's number so that the number became beautiful. To replace one of n digits Vasya has to pay the sum of money, equal to the absolute difference between the old digit and the new one.

Help Vasya: find the minimum sum of money he should pay to make the number of his car beautiful. You should also find the resulting beautiful number. If there are several such numbers, then print the lexicographically minimum one.

## Input Format
The first line contains two space-separated integers n and k (2 ≤ n ≤ 104, 2 ≤ k ≤ n) which represent how many digits the number has and how many equal digits a beautiful number should have. The second line consists of n digits. It describes the old number of Vasya's car. It is guaranteed that the number contains no spaces and only contains digits.

## Output Format
On the first line print the minimum sum of money Vasya needs to change the number. On the second line print the car's new number. If there are several solutions, print the lexicographically minimum one.

## Examples
```input
6 5
898196
```
```output
4
888188
```
-----
```input
3 2
533
```
```output
0
533
```
-----
```input
10 6
0001112223
```
```output
3
0000002223
```

## Note
In the first sample replacing the second digit with an "8" costs |9 - 8| = 1. Replacing the fifth digit with an "8" costs the same. Replacing the sixth digit costs |6 - 8| = 2. As a result, Vasya will pay 1 + 1 + 2 = 4 for a beautiful number "888188".

The lexicographical comparison of strings is performed by the < operator in modern programming languages. The string x is lexicographically smaller than the string y, if there exists such i (1 ≤ i ≤ n), that xi < yi, and for any j (1 ≤ j < i) xj = yj. The strings compared in this problem will always have the length n.

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
Gaius Julius Caesar, a famous general, loved to line up his soldiers. Overall the army had n1 footmen and n2 horsemen. Caesar thought that an arrangement is not beautiful if somewhere in the line there are strictly more that k1 footmen standing successively one after another, or there are strictly more than k2 horsemen standing successively one after another. Find the number of beautiful arrangements of the soldiers.

Note that all n1 + n2 warriors should be present at each arrangement. All footmen are considered indistinguishable among themselves. Similarly, all horsemen are considered indistinguishable among themselves.

## Input Format
The only line contains four space-separated integers n1, n2, k1, k2 (1 ≤ n1, n2 ≤ 100, 1 ≤ k1, k2 ≤ 10) which represent how many footmen and horsemen there are and the largest acceptable number of footmen and horsemen standing in succession, correspondingly.

## Output Format
Print the number of beautiful arrangements of the army modulo 100000000 (108). That is, print the number of such ways to line up the soldiers, that no more than k1 footmen stand successively, and no more than k2 horsemen stand successively.

## Examples
```input
2 1 1 10
```
```output
1
```
-----
```input
2 3 1 2
```
```output
5
```
-----
```input
2 4 1 1
```
```output
0
```

## Note
Let's mark a footman as 1, and a horseman as 2.

In the first sample the only beautiful line-up is: 121

In the second sample 5 beautiful line-ups exist: 12122, 12212, 21212, 21221, 22121

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

# Problem
Bertown has n junctions and m bidirectional roads. We know that one can get from any junction to any other one by the existing roads.

As there were more and more cars in the city, traffic jams started to pose real problems. To deal with them the government decided to make the traffic one-directional on all the roads, thus easing down the traffic. Your task is to determine whether there is a way to make the traffic one-directional so that there still is the possibility to get from any junction to any other one. If the answer is positive, you should also find one of the possible ways to orient the roads.

## Input Format
The first line contains two space-separated integers n and m (2 ≤ n ≤ 105, n - 1 ≤ m ≤ 3·105) which represent the number of junctions and the roads in the town correspondingly. Then follow m lines, each containing two numbers which describe the roads in the city. Each road is determined by two integers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — the numbers of junctions it connects.

It is guaranteed that one can get from any junction to any other one along the existing bidirectional roads. Each road connects different junctions, there is no more than one road between each pair of junctions.

## Output Format
If there's no solution, print the single number 0. Otherwise, print m lines each containing two integers pi and qi — each road's orientation. That is the traffic flow will move along a one-directional road from junction pi to junction qi. You can print the roads in any order. If there are several solutions to that problem, print any of them.

## Examples
```input
6 8
1 2
2 3
1 3
4 5
4 6
5 6
2 4
3 5
```
```output
1 2
2 3
3 1
4 5
5 6
6 4
4 2
3 5
```
-----
```input
6 7
1 2
2 3
1 3
4 5
4 6
5 6
2 4
```
```output
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
Your favorite shop sells $$$n$$$ Kinder Surprise chocolate eggs. You know that exactly $$$s$$$ stickers and exactly $$$t$$$ toys are placed in $$$n$$$ eggs in total.

Each Kinder Surprise can be one of three types:

- it can contain a single sticker and no toy;
- it can contain a single toy and no sticker;
- it can contain both a single sticker and a single toy.

But you don't know which type a particular Kinder Surprise has. All eggs look identical and indistinguishable from each other.

What is the minimum number of Kinder Surprise Eggs you have to buy to be sure that, whichever types they are, you'll obtain at least one sticker and at least one toy?

Note that you do not open the eggs in the purchasing process, that is, you just buy some number of eggs. It's guaranteed that the answer always exists.

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

Next $$$T$$$ lines contain three integers $$$n$$$, $$$s$$$ and $$$t$$$ each ($$$1 \le n \le 10^9$$$, $$$1 \le s, t \le n$$$, $$$s + t \ge n$$$) — the number of eggs, stickers and toys.

All queries are independent.

## Output Format
Print $$$T$$$ integers (one number per query) — the minimum number of Kinder Surprise Eggs you have to buy to be sure that, whichever types they are, you'll obtain at least one sticker and one toy

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

## Note
In the first query, we have to take at least $$$6$$$ eggs because there are $$$5$$$ eggs with only toy inside and, in the worst case, we'll buy all of them.

In the second query, all eggs have both a sticker and a toy inside, that's why it's enough to buy only one egg.

In the third query, we have to buy both eggs: one with a sticker and one with a toy.

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 letters shop showcase is a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters. As the name tells, letters are sold in the shop.

Letters are sold one by one from the leftmost to the rightmost. Any customer can only buy some prefix of letters from the string $$$s$$$.

There are $$$m$$$ friends, the $$$i$$$-th of them is named $$$t_i$$$. Each of them is planning to estimate the following value: how many letters (the length of the shortest prefix) would s/he need to buy if s/he wanted to construct her/his name of bought letters. The name can be constructed if each letter is presented in the equal or greater amount.

- For example, for $$$s$$$="arrayhead" and $$$t_i$$$="arya" $$$5$$$ letters have to be bought ("arrayhead").
- For example, for $$$s$$$="arrayhead" and $$$t_i$$$="harry" $$$6$$$ letters have to be bought ("arrayhead").
- For example, for $$$s$$$="arrayhead" and $$$t_i$$$="ray" $$$5$$$ letters have to be bought ("arrayhead").
- For example, for $$$s$$$="arrayhead" and $$$t_i$$$="r" $$$2$$$ letters have to be bought ("arrayhead").
- For example, for $$$s$$$="arrayhead" and $$$t_i$$$="areahydra" all $$$9$$$ letters have to be bought ("arrayhead").

It is guaranteed that every friend can construct her/his name using the letters from the string $$$s$$$.

Note that the values for friends are independent, friends are only estimating them but not actually buying the letters.

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

The second line contains string $$$s$$$, consisting of exactly $$$n$$$ lowercase Latin letters.

The third line contains one integer $$$m$$$ ($$$1 \le m \le 5 \cdot 10^4$$$) — the number of friends.

The $$$i$$$-th of the next $$$m$$$ lines contains $$$t_i$$$ ($$$1 \le |t_i| \le 2 \cdot 10^5$$$) — the name of the $$$i$$$-th friend.

It is guaranteed that $$$\sum \limits_{i=1}^m |t_i| \le 2 \cdot 10^5$$$.

## Output Format
For each friend print the length of the shortest prefix of letters from $$$s$$$ s/he would need to buy to be able to construct her/his name of them. The name can be constructed if each letter is presented in the equal or greater amount.

It is guaranteed that every friend can construct her/his name using the letters from the string $$$s$$$.

## Examples
```input
9
arrayhead
5
arya
harry
ray
r
areahydra
```
```output
5
6
5
2
9
```

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
Vasya has an array $$$a_1, a_2, \dots, a_n$$$.

You don't know this array, but he told you $$$m$$$ facts about this array. The $$$i$$$-th fact is a triple of numbers $$$t_i$$$, $$$l_i$$$ and $$$r_i$$$ ($$$0 \le t_i \le 1, 1 \le l_i < r_i \le n$$$) and it means:

- if $$$t_i=1$$$ then subbarray $$$a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$$$ is sorted in non-decreasing order;
- if $$$t_i=0$$$ then subbarray $$$a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$$$ is not sorted in non-decreasing order. A subarray is not sorted if there is at least one pair of consecutive elements in this subarray such that the former is greater than the latter.

For example if $$$a = [2, 1, 1, 3, 2]$$$ then he could give you three facts: $$$t_1=1, l_1=2, r_1=4$$$ (the subarray $$$[a_2, a_3, a_4] = [1, 1, 3]$$$ is sorted), $$$t_2=0, l_2=4, r_2=5$$$ (the subarray $$$[a_4, a_5] = [3, 2]$$$ is not sorted), and $$$t_3=0, l_3=3, r_3=5$$$ (the subarray $$$[a_3, a_5] = [1, 3, 2]$$$ is not sorted).

You don't know the array $$$a$$$. Find any array which satisfies all the given facts.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 1000, 1 \le m \le 1000$$$).

Each of the next $$$m$$$ lines contains three integers $$$t_i$$$, $$$l_i$$$ and $$$r_i$$$ ($$$0 \le t_i \le 1, 1 \le l_i < r_i \le n$$$).

If $$$t_i = 1$$$ then subbarray $$$a_{l_i}, a_{l_i + 1}, \dots , a_{r_i}$$$ is sorted. Otherwise (if $$$t_i = 0$$$) subbarray $$$a_{l_i}, a_{l_i + 1}, \dots , a_{r_i}$$$ is not sorted.

## Output Format
If there is no array that satisfies these facts in only line print NO (in any letter case).

If there is a solution, print YES (in any letter case). In second line print $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$, satisfying all the given facts. If there are multiple satisfying arrays you can print any of them.

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

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 an array $$$a_1, a_2, \dots, a_n$$$ and an array $$$b_1, b_2, \dots, b_n$$$.

For one operation you can sort in non-decreasing order any subarray $$$a[l \dots r]$$$ of the array $$$a$$$.

For example, if $$$a = [4, 2, 2, 1, 3, 1]$$$ and you choose subbarray $$$a[2 \dots 5]$$$, then the array turns into $$$[4, 1, 2, 2, 3, 1]$$$.

You are asked to determine whether it is possible to obtain the array $$$b$$$ by applying this operation any number of times (possibly zero) to the array $$$a$$$.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^5$$$) — the number of queries.

The first line of each query contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

The second line of each query contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

The third line of each query contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$).

It is guaranteed that $$$\sum n \le 3 \cdot 10^5$$$ over all queries in a test.

## Output Format
For each query print YES (in any letter case) if it is possible to obtain an array $$$b$$$ and NO (in any letter case) otherwise.

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

## Note
In first test case the can sort subarray $$$a_1 \dots a_5$$$, then $$$a$$$ will turn into $$$[1, 1, 4, 4, 7, 5, 6]$$$, and then sort subarray $$$a_5 \dots a_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 tree (an undirected connected acyclic graph) consisting of $$$n$$$ vertices. You are playing a game on this tree.

Initially all vertices are white. On the first turn of the game you choose one vertex and paint it black. Then on each turn you choose a white vertex adjacent (connected by an edge) to any black vertex and paint it black.

Each time when you choose a vertex (even during the first turn), you gain the number of points equal to the size of the connected component consisting only of white vertices that contains the chosen vertex. The game ends when all vertices are painted black.

Let's see the following example:

Vertices $$$1$$$ and $$$4$$$ are painted black already. If you choose the vertex $$$2$$$, you will gain $$$4$$$ points for the connected component consisting of vertices $$$2, 3, 5$$$ and $$$6$$$. If you choose the vertex $$$9$$$, you will gain $$$3$$$ points for the connected component consisting of vertices $$$7, 8$$$ and $$$9$$$.

Your task is to maximize the number of points you gain.

## Input Format
The first line contains an integer $$$n$$$ — the number of vertices in the tree ($$$2 \le n \le 2 \cdot 10^5$$$).

Each of the next $$$n - 1$$$ lines describes an edge of the tree. Edge $$$i$$$ is denoted by two integers $$$u_i$$$ and $$$v_i$$$, the indices of vertices it connects ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$).

It is guaranteed that the given edges form a tree.

## Output Format
Print one integer — the maximum number of points you gain if you will play optimally.

## Examples
```input
9
1 2
2 3
2 5
2 6
1 4
4 9
9 7
9 8
```
```output
36
```
-----
```input
5
1 2
1 3
2 4
2 5
```
```output
14
```

## Note
The first example tree is shown in the problem statement.

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
Let $$$x$$$ be an array of integers $$$x = [x_1, x_2, \dots, x_n]$$$. Let's define $$$B(x)$$$ as a minimal size of a partition of $$$x$$$ into subsegments such that all elements in each subsegment are equal. For example, $$$B([3, 3, 6, 1, 6, 6, 6]) = 4$$$ using next partition: $$$[3, 3\ |\ 6\ |\ 1\ |\ 6, 6, 6]$$$.

Now you don't have any exact values of $$$x$$$, but you know that $$$x_i$$$ can be any integer value from $$$[l_i, r_i]$$$ ($$$l_i \le r_i$$$) uniformly at random. All $$$x_i$$$ are independent.

Calculate expected value of $$$(B(x))^2$$$, or $$$E((B(x))^2)$$$. It's guaranteed that the expected value can be represented as rational fraction $$$\frac{P}{Q}$$$ where $$$(P, Q) = 1$$$, so print the value $$$P \cdot Q^{-1} \mod 10^9 + 7$$$.

## Input Format
The first line contains the single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the array $$$x$$$.

The second line contains $$$n$$$ integers $$$l_1, l_2, \dots, l_n$$$ ($$$1 \le l_i \le 10^9$$$).

The third line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$l_i \le r_i \le 10^9$$$).

## Output Format
Print the single integer — $$$E((B(x))^2)$$$ as $$$P \cdot Q^{-1} \mod 10^9 + 7$$$.

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

## Note
Let's describe all possible values of $$$x$$$ for the first sample:

- $$$[1, 1, 1]$$$: $$$B(x) = 1$$$, $$$B^2(x) = 1$$$;
- $$$[1, 1, 2]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 1, 3]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 2, 1]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[1, 2, 2]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 2, 3]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;

All possible values of $$$x$$$ for the second sample:

- $$$[3, 4, 5]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[3, 4, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[3, 5, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[3, 5, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[4, 4, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 4, 6]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 5, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 5, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;

Now solve the problem and return the code.