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
You are given two binary strings $$$a$$$ and $$$b$$$ of the same length. You can perform the following two operations on the string $$$a$$$:

- Swap any two bits at indices $$$i$$$ and $$$j$$$ respectively ($$$1 \le i, j \le n$$$), the cost of this operation is $$$|i - j|$$$, that is, the absolute difference between $$$i$$$ and $$$j$$$.
- Select any arbitrary index $$$i$$$ ($$$1 \le i \le n$$$) and flip (change $$$0$$$ to $$$1$$$ or $$$1$$$ to $$$0$$$) the bit at this index. The cost of this operation is $$$1$$$.

Find the minimum cost to make the string $$$a$$$ equal to $$$b$$$. It is not allowed to modify string $$$b$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the strings $$$a$$$ and $$$b$$$.

The second and third lines contain strings $$$a$$$ and $$$b$$$ respectively.

Both strings $$$a$$$ and $$$b$$$ have length $$$n$$$ and contain only '0' and '1'.

## Output Format
Output the minimum cost to make the string $$$a$$$ equal to $$$b$$$.

## Examples
```input
3
100
001
```
```output
2
```
-----
```input
4
0101
0011
```
```output
1
```

## Note
In the first example, one of the optimal solutions is to flip index $$$1$$$ and index $$$3$$$, the string $$$a$$$ changes in the following way: "100" $$$\to$$$ "000" $$$\to$$$ "001". The cost is $$$1 + 1 = 2$$$.

The other optimal solution is to swap bits and indices $$$1$$$ and $$$3$$$, the string $$$a$$$ changes then "100" $$$\to$$$ "001", the cost is also $$$|1 - 3| = 2$$$.

In the second example, the optimal solution is to swap bits at indices $$$2$$$ and $$$3$$$, the string $$$a$$$ changes as "0101" $$$\to$$$ "0011". The cost is $$$|2 - 3| = 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
You are given a set of all integers from $$$l$$$ to $$$r$$$ inclusive, $$$l < r$$$, $$$(r - l + 1) \le 3 \cdot 10^5$$$ and $$$(r - l)$$$ is always odd.

You want to split these numbers into exactly $$$\frac{r - l + 1}{2}$$$ pairs in such a way that for each pair $$$(i, j)$$$ the greatest common divisor of $$$i$$$ and $$$j$$$ is equal to $$$1$$$. Each number should appear in exactly one of the pairs.

Print the resulting pairs or output that no solution exists. If there are multiple solutions, print any of them.

## Input Format
The only line contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le 10^{18}$$$, $$$r - l + 1 \le 3 \cdot 10^5$$$, $$$(r - l)$$$ is odd).

## Output Format
If any solution exists, print "YES" in the first line. Each of the next $$$\frac{r - l + 1}{2}$$$ lines should contain some pair of integers. GCD of numbers in each pair should be equal to $$$1$$$. All $$$(r - l + 1)$$$ numbers should be pairwise distinct and should have values from $$$l$$$ to $$$r$$$ inclusive.

If there are multiple solutions, print any of them.

If there exists no solution, print "NO".

## Examples
```input
1 8
```
```output
YES
2 7
4 1
3 8
6 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 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 a multiset $$$s$$$ consisting of $$$n$$$ integer numbers. Vasya calls some number $$$x$$$ nice if it appears in the multiset exactly once. For example, multiset $$$\{1, 1, 2, 3, 3, 3, 4\}$$$ contains nice numbers $$$2$$$ and $$$4$$$.

Vasya wants to split multiset $$$s$$$ into two multisets $$$a$$$ and $$$b$$$ (one of which may be empty) in such a way that the quantity of nice numbers in multiset $$$a$$$ would be the same as the quantity of nice numbers in multiset $$$b$$$ (the quantity of numbers to appear exactly once in multiset $$$a$$$ and the quantity of numbers to appear exactly once in multiset $$$b$$$).

## Input Format
The first line contains a single integer $$$n~(2 \le n \le 100)$$$.

The second line contains $$$n$$$ integers $$$s_1, s_2, \dots s_n~(1 \le s_i \le 100)$$$ — the multiset $$$s$$$.

## Output Format
If there exists no split of $$$s$$$ to satisfy the given requirements, then print "NO" in the first line.

Otherwise print "YES" in the first line.

The second line should contain a string, consisting of $$$n$$$ characters. $$$i$$$-th character should be equal to 'A' if the $$$i$$$-th element of multiset $$$s$$$ goes to multiset $$$a$$$ and 'B' if if the $$$i$$$-th element of multiset $$$s$$$ goes to multiset $$$b$$$. Elements are numbered from $$$1$$$ to $$$n$$$ in the order they are given in the input.

If there exist multiple solutions, then print any of them.

## Examples
```input
4
3 5 7 1
```
```output
YES
BABA
```
-----
```input
3
3 5 1
```
```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 a grid, consisting of $$$2$$$ rows and $$$n$$$ columns. Each cell of this grid should be colored either black or white.

Two cells are considered neighbours if they have a common border and share the same color. Two cells $$$A$$$ and $$$B$$$ belong to the same component if they are neighbours, or if there is a neighbour of $$$A$$$ that belongs to the same component with $$$B$$$.

Let's call some bicoloring beautiful if it has exactly $$$k$$$ components.

Count the number of beautiful bicolorings. The number can be big enough, so print the answer modulo $$$998244353$$$.

## Input Format
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 1000$$$, $$$1 \le k \le 2n$$$) — the number of columns in a grid and the number of components required.

## Output Format
Print a single integer — the number of beautiful bicolorings modulo $$$998244353$$$.

## Examples
```input
3 4
```
```output
12
```
-----
```input
4 1
```
```output
2
```
-----
```input
1 2
```
```output
2
```

## Note
One of possible bicolorings in sample $$$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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya owns three big integers — $$$a, l, r$$$. Let's define a partition of $$$x$$$ such a sequence of strings $$$s_1, s_2, \dots, s_k$$$ that $$$s_1 + s_2 + \dots + s_k = x$$$, where $$$+$$$ is a concatanation of strings. $$$s_i$$$ is the $$$i$$$-th element of the partition. For example, number $$$12345$$$ has the following partitions: ["1", "2", "3", "4", "5"], ["123", "4", "5"], ["1", "2345"], ["12345"] and lots of others.

Let's call some partition of $$$a$$$ beautiful if each of its elements contains no leading zeros.

Vasya want to know the number of beautiful partitions of number $$$a$$$, which has each of $$$s_i$$$ satisfy the condition $$$l \le s_i \le r$$$. Note that the comparison is the integer comparison, not the string one.

Help Vasya to count the amount of partitions of number $$$a$$$ such that they match all the given requirements. The result can be rather big, so print it modulo $$$998244353$$$.

## Input Format
The first line contains a single integer $$$a~(1 \le a \le 10^{1000000})$$$.

The second line contains a single integer $$$l~(0 \le l \le 10^{1000000})$$$.

The third line contains a single integer $$$r~(0 \le r \le 10^{1000000})$$$.

It is guaranteed that $$$l \le r$$$.

It is also guaranteed that numbers $$$a, l, r$$$ contain no leading zeros.

## Output Format
Print a single integer — the amount of partitions of number $$$a$$$ such that they match all the given requirements modulo $$$998244353$$$.

## Examples
```input
135
1
15
```
```output
2
```
-----
```input
10000
0
9
```
```output
1
```

## Note
In the first test case, there are two good partitions $$$13+5$$$ and $$$1+3+5$$$.

In the second test case, there is one good partition $$$1+0+0+0+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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Bob and Alice are often participating in various programming competitions. Like many competitive programmers, Alice and Bob have good and bad days. They noticed, that their lucky and unlucky days are repeating with some period. For example, for Alice days $$$[l_a; r_a]$$$ are lucky, then there are some unlucky days: $$$[r_a + 1; l_a + t_a - 1]$$$, and then there are lucky days again: $$$[l_a + t_a; r_a + t_a]$$$ and so on. In other words, the day is lucky for Alice if it lies in the segment $$$[l_a + k t_a; r_a + k t_a]$$$ for some non-negative integer $$$k$$$.

The Bob's lucky day have similar structure, however the parameters of his sequence are different: $$$l_b$$$, $$$r_b$$$, $$$t_b$$$. So a day is a lucky for Bob if it lies in a segment $$$[l_b + k t_b; r_b + k t_b]$$$, for some non-negative integer $$$k$$$.

Alice and Bob want to participate in team competitions together and so they want to find out what is the largest possible number of consecutive days, which are lucky for both Alice and Bob.

## Input Format
The first line contains three integers $$$l_a$$$, $$$r_a$$$, $$$t_a$$$ ($$$0 \le l_a \le r_a \le t_a - 1, 2 \le t_a \le 10^9$$$) and describes Alice's lucky days.

The second line contains three integers $$$l_b$$$, $$$r_b$$$, $$$t_b$$$ ($$$0 \le l_b \le r_b \le t_b - 1, 2 \le t_b \le 10^9$$$) and describes Bob's lucky days.

It is guaranteed that both Alice and Bob have some unlucky days.

## Output Format
Print one integer: the maximum number of days in the row that are lucky for both Alice and Bob.

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

## Note
The graphs below correspond to the two sample tests and show the lucky and unlucky days of Alice and Bob as well as the possible solutions for these tests.

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 a given a list of integers $$$a_1, a_2, \ldots, a_n$$$ and $$$s$$$ of its segments $$$[l_j; r_j]$$$ (where $$$1 \le l_j \le r_j \le n$$$).

You need to select exactly $$$m$$$ segments in such a way that the $$$k$$$-th order statistic of the multiset of $$$a_i$$$, where $$$i$$$ is contained in at least one segment, is the smallest possible. If it's impossible to select a set of $$$m$$$ segments in such a way that the multiset contains at least $$$k$$$ elements, print -1.

The $$$k$$$-th order statistic of a multiset is the value of the $$$k$$$-th element after sorting the multiset in non-descending order.

## Input Format
The first line contains four integers $$$n$$$, $$$s$$$, $$$m$$$ and $$$k$$$ ($$$1 \le m \le s \le 1500$$$, $$$1 \le k \le n \le 1500$$$) — the size of the list, the number of segments, the number of segments to choose and the statistic number.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the values of the numbers in the list.

Each of the next $$$s$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the endpoints of the segments.

It is possible that some segments coincide.

## Output Format
Print exactly one integer — the smallest possible $$$k$$$-th order statistic, or -1 if it's impossible to choose segments in a way that the multiset contains at least $$$k$$$ elements.

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

## Note
In the first example, one possible solution is to choose the first and the third segment. Together they will cover three elements of the list (all, except for the third one). This way the $$$2$$$-nd order statistic for the covered elements is $$$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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a connected undirected graph without cycles (that is, a tree) of $$$n$$$ vertices, moreover, there is a non-negative integer written on every edge.

Consider all pairs of vertices $$$(v, u)$$$ (that is, there are exactly $$$n^2$$$ such pairs) and for each pair calculate the bitwise exclusive or (xor) of all integers on edges of the simple path between $$$v$$$ and $$$u$$$. If the path consists of one vertex only, then xor of all integers on edges of this path is equal to $$$0$$$.

Suppose we sorted the resulting $$$n^2$$$ values in non-decreasing order. You need to find the $$$k$$$-th of them.

The definition of xor is as follows.

Given two integers $$$x$$$ and $$$y$$$, consider their binary representations (possibly with leading zeros): $$$x_k \dots x_2 x_1 x_0$$$ and $$$y_k \dots y_2 y_1 y_0$$$ (where $$$k$$$ is any number so that all bits of $$$x$$$ and $$$y$$$ can be represented). Here, $$$x_i$$$ is the $$$i$$$-th bit of the number $$$x$$$ and $$$y_i$$$ is the $$$i$$$-th bit of the number $$$y$$$. Let $$$r = x \oplus y$$$ be the result of the xor operation of $$$x$$$ and $$$y$$$. Then $$$r$$$ is defined as $$$r_k \dots r_2 r_1 r_0$$$ where:

$$$$$$ r_i = \left\{ \begin{aligned} 1, ~ \text{if} ~ x_i \ne y_i \\ 0, ~ \text{if} ~ x_i = y_i \end{aligned} \right. $$$$$$

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le k \le n^2$$$) — the number of vertices in the tree and the number of path in the list with non-decreasing order.

Each of the following $$$n - 1$$$ lines contains two integers $$$p_i$$$ and $$$w_i$$$ ($$$1 \le p_i \le i$$$, $$$0 \le w_i < 2^{62}$$$) — the ancestor of vertex $$$i + 1$$$ and the weight of the corresponding edge.

## Output Format
Print one integer: $$$k$$$-th smallest xor of a path in the tree.

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

## Note
The tree in the second sample test looks like this:

For such a tree in total $$$9$$$ paths exist:

1. $$$1 \to 1$$$ of value $$$0$$$
2. $$$2 \to 2$$$ of value $$$0$$$
3. $$$3 \to 3$$$ of value $$$0$$$
4. $$$2 \to 3$$$ (goes through $$$1$$$) of value $$$1 = 2 \oplus 3$$$
5. $$$3 \to 2$$$ (goes through $$$1$$$) of value $$$1 = 2 \oplus 3$$$
6. $$$1 \to 2$$$ of value $$$2$$$
7. $$$2 \to 1$$$ of value $$$2$$$
8. $$$1 \to 3$$$ of value $$$3$$$
9. $$$3 \to 1$$$ of value $$$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
Let's call a string a phone number if it has length 11 and fits the pattern "8xxxxxxxxxx", where each "x" is replaced by a digit.

For example, "80123456789" and "80000000000" are phone numbers, while "8012345678" and "79000000000" are not.

You have $$$n$$$ cards with digits, and you want to use them to make as many phone numbers as possible. Each card must be used in at most one phone number, and you don't have to use all cards. The phone numbers do not necessarily have to be distinct.

## Input Format
The first line contains an integer $$$n$$$ — the number of cards with digits that you have ($$$1 \leq n \leq 100$$$).

The second line contains a string of $$$n$$$ digits (characters "0", "1", ..., "9") $$$s_1, s_2, \ldots, s_n$$$. The string will not contain any other characters, such as leading or trailing spaces.

## Output Format
If at least one phone number can be made from these cards, output the maximum number of phone numbers that can be made. Otherwise, output 0.

## Examples
```input
11
00000000008
```
```output
1
```
-----
```input
22
0011223344556677889988
```
```output
2
```
-----
```input
11
31415926535
```
```output
0
```

## Note
In the first example, one phone number, "8000000000", can be made from these cards.

In the second example, you can make two phone numbers from the cards, for example, "80123456789" and "80123456789".

In the third example you can't make any phone number from the given cards.

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
You are given a positive integer $$$n$$$.

Let $$$S(x)$$$ be sum of digits in base 10 representation of $$$x$$$, for example, $$$S(123) = 1 + 2 + 3 = 6$$$, $$$S(0) = 0$$$.

Your task is to find two integers $$$a, b$$$, such that $$$0 \leq a, b \leq n$$$, $$$a + b = n$$$ and $$$S(a) + S(b)$$$ is the largest possible among all such pairs.

## Input Format
The only line of input contains an integer $$$n$$$ $$$(1 \leq n \leq 10^{12})$$$.

## Output Format
Print largest $$$S(a) + S(b)$$$ among all pairs of integers $$$a, b$$$, such that $$$0 \leq a, b \leq n$$$ and $$$a + b = n$$$.

## Examples
```input
35
```
```output
17
```
-----
```input
10000000000
```
```output
91
```

## Note
In the first example, you can choose, for example, $$$a = 17$$$ and $$$b = 18$$$, so that $$$S(17) + S(18) = 1 + 7 + 1 + 8 = 17$$$. It can be shown that it is impossible to get a larger answer.

In the second test example, you can choose, for example, $$$a = 5000000001$$$ and $$$b = 4999999999$$$, with $$$S(5000000001) + S(4999999999) = 91$$$. It can be shown that it is impossible to get a larger answer.

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
You are given two arrays $$$a$$$ and $$$b$$$ of positive integers, with length $$$n$$$ and $$$m$$$ respectively.

Let $$$c$$$ be an $$$n \times m$$$ matrix, where $$$c_{i,j} = a_i \cdot b_j$$$.

You need to find a subrectangle of the matrix $$$c$$$ such that the sum of its elements is at most $$$x$$$, and its area (the total number of elements) is the largest possible.

Formally, you need to find the largest number $$$s$$$ such that it is possible to choose integers $$$x_1, x_2, y_1, y_2$$$ subject to $$$1 \leq x_1 \leq x_2 \leq n$$$, $$$1 \leq y_1 \leq y_2 \leq m$$$, $$$(x_2 - x_1 + 1) \times (y_2 - y_1 + 1) = s$$$, and $$$$$$\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x.$$$$$$

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2000$$$).

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 2000$$$).

The fourth line contains a single integer $$$x$$$ ($$$1 \leq x \leq 2 \cdot 10^{9}$$$).

## Output Format
If it is possible to choose four integers $$$x_1, x_2, y_1, y_2$$$ such that $$$1 \leq x_1 \leq x_2 \leq n$$$, $$$1 \leq y_1 \leq y_2 \leq m$$$, and $$$\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x$$$, output the largest value of $$$(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$$$ among all such quadruplets, otherwise output $$$0$$$.

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

## Note
Matrix from the first sample and the chosen subrectangle (of blue color):

Matrix from the second sample and the chosen subrectangle (of blue color):

Now solve the problem and return the code.