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 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: 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 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: 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: 8.0 seconds
Memory limit: 128.0 MB

# Problem
While roaming the mystic areas of Stonefalls, in order to drop legendary loot, an adventurer was given a quest as follows. He was given an array $$$A = {a_1,a_2,...,a_N }$$$ of length $$$N$$$, and a number $$$K$$$.

Define array $$$B$$$ as $$$B(q, A) = $$$ { $$$q-a_1, q-a_2, ..., q-a_N$$$ }. Define function $$$F$$$ as $$$F(B,K)$$$ being sum of products of all $$$K$$$-tuples of elements in array $$$B$$$. For example, if the array $$$B$$$ is $$$[2,3,4,5]$$$, and with $$$K=3$$$, sum of products of all 3-tuples is $$$$$$F(B, 3) = 2*3*4+2*3*5+3*4*5+2*4*5$$$$$$

He was then given a number Q, number of queries of two types:

- Type 1: Given $$$q$$$, $$$i$$$, and $$$d$$$ calculate $$$F(B(q, A), K)$$$ where we make change to initial array as $$$A[i] = d$$$.
- Type 2: Given $$$q$$$, $$$L$$$, $$$R$$$, and $$$d$$$ calculate $$$F(B(q, A), K)$$$ where we make change to initial array as $$$A[i] = A[i] + d$$$ for all $$$i$$$ in range $$$[L, R]$$$ inclusive.

All changes are temporarily made to initial array, and don't propagate to following queries. Help the adventurer calculate the answer to a quest, and finally get that loot!

## Input Format
In the first two lines, numbers $$$N$$$ ($$$1 \leq N \leq 2*10^4$$$) and $$$K$$$ ($$$1 \leq K \leq N$$$), the length of initial array $$$A$$$, and tuple size, followed by $$$a_1,a_2,a_3,…,a_N$$$ ($$$0 \leq a_i \leq 10^9$$$) , elements of array $$$A$$$, in the next line. Then follows number $$$Q$$$ ($$$Q \leq 10$$$), number of queries. In the next $$$Q$$$ lines come queries of the form:

- 1 q i d, for type 1,
- 2 q L R d, for type 2,

as explained above ($$$0 \leq q, d \leq 10^9, 1 \leq i,L,R \leq N$$$)

## Output Format
Print $$$Q$$$ lines, the answers to queries, modulo $$$998244353$$$.

## Examples
```input
5
2
1 2 3 4 5
3
1 6 1 1
1 6 5 2
2 6 2 3 1
```
```output
85
127
63
```

## Note
In the first query array A = [1, 2, 3, 4, 5], B = [5, 4, 3, 2, 1], sum of products of 2-tuples = 85.

In second query array A = [1, 2, 3, 4, 2], B = [5, 4, 3, 2, 4], sum of products of 2-tuples = 127

In third query array A = [1, 3, 4, 4, 5], B = [5, 3, 2, 2, 1], sum of products of 2-tuples = 63

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: 1.0 seconds
Memory limit: 128.0 MB

# Problem
Three planets $$$X$$$, $$$Y$$$ and $$$Z$$$ within the Alpha planetary system are inhabited with an advanced civilization. The spaceports of these planets are connected by interplanetary space shuttles. The flight scheduler should decide between $$$1$$$, $$$2$$$ and $$$3$$$ return flights for every existing space shuttle connection. Since the residents of Alpha are strong opponents of the symmetry, there is a strict rule that any two of the spaceports connected by a shuttle must have a different number of flights.

For every pair of connected spaceports, your goal is to propose a number $$$1$$$, $$$2$$$ or $$$3$$$ for each shuttle flight, so that for every two connected spaceports the overall number of flights differs.

You may assume that:

1) Every planet has at least one spaceport

2) There exist only shuttle flights between spaceports of different planets

3) For every two spaceports there is a series of shuttle flights enabling traveling between them

4) Spaceports are not connected by more than one shuttle

## Input Format
The first row of the input is the integer number $$$N$$$ $$$(3 \leq N \leq 100 000)$$$, representing overall number of spaceports. The second row is the integer number $$$M$$$ $$$(2 \leq M \leq 100 000)$$$ representing number of shuttle flight connections.

Third row contains $$$N$$$ characters from the set $$$\{X, Y, Z\}$$$. Letter on $$$I^{th}$$$ position indicates on which planet is situated spaceport $$$I$$$. For example, "XYYXZZ" indicates that the spaceports $$$0$$$ and $$$3$$$ are located at planet $$$X$$$, spaceports $$$1$$$ and $$$2$$$ are located at $$$Y$$$, and spaceports $$$4$$$ and $$$5$$$ are at $$$Z$$$.

Starting from the fourth row, every row contains two integer numbers separated by a whitespace. These numbers are natural numbers smaller than $$$N$$$ and indicate the numbers of the spaceports that are connected. For example, "$$$12\ 15$$$" indicates that there is a shuttle flight between spaceports $$$12$$$ and $$$15$$$.

## Output Format
The same representation of shuttle flights in separate rows as in the input, but also containing a third number from the set $$$\{1, 2, 3\}$$$ standing for the number of shuttle flights between these spaceports.

## Examples
```input
10
15
XXXXYYYZZZ
0 4
0 5
0 6
4 1
4 8
1 7
1 9
7 2
7 5
5 3
6 2
6 9
8 2
8 3
9 3
```
```output
0 4 2
0 5 2
0 6 2
4 1 1
4 8 1
1 7 2
1 9 3
7 2 2
7 5 1
5 3 1
6 2 1
6 9 1
8 2 3
8 3 1
9 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 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You're given two arrays $$$a[1 \dots n]$$$ and $$$b[1 \dots n]$$$, both of the same length $$$n$$$.

In order to perform a push operation, you have to choose three integers $$$l, r, k$$$ satisfying $$$1 \le l \le r \le n$$$ and $$$k > 0$$$. Then, you will add $$$k$$$ to elements $$$a_l, a_{l+1}, \ldots, a_r$$$.

For example, if $$$a = [3, 7, 1, 4, 1, 2]$$$ and you choose $$$(l = 3, r = 5, k = 2)$$$, the array $$$a$$$ will become $$$[3, 7, \underline{3, 6, 3}, 2]$$$.

You can do this operation at most once. Can you make array $$$a$$$ equal to array $$$b$$$?

(We consider that $$$a = b$$$ if and only if, for every $$$1 \le i \le n$$$, $$$a_i = b_i$$$)

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100\ 000$$$) — the number of elements in each array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$).

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 1000$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, output one line containing "YES" if it's possible to make arrays $$$a$$$ and $$$b$$$ equal by performing at most once the described operation or "NO" if it's impossible.

You can print each letter in any case (upper or lower).

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

## Note
The first test case is described in the statement: we can perform a push operation with parameters $$$(l=3, r=5, k=2)$$$ to make $$$a$$$ equal to $$$b$$$.

In the second test case, we would need at least two operations to make $$$a$$$ equal to $$$b$$$.

In the third test case, arrays $$$a$$$ and $$$b$$$ are already equal.

In the fourth test case, it's impossible to make $$$a$$$ equal to $$$b$$$, because the integer $$$k$$$ has to be positive.

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

# Problem
You're given an undirected graph with $$$n$$$ nodes and $$$m$$$ edges. Nodes are numbered from $$$1$$$ to $$$n$$$.

The graph is considered harmonious if and only if the following property holds:

- For every triple of integers $$$(l, m, r)$$$ such that $$$1 \le l < m < r \le n$$$, if there exists a path going from node $$$l$$$ to node $$$r$$$, then there exists a path going from node $$$l$$$ to node $$$m$$$.

In other words, in a harmonious graph, if from a node $$$l$$$ we can reach a node $$$r$$$ through edges ($$$l < r$$$), then we should able to reach nodes $$$(l+1), (l+2), \ldots, (r-1)$$$ too.

What is the minimum number of edges we need to add to make the graph harmonious?

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 200\ 000$$$ and $$$1 \le m \le 200\ 000$$$).

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), that mean that there's an edge between nodes $$$u$$$ and $$$v$$$.

It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes).

## Output Format
Print the minimum number of edges we have to add to the graph to make it harmonious.

## Examples
```input
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12
```
```output
1
```
-----
```input
200000 3
7 9
9 8
4 5
```
```output
0
```

## Note
In the first example, the given graph is not harmonious (for instance, $$$1 < 6 < 7$$$, node $$$1$$$ can reach node $$$7$$$ through the path $$$1 \rightarrow 2 \rightarrow 7$$$, but node $$$1$$$ can't reach node $$$6$$$). However adding the edge $$$(2, 4)$$$ is sufficient to make it harmonious.

In the second example, the given graph is already harmonious.

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: 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 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: 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 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: 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.