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
The only difference between easy and hard versions is the length of the string. You can hack this problem if you solve it. But you can hack the previous problem only if you solve both problems.

Kirk has a binary string $$$s$$$ (a string which consists of zeroes and ones) of length $$$n$$$ and he is asking you to find a binary string $$$t$$$ of the same length which satisfies the following conditions:

- For any $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) the length of the longest non-decreasing subsequence of the substring $$$s_{l}s_{l+1} \ldots s_{r}$$$ is equal to the length of the longest non-decreasing subsequence of the substring $$$t_{l}t_{l+1} \ldots t_{r}$$$;
- The number of zeroes in $$$t$$$ is the maximum possible.

A non-decreasing subsequence of a string $$$p$$$ is a sequence of indices $$$i_1, i_2, \ldots, i_k$$$ such that $$$i_1 < i_2 < \ldots < i_k$$$ and $$$p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}$$$. The length of the subsequence is $$$k$$$.

If there are multiple substrings which satisfy the conditions, output any.

## Input Format
The first line contains a binary string of length not more than $$$10^5$$$.

## Output Format
Output a binary string which satisfied the above conditions. If there are many such strings, output any of them.

## Examples
```input
110
```
```output
010
```
-----
```input
010
```
```output
010
```
-----
```input
0001111
```
```output
0000000
```
-----
```input
0111001100111011101000
```
```output
0011001100001011101000
```

## Note
In the first example:

- For the substrings of the length $$$1$$$ the length of the longest non-decreasing subsequnce is $$$1$$$;
- For $$$l = 1, r = 2$$$ the longest non-decreasing subsequnce of the substring $$$s_{1}s_{2}$$$ is $$$11$$$ and the longest non-decreasing subsequnce of the substring $$$t_{1}t_{2}$$$ is $$$01$$$;
- For $$$l = 1, r = 3$$$ the longest non-decreasing subsequnce of the substring $$$s_{1}s_{3}$$$ is $$$11$$$ and the longest non-decreasing subsequnce of the substring $$$t_{1}t_{3}$$$ is $$$00$$$;
- For $$$l = 2, r = 3$$$ the longest non-decreasing subsequnce of the substring $$$s_{2}s_{3}$$$ is $$$1$$$ and the longest non-decreasing subsequnce of the substring $$$t_{2}t_{3}$$$ is $$$1$$$;

The second example is similar to the first one.

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
Natasha's favourite numbers are $$$n$$$ and $$$1$$$, and Sasha's favourite numbers are $$$m$$$ and $$$-1$$$. One day Natasha and Sasha met and wrote down every possible array of length $$$n+m$$$ such that some $$$n$$$ of its elements are equal to $$$1$$$ and another $$$m$$$ elements are equal to $$$-1$$$. For each such array they counted its maximal prefix sum, probably an empty one which is equal to $$$0$$$ (in another words, if every nonempty prefix sum is less to zero, then it is considered equal to zero). Formally, denote as $$$f(a)$$$ the maximal prefix sum of an array $$$a_{1, \ldots ,l}$$$ of length $$$l \geq 0$$$. Then:

$$$$$$f(a) = \max (0, \smash{\displaystyle\max_{1 \leq i \leq l}} \sum_{j=1}^{i} a_j )$$$$$$

Now they want to count the sum of maximal prefix sums for each such an array and they are asking you to help. As this sum can be very large, output it modulo $$$998\: 244\: 853$$$.

## Input Format
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$0 \le n,m \le 2\,000$$$).

## Output Format
Output the answer to the problem modulo $$$998\: 244\: 853$$$.

## Examples
```input
0 2
```
```output
0
```
-----
```input
2 0
```
```output
2
```
-----
```input
2 2
```
```output
5
```
-----
```input
2000 2000
```
```output
674532367
```

## Note
In the first example the only possible array is [-1,-1], its maximal prefix sum is equal to $$$0$$$.

In the second example the only possible array is [1,1], its maximal prefix sum is equal to $$$2$$$.

There are $$$6$$$ possible arrays in the third example:

[1,1,-1,-1], f([1,1,-1,-1]) = 2

[1,-1,1,-1], f([1,-1,1,-1]) = 1

[1,-1,-1,1], f([1,-1,-1,1]) = 1

[-1,1,1,-1], f([-1,1,1,-1]) = 1

[-1,1,-1,1], f([-1,1,-1,1]) = 0

[-1,-1,1,1], f([-1,-1,1,1]) = 0

So the answer for the third example is $$$2+1+1+1+0+0 = 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 python3.

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:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya has n number segments [l1; r1], [l2; r2], ..., [ln; rn]. During one move Petya can take any segment (let it be segment number i) and replace it with segment [li + 1; ri + 1] or [li - 1; ri - 1]. In other words, during one move Petya can shift any segment to the left or to the right by a unit distance. Petya calls a number full if it belongs to each segment. That is, number x is full if for any i (1 ≤ i ≤ n) the condition li ≤ x ≤ ri is fulfilled.

Petya makes no more than k moves. After that he counts the quantity of full lucky numbers. Find the maximal quantity that he can get.

## Input Format
The first line contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 1018) — the number of segments and the maximum number of moves. Next n lines contain pairs of integers li and ri (1 ≤ li ≤ ri ≤ 1018).

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the %I64d specificator.

## Output Format
Print on the single line the single number — the answer to the problem.

## Examples
```input
4 7
1 4
6 9
4 7
3 5
```
```output
1
```
-----
```input
2 7
40 45
47 74
```
```output
2
```

## Note
In the first sample Petya shifts the second segment by two units to the left (it turns into [4; 7]), after that number 4 becomes full.

In the second sample Petya shifts the first segment by two units to the right (it turns into [42; 47]), and shifts the second segment by three units to the left (it turns into [44; 71]), after that numbers 44 and 47 become full.

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 the gym teacher in the school.

There are $$$n$$$ students in the row. And there are two rivalling students among them. The first one is in position $$$a$$$, the second in position $$$b$$$. Positions are numbered from $$$1$$$ to $$$n$$$ from left to right.

Since they are rivals, you want to maximize the distance between them. If students are in positions $$$p$$$ and $$$s$$$ respectively, then distance between them is $$$|p - s|$$$.

You can do the following operation at most $$$x$$$ times: choose two adjacent (neighbouring) students and swap them.

Calculate the maximum distance between two rivalling students after at most $$$x$$$ swaps.

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

The only line of each test case contains four integers $$$n$$$, $$$x$$$, $$$a$$$ and $$$b$$$ ($$$2 \le n \le 100$$$, $$$0 \le x \le 100$$$, $$$1 \le a, b \le n$$$, $$$a \neq b$$$) — the number of students in the row, the number of swaps which you can do, and positions of first and second rivaling students respectively.

## Output Format
For each test case print one integer — the maximum distance between two rivaling students which you can obtain.

## Examples
```input
3
5 1 3 2
100 33 100 1
6 0 2 3
```
```output
2
99
1
```

## Note
In the first test case you can swap students in positions $$$3$$$ and $$$4$$$. And then the distance between the rivals is equal to $$$|4 - 2| = 2$$$.

In the second test case you don't have to swap students.

In the third test case you can't swap students.

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
Recently Petya walked in the forest and found a magic stick.

Since Petya really likes numbers, the first thing he learned was spells for changing numbers. So far, he knows only two spells that can be applied to a positive integer:

1. If the chosen number $$$a$$$ is even, then the spell will turn it into $$$\frac{3a}{2}$$$;
2. If the chosen number $$$a$$$ is greater than one, then the spell will turn it into $$$a-1$$$.

Note that if the number is even and greater than one, then Petya can choose which spell to apply.

Petya now has only one number $$$x$$$. He wants to know if his favorite number $$$y$$$ can be obtained from $$$x$$$ using the spells he knows. The spells can be used any number of times in any order. It is not required to use spells, Petya can leave $$$x$$$ as it is.

## Input Format
The first line contains single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases. Each test case consists of two lines.

The first line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le 10^9$$$) — the current number and the number that Petya wants to get.

## Output Format
For the $$$i$$$-th test case print the answer on it — YES if Petya can get the number $$$y$$$ from the number $$$x$$$ using known spells, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

## Examples
```input
7
2 3
1 1
3 6
6 8
1 2
4 1
31235 6578234
```
```output
YES
YES
NO
YES
NO
YES
YES
```

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's call an array $$$t$$$ dominated by value $$$v$$$ in the next situation.

At first, array $$$t$$$ should have at least $$$2$$$ elements. Now, let's calculate number of occurrences of each number $$$num$$$ in $$$t$$$ and define it as $$$occ(num)$$$. Then $$$t$$$ is dominated (by $$$v$$$) if (and only if) $$$occ(v) > occ(v')$$$ for any other number $$$v'$$$. For example, arrays $$$[1, 2, 3, 4, 5, 2]$$$, $$$[11, 11]$$$ and $$$[3, 2, 3, 2, 3]$$$ are dominated (by $$$2$$$, $$$11$$$ and $$$3$$$ respectevitely) but arrays $$$[3]$$$, $$$[1, 2]$$$ and $$$[3, 3, 2, 2, 1]$$$ are not.

Small remark: since any array can be dominated only by one number, we can not specify this number and just say that array is either dominated or not.

You are given array $$$a_1, a_2, \dots, a_n$$$. Calculate its shortest dominated subarray or say that there are no such subarrays.

The subarray of $$$a$$$ is a contiguous part of the array $$$a$$$, i. e. the array $$$a_i, a_{i + 1}, \dots, a_j$$$ for some $$$1 \le i \le j \le n$$$.

## Input Format
The first line contains single integer $$$T$$$ ($$$1 \le T \le 1000$$$) — the number of test cases. Each test case consists of two lines.

The first line contains single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the corresponding values of the array $$$a$$$.

It's guaranteed that the total length of all arrays in one test doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
Print $$$T$$$ integers — one per test case. For each test case print the only integer — the length of the shortest dominated subarray, or $$$-1$$$ if there are no such subarrays.

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

## Note
In the first test case, there are no subarrays of length at least $$$2$$$, so the answer is $$$-1$$$.

In the second test case, the whole array is dominated (by $$$1$$$) and it's the only dominated subarray.

In the third test case, the subarray $$$a_4, a_5, a_6$$$ is the shortest dominated subarray.

In the fourth test case, all subarrays of length more than one are dominated.

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
Let's call two numbers similar if their binary representations contain the same number of digits equal to $$$1$$$. For example:

- $$$2$$$ and $$$4$$$ are similar (binary representations are $$$10$$$ and $$$100$$$);
- $$$1337$$$ and $$$4213$$$ are similar (binary representations are $$$10100111001$$$ and $$$1000001110101$$$);
- $$$3$$$ and $$$2$$$ are not similar (binary representations are $$$11$$$ and $$$10$$$);
- $$$42$$$ and $$$13$$$ are similar (binary representations are $$$101010$$$ and $$$1101$$$).

You are given an array of $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$. You may choose a non-negative integer $$$x$$$, and then get another array of $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$, where $$$b_i = a_i \oplus x$$$ ($$$\oplus$$$ denotes bitwise XOR).

Is it possible to obtain an array $$$b$$$ where all numbers are similar to each other?

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

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 2^{30} - 1$$$).

## Output Format
If it is impossible to choose $$$x$$$ so that all elements in the resulting array are similar to each other, print one integer $$$-1$$$.

Otherwise, print any non-negative integer not exceeding $$$2^{30} - 1$$$ that can be used as $$$x$$$ so that all elements in the resulting array are similar.

## Examples
```input
2
7 2
```
```output
1
```
-----
```input
4
3 17 6 0
```
```output
5
```
-----
```input
3
1 2 3
```
```output
-1
```
-----
```input
3
43 12 12
```
```output
1073709057
```

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

# Problem
You are given an integer $$$x$$$ represented as a product of $$$n$$$ its prime divisors $$$p_1 \cdot p_2, \cdot \ldots \cdot p_n$$$. Let $$$S$$$ be the set of all positive integer divisors of $$$x$$$ (including $$$1$$$ and $$$x$$$ itself).

We call a set of integers $$$D$$$ good if (and only if) there is no pair $$$a \in D$$$, $$$b \in D$$$ such that $$$a \ne b$$$ and $$$a$$$ divides $$$b$$$.

Find a good subset of $$$S$$$ with maximum possible size. Since the answer can be large, print the size of the subset modulo $$$998244353$$$.

## Input Format
The first line contains the single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of prime divisors in representation of $$$x$$$.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$2 \le p_i \le 3 \cdot 10^6$$$) — the prime factorization of $$$x$$$.

## Output Format
Print the maximum possible size of a good subset modulo $$$998244353$$$.

## Examples
```input
3
2999999 43 2999957
```
```output
3
```
-----
```input
6
2 3 2 3 2 2
```
```output
3
```

## Note
In the first sample, $$$x = 2999999 \cdot 43 \cdot 2999957$$$ and one of the maximum good subsets is $$$\{ 43, 2999957, 2999999 \}$$$.

In the second sample, $$$x = 2 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 2 = 144$$$ and one of the maximum good subsets is $$$\{ 9, 12, 16 \}$$$.

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 is a competitive programmer. He wants to become red, and for that he needs a strict training regime. He went to the annual meeting of grandmasters and asked $$$n$$$ of them how much effort they needed to reach red.

"Oh, I just spent $$$x_i$$$ hours solving problems", said the $$$i$$$-th of them.

Bob wants to train his math skills, so for each answer he wrote down the number of minutes ($$$60 \cdot x_i$$$), thanked the grandmasters and went home. Bob could write numbers with leading zeroes — for example, if some grandmaster answered that he had spent $$$2$$$ hours, Bob could write $$$000120$$$ instead of $$$120$$$.

Alice wanted to tease Bob and so she took the numbers Bob wrote down, and for each of them she did one of the following independently:

- rearranged its digits, or
- wrote a random number.

This way, Alice generated $$$n$$$ numbers, denoted $$$y_1$$$, ..., $$$y_n$$$.

For each of the numbers, help Bob determine whether $$$y_i$$$ can be a permutation of a number divisible by $$$60$$$ (possibly with leading zeroes).

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 418$$$) — the number of grandmasters Bob asked.

Then $$$n$$$ lines follow, the $$$i$$$-th of which contains a single integer $$$y_i$$$ — the number that Alice wrote down.

Each of these numbers has between $$$2$$$ and $$$100$$$ digits '0' through '9'. They can contain leading zeroes.

## Output Format
Output $$$n$$$ lines.

For each $$$i$$$, output the following. If it is possible to rearrange the digits of $$$y_i$$$ such that the resulting number is divisible by $$$60$$$, output "red" (quotes for clarity). Otherwise, output "cyan".

## Examples
```input
6
603
006
205
228
1053
0000000000000000000000000000000000000000000000
```
```output
red
red
cyan
cyan
cyan
red
```

## Note
In the first example, there is one rearrangement that yields a number divisible by $$$60$$$, and that is $$$360$$$.

In the second example, there are two solutions. One is $$$060$$$ and the second is $$$600$$$.

In the third example, there are $$$6$$$ possible rearrangments: $$$025$$$, $$$052$$$, $$$205$$$, $$$250$$$, $$$502$$$, $$$520$$$. None of these numbers is divisible by $$$60$$$.

In the fourth example, there are $$$3$$$ rearrangements: $$$228$$$, $$$282$$$, $$$822$$$.

In the fifth example, none of the $$$24$$$ rearrangements result in a number divisible by $$$60$$$.

In the sixth example, note that $$$000\dots0$$$ is a valid solution.

Now solve the problem and return the code.