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
Our dear Cafe's owner, JOE Miller, will soon take part in a new game TV-show "1 vs. $$$n$$$"!

The game goes in rounds, where in each round the host asks JOE and his opponents a common question. All participants failing to answer are eliminated. The show ends when only JOE remains (we assume that JOE never answers a question wrong!).

For each question JOE answers, if there are $$$s$$$ ($$$s > 0$$$) opponents remaining and $$$t$$$ ($$$0 \le t \le s$$$) of them make a mistake on it, JOE receives $$$\displaystyle\frac{t}{s}$$$ dollars, and consequently there will be $$$s - t$$$ opponents left for the next question.

JOE wonders what is the maximum possible reward he can receive in the best possible scenario. Yet he has little time before show starts, so can you help him answering it instead?

## Input Format
The first and single line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), denoting the number of JOE's opponents in the show.

## Output Format
Print a number denoting the maximum prize (in dollars) JOE could have.

Your answer will be considered correct if it's absolute or relative error won't exceed $$$10^{-4}$$$. In other words, if your answer is $$$a$$$ and the jury answer is $$$b$$$, then it must hold that $$$\frac{|a - b|}{max(1, b)} \le 10^{-4}$$$.

## Examples
```input
1
```
```output
1.000000000000
```
-----
```input
2
```
```output
1.500000000000
```

## Note
In the second example, the best scenario would be: one contestant fails at the first question, the other fails at the next one. The total reward will be $$$\displaystyle \frac{1}{2} + \frac{1}{1} = 1.5$$$ dollars.

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 given two integers $$$n$$$ and $$$m$$$ ($$$m < n$$$). Consider a convex regular polygon of $$$n$$$ vertices. Recall that a regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length).

Examples of convex regular polygons

Your task is to say if it is possible to build another convex regular polygon with $$$m$$$ vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon.

You have to answer $$$t$$$ independent test cases.

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

The next $$$t$$$ lines describe test cases. Each test case is given as two space-separated integers $$$n$$$ and $$$m$$$ ($$$3 \le m < n \le 100$$$) — the number of vertices in the initial polygon and the number of vertices in the polygon you want to build.

## Output Format
For each test case, print the answer — "YES" (without quotes), if it is possible to build another convex regular polygon with $$$m$$$ vertices such that its center coincides with the center of the initial polygon and each of its vertices is some vertex of the initial polygon and "NO" otherwise.

## Examples
```input
2
6 3
7 3
```
```output
YES
NO
```

## Note
The first test case of the example

It can be shown that the answer for the second test case of the example is "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 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$$$. Array is good if for each pair of indexes $$$i < j$$$ the condition $$$j - a_j \ne i - a_i$$$ holds. Can you shuffle this array so that it becomes good? To shuffle an array means to reorder its elements arbitrarily (leaving the initial order is also an option).

For example, if $$$a = [1, 1, 3, 5]$$$, then shuffled arrays $$$[1, 3, 5, 1]$$$, $$$[3, 5, 1, 1]$$$ and $$$[5, 3, 1, 1]$$$ are good, but shuffled arrays $$$[3, 1, 5, 1]$$$, $$$[1, 1, 3, 5]$$$ and $$$[1, 1, 5, 3]$$$ aren't.

It's guaranteed that it's always possible to shuffle an array to meet this condition.

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of array $$$a$$$.

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

## Output Format
For each test case print the shuffled version of the array $$$a$$$ which is good.

## Examples
```input
3
1
7
4
1 1 3 5
6
3 2 1 5 6 4
```
```output
7
1 5 1 3
2 4 6 1 3 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
You are given an array $$$a_1, a_2, \dots, a_n$$$. You can perform the following operation any number of times:

- Choose a pair of two neighboring equal elements $$$a_i = a_{i + 1}$$$ (if there is at least one such pair).
- Replace them by one element with value $$$a_i + 1$$$.

After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array $$$a$$$ you can get?

## Input Format
The first line contains the single integer $$$n$$$ ($$$1 \le n \le 500$$$) — the initial length of the array $$$a$$$.

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

## Output Format
Print the only integer — the minimum possible length you can get after performing the operation described above any number of times.

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

## Note
In the first test, this is one of the optimal sequences of operations: $$$4$$$ $$$3$$$ $$$2$$$ $$$2$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$\rightarrow$$$ $$$5$$$ $$$3$$$.

In the second test, this is one of the optimal sequences of operations: $$$3$$$ $$$3$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$\rightarrow$$$ $$$5$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$\rightarrow$$$ $$$5$$$ $$$5$$$ $$$4$$$ $$$\rightarrow$$$ $$$6$$$ $$$4$$$.

In the third and fourth tests, you can't perform the operation at all.

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

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ positive integers. Find a non-empty subset of its elements such that their sum is even (i.e. divisible by $$$2$$$) or determine that there is no such subset.

Both the given array and required subset may contain equal values.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$), number of test cases to solve. Descriptions of $$$t$$$ test cases follow.

A description of each test case consists of two lines. The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$), length of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$), elements of $$$a$$$. The given array $$$a$$$ can contain equal values (duplicates).

## Output Format
For each test case output $$$-1$$$ if there is no such subset of elements. Otherwise output positive integer $$$k$$$, number of elements in the required subset. Then output $$$k$$$ distinct integers ($$$1 \leq p_i \leq n$$$), indexes of the chosen elements. If there are multiple solutions output any of them.

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

## Note
There are three test cases in the example.

In the first test case, you can choose the subset consisting of only the second element. Its sum is $$$4$$$ and it is even.

In the second test case, there is only one non-empty subset of elements consisting of the first element, however sum in it is odd, so there is no solution.

In the third test case, the subset consisting of all array's elements has even sum.

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

# Problem
You are given an array $$$a$$$ of length $$$n$$$ and array $$$b$$$ of length $$$m$$$ both consisting of only integers $$$0$$$ and $$$1$$$. Consider a matrix $$$c$$$ of size $$$n \times m$$$ formed by following rule: $$$c_{i, j} = a_i \cdot b_j$$$ (i.e. $$$a_i$$$ multiplied by $$$b_j$$$). It's easy to see that $$$c$$$ consists of only zeroes and ones too.

How many subrectangles of size (area) $$$k$$$ consisting only of ones are there in $$$c$$$?

A subrectangle is an intersection of a consecutive (subsequent) segment of rows and a consecutive (subsequent) segment of columns. I.e. consider four integers $$$x_1, x_2, y_1, y_2$$$ ($$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$) a subrectangle $$$c[x_1 \dots x_2][y_1 \dots y_2]$$$ is an intersection of the rows $$$x_1, x_1+1, x_1+2, \dots, x_2$$$ and the columns $$$y_1, y_1+1, y_1+2, \dots, y_2$$$.

The size (area) of a subrectangle is the total number of cells in it.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n, m \leq 40\,000, 1 \leq k \leq n \cdot m$$$), length of array $$$a$$$, length of array $$$b$$$ and required size of subrectangles.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 1$$$), elements of $$$a$$$.

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \leq b_i \leq 1$$$), elements of $$$b$$$.

## Output Format
Output single integer — the number of subrectangles of $$$c$$$ with size (area) $$$k$$$ consisting only of ones.

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

## Note
In first example matrix $$$c$$$ is:

There are $$$4$$$ subrectangles of size $$$2$$$ consisting of only ones in it:

In second example matrix $$$c$$$ is:

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 two integers $$$n$$$ and $$$k$$$. Your task is to find if $$$n$$$ can be represented as a sum of $$$k$$$ distinct positive odd (not divisible by $$$2$$$) integers or not.

You have to answer $$$t$$$ independent test cases.

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

The next $$$t$$$ lines describe test cases. The only line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^7$$$).

## Output Format
For each test case, print the answer — "YES" (without quotes) if $$$n$$$ can be represented as a sum of $$$k$$$ distinct positive odd (not divisible by $$$2$$$) integers and "NO" otherwise.

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

## Note
In the first test case, you can represent $$$3$$$ as $$$3$$$.

In the second test case, the only way to represent $$$4$$$ is $$$1+3$$$.

In the third test case, you cannot represent $$$10$$$ as the sum of three distinct positive odd integers.

In the fourth test case, you can represent $$$10$$$ as $$$3+7$$$, for example.

In the fifth test case, you can represent $$$16$$$ as $$$1+3+5+7$$$.

In the sixth test case, you cannot represent $$$16$$$ as the sum of five distinct positive odd integers.

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
Petya has a rectangular Board of size $$$n \times m$$$. Initially, $$$k$$$ chips are placed on the board, $$$i$$$-th chip is located in the cell at the intersection of $$$sx_i$$$-th row and $$$sy_i$$$-th column.

In one action, Petya can move all the chips to the left, right, down or up by $$$1$$$ cell.

If the chip was in the $$$(x, y)$$$ cell, then after the operation:

- left, its coordinates will be $$$(x, y - 1)$$$;
- right, its coordinates will be $$$(x, y + 1)$$$;
- down, its coordinates will be $$$(x + 1, y)$$$;
- up, its coordinates will be $$$(x - 1, y)$$$.

If the chip is located by the wall of the board, and the action chosen by Petya moves it towards the wall, then the chip remains in its current position.

Note that several chips can be located in the same cell.

For each chip, Petya chose the position which it should visit. Note that it's not necessary for a chip to end up in this position.

Since Petya does not have a lot of free time, he is ready to do no more than $$$2nm$$$ actions.

You have to find out what actions Petya should do so that each chip visits the position that Petya selected for it at least once. Or determine that it is not possible to do this in $$$2nm$$$ actions.

## Input Format
The first line contains three integers $$$n, m, k$$$ ($$$1 \le n, m, k \le 200$$$) — the number of rows and columns of the board and the number of chips, respectively.

The next $$$k$$$ lines contains two integers each $$$sx_i, sy_i$$$ ($$$ 1 \le sx_i \le n, 1 \le sy_i \le m$$$) — the starting position of the $$$i$$$-th chip.

The next $$$k$$$ lines contains two integers each $$$fx_i, fy_i$$$ ($$$ 1 \le fx_i \le n, 1 \le fy_i \le m$$$) — the position that the $$$i$$$-chip should visit at least once.

## Output Format
In the first line print the number of operations so that each chip visits the position that Petya selected for it at least once.

In the second line output the sequence of operations. To indicate operations left, right, down, and up, use the characters $$$L, R, D, U$$$ respectively.

If the required sequence does not exist, print -1 in the single line.

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

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 a colored permutation $$$p_1, p_2, \dots, p_n$$$. The $$$i$$$-th element of the permutation has color $$$c_i$$$.

Let's define an infinite path as infinite sequence $$$i, p[i], p[p[i]], p[p[p[i]]] \dots$$$ where all elements have same color ($$$c[i] = c[p[i]] = c[p[p[i]]] = \dots$$$).

We can also define a multiplication of permutations $$$a$$$ and $$$b$$$ as permutation $$$c = a \times b$$$ where $$$c[i] = b[a[i]]$$$. Moreover, we can define a power $$$k$$$ of permutation $$$p$$$ as $$$p^k=\underbrace{p \times p \times \dots \times p}_{k \text{ times}}$$$.

Find the minimum $$$k > 0$$$ such that $$$p^k$$$ has at least one infinite path (i.e. there is a position $$$i$$$ in $$$p^k$$$ such that the sequence starting from $$$i$$$ is an infinite path).

It can be proved that the answer always exists.

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

Next $$$3T$$$ lines contain test cases — one per three lines. The first line contains single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the permutation.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i \neq p_j$$$ for $$$i \neq j$$$) — the permutation $$$p$$$.

The third line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — the colors of elements of the permutation.

It is guaranteed that the total sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
Print $$$T$$$ integers — one per test case. For each test case print minimum $$$k > 0$$$ such that $$$p^k$$$ has at least one infinite path.

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

## Note
In the first test case, $$$p^1 = p = [1, 3, 4, 2]$$$ and the sequence starting from $$$1$$$: $$$1, p[1] = 1, \dots$$$ is an infinite path.

In the second test case, $$$p^5 = [1, 2, 3, 4, 5]$$$ and it obviously contains several infinite paths.

In the third test case, $$$p^2 = [3, 6, 1, 8, 7, 2, 5, 4]$$$ and the sequence starting from $$$4$$$: $$$4, p^2[4]=8, p^2[8]=4, \dots$$$ is an infinite path since $$$c_4 = c_8 = 4$$$.

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 wrote down all integers from $$$0$$$ to $$$10^n - 1$$$, padding them with leading zeroes so their lengths are exactly $$$n$$$. For example, if $$$n = 3$$$ then you wrote out 000, 001, ..., 998, 999.

A block in an integer $$$x$$$ is a consecutive segment of equal digits that cannot be extended to the left or to the right.

For example, in the integer $$$00027734000$$$ there are three blocks of length $$$1$$$, one block of length $$$2$$$ and two blocks of length $$$3$$$.

For all integers $$$i$$$ from $$$1$$$ to $$$n$$$ count the number of blocks of length $$$i$$$ among the written down integers.

Since these integers may be too large, print them modulo $$$998244353$$$.

## Input Format
The only line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

## Output Format
In the only line print $$$n$$$ integers. The $$$i$$$-th integer is equal to the number of blocks of length $$$i$$$.

Since these integers may be too large, print them modulo $$$998244353$$$.

## Examples
```input
1
```
```output
10
```
-----
```input
2
```
```output
180 10
```

Now solve the problem and return the code.