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

# Problem
You are given four positive integers $$$n$$$, $$$m$$$, $$$a$$$, $$$b$$$ ($$$1 \le b \le n \le 50$$$; $$$1 \le a \le m \le 50$$$). Find any such rectangular matrix of size $$$n \times m$$$ that satisfies all of the following conditions:

- each row of the matrix contains exactly $$$a$$$ ones;
- each column of the matrix contains exactly $$$b$$$ ones;
- all other elements are zeros.

If the desired matrix does not exist, indicate this.

For example, for $$$n=3$$$, $$$m=6$$$, $$$a=2$$$, $$$b=1$$$, there exists a matrix satisfying the conditions above:

$$$$$$ \begin{vmatrix} 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \end{vmatrix} $$$$$$

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

Each test case is described by four positive integers $$$n$$$, $$$m$$$, $$$a$$$, $$$b$$$ ($$$1 \le b \le n \le 50$$$; $$$1 \le a \le m \le 50$$$), where $$$n$$$ and $$$m$$$ are the sizes of the matrix, and $$$a$$$ and $$$b$$$ are the number of ones for rows and columns, respectively.

## Output Format
For each test case print:

- "YES" (without quotes) and the required matrix (if there are several answers, print any) if it exists, or
- "NO" (without quotes) if it does not exist.

To print the matrix $$$n \times m$$$, print $$$n$$$ rows, each of which consists of $$$m$$$ numbers $$$0$$$ or $$$1$$$ describing a row of the matrix. Numbers must be printed without spaces.

## Examples
```input
5
3 6 2 1
2 2 2 1
2 2 2 2
4 4 2 2
2 1 1 2
```
```output
YES
010001
100100
001010
NO
YES
11
11
YES
1100
1100
0011
0011
YES
1
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
Ehab loves number theory, but for some reason he hates the number $$$x$$$. Given an array $$$a$$$, find the length of its longest subarray such that the sum of its elements isn't divisible by $$$x$$$, or determine that such subarray doesn't exist.

An array $$$a$$$ is a subarray of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

## Input Format
The first line contains an integer $$$t$$$ $$$(1 \le t \le 5)$$$ — the number of test cases you need to solve. The description of the test cases follows.

The first line of each test case contains 2 integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le x \le 10^4$$$) — the number of elements in the array $$$a$$$ and the number that Ehab hates.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$0 \le a_i \le 10^4$$$) — the elements of the array $$$a$$$.

## Output Format
For each testcase, print the length of the longest subarray whose sum isn't divisible by $$$x$$$. If there's no such subarray, print $$$-1$$$.

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

## Note
In the first test case, the subarray $$$[2,3]$$$ has sum of elements $$$5$$$, which isn't divisible by $$$3$$$.

In the second test case, the sum of elements of the whole array is $$$6$$$, which isn't divisible by $$$4$$$.

In the third test case, all subarrays have an even sum, so the answer is $$$-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
Given a permutation $$$p$$$ of length $$$n$$$, find its subsequence $$$s_1$$$, $$$s_2$$$, $$$\ldots$$$, $$$s_k$$$ of length at least $$$2$$$ such that:

- $$$|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$$$ is as big as possible over all subsequences of $$$p$$$ with length at least $$$2$$$.
- Among all such subsequences, choose the one whose length, $$$k$$$, is as small as possible.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

A sequence $$$a$$$ is a subsequence of an array $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deleting some (possibly, zero or all) elements.

A permutation of length $$$n$$$ is an array of length $$$n$$$ in which every element from $$$1$$$ to $$$n$$$ occurs exactly once.

## Input Format
The first line contains an integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the length of the permutation $$$p$$$.

The second line of each test case contains $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_{n}$$$ ($$$1 \le p_i \le n$$$, $$$p_i$$$ are distinct) — the elements of the permutation $$$p$$$.

The sum of $$$n$$$ across the test cases doesn't exceed $$$10^5$$$.

## Output Format
For each test case, the first line should contain the length of the found subsequence, $$$k$$$. The second line should contain $$$s_1$$$, $$$s_2$$$, $$$\ldots$$$, $$$s_k$$$ — its elements.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

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

## Note
In the first test case, there are $$$4$$$ subsequences of length at least $$$2$$$:

- $$$[3,2]$$$ which gives us $$$|3-2|=1$$$.
- $$$[3,1]$$$ which gives us $$$|3-1|=2$$$.
- $$$[2,1]$$$ which gives us $$$|2-1|=1$$$.
- $$$[3,2,1]$$$ which gives us $$$|3-2|+|2-1|=2$$$.

So the answer is either $$$[3,1]$$$ or $$$[3,2,1]$$$. Since we want the subsequence to be as short as possible, the answer is $$$[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
Given an array $$$a$$$ of length $$$n$$$, find another array, $$$b$$$, of length $$$n$$$ such that:

- for each $$$i$$$ $$$(1 \le i \le n)$$$ $$$MEX(\{b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_i\})=a_i$$$.

The $$$MEX$$$ of a set of integers is the smallest non-negative integer that doesn't belong to this set.

If such array doesn't exist, determine this.

## Input Format
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$0 \le a_i \le i$$$) — the elements of the array $$$a$$$. It's guaranteed that $$$a_i \le a_{i+1}$$$ for $$$1\le i < n$$$.

## Output Format
If there's no such array, print a single line containing $$$-1$$$.

Otherwise, print a single line containing $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_n$$$ ($$$0 \le b_i \le 10^6$$$)

If there are multiple answers, print any.

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

## Note
In the second test case, other answers like $$$[1,1,1,0]$$$, for example, are valid.

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
Given a connected undirected graph with $$$n$$$ vertices and an integer $$$k$$$, you have to either:

- either find an independent set that has exactly $$$\lceil\frac{k}{2}\rceil$$$ vertices.
- or find a simple cycle of length at most $$$k$$$.

An independent set is a set of vertices such that no two of them are connected by an edge. A simple cycle is a cycle that doesn't contain any vertex twice.

I have a proof that for any input you can always solve at least one of these problems, but it's left as an exercise for the reader.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$3 \le k \le n \le 10^5$$$, $$$n-1 \le m \le 2 \cdot 10^5$$$) — the number of vertices and edges in the graph, and the parameter $$$k$$$ from the statement.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$) that mean there's an edge between vertices $$$u$$$ and $$$v$$$. It's guaranteed that the graph is connected and doesn't contain any self-loops or multiple edges.

## Output Format
If you choose to solve the first problem, then on the first line print $$$1$$$, followed by a line containing $$$\lceil\frac{k}{2}\rceil$$$ distinct integers not exceeding $$$n$$$, the vertices in the desired independent set.

If you, however, choose to solve the second problem, then on the first line print $$$2$$$, followed by a line containing one integer, $$$c$$$, representing the length of the found cycle, followed by a line containing $$$c$$$ distinct integers not exceeding $$$n$$$, the vertices in the desired cycle, in the order they appear in the cycle.

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

## Note
In the first sample:

Notice that printing the independent set $$$\{2,4\}$$$ is also OK, but printing the cycle $$$1-2-3-4$$$ isn't, because its length must be at most $$$3$$$.

In the second sample:

Notice that printing the independent set $$$\{1,3\}$$$ or printing the cycle $$$2-1-4$$$ is also OK.

In the third sample:

In the fourth sample:

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
"Hey, it's homework time" — thought Polycarpus and of course he started with his favourite subject, IT. Polycarpus managed to solve all tasks but for the last one in 20 minutes. However, as he failed to solve the last task after some considerable time, the boy asked you to help him.

The sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

You are given an arbitrary sequence a1, a2, ..., an containing n integers. Each integer is not less than 1 and not greater than 5000. Determine what minimum number of elements Polycarpus needs to change to get a permutation (he should not delete or add numbers). In a single change he can modify any single sequence element (i. e. replace it with another integer).

## Input Format
The first line of the input data contains an integer n (1 ≤ n ≤ 5000) which represents how many numbers are in the sequence. The second line contains a sequence of integers ai (1 ≤ ai ≤ 5000, 1 ≤ i ≤ n).

## Output Format
Print the only number — the minimum number of changes needed to get the permutation.

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

## Note
The first sample contains the permutation, which is why no replacements are required.

In the second sample it is enough to replace the first element with the number 1 and that will make the sequence the needed permutation.

In the third sample we can replace the second element with number 4 and the fourth element with number 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 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
Polycarpus likes studying at school a lot and he is always diligent about his homework. Polycarpus has never had any problems with natural sciences as his great-great-grandfather was the great physicist Seinstein. On the other hand though, Polycarpus has never had an easy time with history.

Everybody knows that the World history encompasses exactly n events: the i-th event had continued from the year ai to the year bi inclusive (ai < bi). Polycarpus easily learned the dates when each of n events started and ended (Polycarpus inherited excellent memory from his great-great-granddad). But the teacher gave him a more complicated task: Polycaprus should know when all events began and ended and he should also find out for each event whether it includes another event. Polycarpus' teacher thinks that an event j includes an event i if aj < ai and bi < bj. Your task is simpler: find the number of events that are included in some other event.

## Input Format
The first input line contains integer n (1 ≤ n ≤ 105) which represents the number of events. Next n lines contain descriptions of the historical events, one event per line. The i + 1 line contains two integers ai and bi (1 ≤ ai < bi ≤ 109) — the beginning and the end of the i-th event. No two events start or finish in the same year, that is, ai ≠ aj, ai ≠ bj, bi ≠ aj, bi ≠ bj for all i, j (where i ≠ j). Events are given in arbitrary order.

## Output Format
Print the only integer — the answer to the problem.

## Examples
```input
5
1 10
2 9
3 8
4 7
5 6
```
```output
4
```
-----
```input
5
1 100
2 50
51 99
52 98
10 60
```
```output
4
```
-----
```input
1
1 1000000000
```
```output
0
```

## Note
In the first example the fifth event is contained in the fourth. Similarly, the fourth event is contained in the third, the third — in the second and the second — in the first.

In the second example all events except the first one are contained in the first.

In the third example only one event, so the answer is 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 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 $$$LCM(x, y)$$$ be the minimum positive integer that is divisible by both $$$x$$$ and $$$y$$$. For example, $$$LCM(13, 37) = 481$$$, $$$LCM(9, 6) = 18$$$.

You are given two integers $$$l$$$ and $$$r$$$. Find two integers $$$x$$$ and $$$y$$$ such that $$$l \le x < y \le r$$$ and $$$l \le LCM(x, y) \le r$$$.

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

Each test case is represented by one line containing two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le 10^9$$$).

## Output Format
For each test case, print two integers:

- if it is impossible to find integers $$$x$$$ and $$$y$$$ meeting the constraints in the statement, print two integers equal to $$$-1$$$;
- otherwise, print the values of $$$x$$$ and $$$y$$$ (if there are multiple valid answers, you may print any of them).

## Examples
```input
4
1 1337
13 69
2 4
88 89
```
```output
6 7
14 21
2 4
-1 -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: 2.0 seconds
Memory limit: 256.0 MB

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

Initially you are standing at index $$$1$$$ and have a score equal to $$$a_1$$$. You can perform two kinds of moves:

1. move right — go from your current index $$$x$$$ to $$$x+1$$$ and add $$$a_{x+1}$$$ to your score. This move can only be performed if $$$x<n$$$.
2. move left — go from your current index $$$x$$$ to $$$x-1$$$ and add $$$a_{x-1}$$$ to your score. This move can only be performed if $$$x>1$$$. Also, you can't perform two or more moves to the left in a row.

You want to perform exactly $$$k$$$ moves. Also, there should be no more than $$$z$$$ moves to the left among them.

What is the maximum score you can achieve?

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

The first line of each testcase contains three integers $$$n, k$$$ and $$$z$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le n - 1$$$, $$$0 \le z \le min(5, k)$$$) — the number of elements in the array, the total number of moves you should perform and the maximum number of moves to the left you can perform.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$) — the given array.

The sum of $$$n$$$ over all testcases does not exceed $$$3 \cdot 10^5$$$.

## Output Format
Print $$$t$$$ integers — for each testcase output the maximum score you can achieve if you make exactly $$$k$$$ moves in total, no more than $$$z$$$ of them are to the left and there are no two or more moves to the left in a row.

## Examples
```input
4
5 4 0
1 5 4 3 2
5 4 1
1 5 4 3 2
5 4 4
10 20 30 40 50
10 7 3
4 6 8 2 9 9 7 4 10 9
```
```output
15
19
150
56
```

## Note
In the first testcase you are not allowed to move left at all. So you make four moves to the right and obtain the score $$$a_1 + a_2 + a_3 + a_4 + a_5$$$.

In the second example you can move one time to the left. So we can follow these moves: right, right, left, right. The score will be $$$a_1 + a_2 + a_3 + a_2 + a_3$$$.

In the third example you can move four times to the left but it's not optimal anyway, you can just move four times to the right and obtain the score $$$a_1 + a_2 + a_3 + a_4 + a_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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's call left cyclic shift of some string $$$t_1 t_2 t_3 \dots t_{n - 1} t_n$$$ as string $$$t_2 t_3 \dots t_{n - 1} t_n t_1$$$.

Analogically, let's call right cyclic shift of string $$$t$$$ as string $$$t_n t_1 t_2 t_3 \dots t_{n - 1}$$$.

Let's say string $$$t$$$ is good if its left cyclic shift is equal to its right cyclic shift.

You are given string $$$s$$$ which consists of digits 0–9.

What is the minimum number of characters you need to erase from $$$s$$$ to make it good?

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

Next $$$t$$$ lines contains test cases — one per line. The first and only line of each test case contains string $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$). Each character $$$s_i$$$ is digit 0–9.

It's guaranteed that the total length of strings doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print the minimum number of characters you need to erase from $$$s$$$ to make it good.

## Examples
```input
3
95831
100120013
252525252525
```
```output
3
5
0
```

## Note
In the first test case, you can erase any $$$3$$$ characters, for example, the $$$1$$$-st, the $$$3$$$-rd, and the $$$4$$$-th. You'll get string 51 and it is good.

In the second test case, we can erase all characters except 0: the remaining string is 0000 and it's good.

In the third test case, the given string $$$s$$$ is already good.

Now solve the problem and return the code.