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
Suppose you are living with two cats: A and B. There are $$$n$$$ napping spots where both cats usually sleep.

Your cats like to sleep and also like all these spots, so they change napping spot each hour cyclically:

- Cat A changes its napping place in order: $$$n, n - 1, n - 2, \dots, 3, 2, 1, n, n - 1, \dots$$$ In other words, at the first hour it's on the spot $$$n$$$ and then goes in decreasing order cyclically;
- Cat B changes its napping place in order: $$$1, 2, 3, \dots, n - 1, n, 1, 2, \dots$$$ In other words, at the first hour it's on the spot $$$1$$$ and then goes in increasing order cyclically.

The cat B is much younger, so they have a strict hierarchy: A and B don't lie together. In other words, if both cats'd like to go in spot $$$x$$$ then the A takes this place and B moves to the next place in its order (if $$$x < n$$$ then to $$$x + 1$$$, but if $$$x = n$$$ then to $$$1$$$). Cat B follows his order, so it won't return to the skipped spot $$$x$$$ after A frees it, but will move to the spot $$$x + 2$$$ and so on.

Calculate, where cat B will be at hour $$$k$$$?

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

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^9$$$; $$$1 \le k \le 10^9$$$) — the number of spots and hour $$$k$$$.

## Output Format
For each test case, print one integer — the index of the spot where cat B will sleep at hour $$$k$$$.

## Examples
```input
7
2 1
2 2
3 1
3 2
3 3
5 5
69 1337
```
```output
1
2
1
3
2
2
65
```

## Note
In the first and second test cases $$$n = 2$$$, so:

- at the $$$1$$$-st hour, A is on spot $$$2$$$ and B is on $$$1$$$;
- at the $$$2$$$-nd hour, A moves to spot $$$1$$$ and B — to $$$2$$$.

- at the $$$1$$$-st hour, A is on spot $$$3$$$ and B is on $$$1$$$;
- at the $$$2$$$-nd hour, A moves to spot $$$2$$$; B'd like to move from $$$1$$$ to $$$2$$$, but this spot is occupied, so it moves to $$$3$$$;
- at the $$$3$$$-rd hour, A moves to spot $$$1$$$; B also would like to move from $$$3$$$ to $$$1$$$, but this spot is occupied, so it moves to $$$2$$$.

In the sixth test case:

- A's spots at each hour are $$$[5, 4, 3, 2, 1]$$$;
- B's spots at each hour are $$$[1, 2, 4, 5, 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
A Pythagorean triple is a triple of integer numbers $$$(a, b, c)$$$ such that it is possible to form a right triangle with the lengths of the first cathetus, the second cathetus and the hypotenuse equal to $$$a$$$, $$$b$$$ and $$$c$$$, respectively. An example of the Pythagorean triple is $$$(3, 4, 5)$$$.

Vasya studies the properties of right triangles, and he uses a formula that determines if some triple of integers is Pythagorean. Unfortunately, he has forgotten the exact formula; he remembers only that the formula was some equation with squares. So, he came up with the following formula: $$$c = a^2 - b$$$.

Obviously, this is not the right formula to check if a triple of numbers is Pythagorean. But, to Vasya's surprise, it actually worked on the triple $$$(3, 4, 5)$$$: $$$5 = 3^2 - 4$$$, so, according to Vasya's formula, it is a Pythagorean triple.

When Vasya found the right formula (and understood that his formula is wrong), he wondered: how many are there triples of integers $$$(a, b, c)$$$ with $$$1 \le a \le b \le c \le n$$$ such that they are Pythagorean both according to his formula and the real definition? He asked you to count these triples.

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

Each test case consists of one line containing one integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

## Output Format
For each test case, print one integer — the number of triples of integers $$$(a, b, c)$$$ with $$$1 \le a \le b \le c \le n$$$ such that they are Pythagorean according both to the real definition and to the formula Vasya came up with.

## Examples
```input
3
3
6
9
```
```output
0
1
1
```

## Note
The only Pythagorean triple satisfying $$$c = a^2 - b$$$ with $$$1 \le a \le b \le c \le 9$$$ is $$$(3, 4, 5)$$$; that's why the answer for $$$n = 3$$$ is $$$0$$$, and the answer for $$$n = 6$$$ (and for $$$n = 9$$$) 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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a positive (greater than zero) integer $$$n$$$.

You have to represent $$$n$$$ as the sum of integers (possibly negative) consisting only of ones (digits '1'). For example, $$$24 = 11 + 11 + 1 + 1$$$ and $$$102 = 111 - 11 + 1 + 1$$$.

Among all possible representations, you have to find the one that uses the minimum number of ones in total.

## Input Format
The single line contains one integer $$$n$$$ ($$$1 \le n < 10^{50}$$$).

## Output Format
Print one integer $$$x$$$ — the minimum number of ones, such that there exist a representation of $$$n$$$ as the sum of integers (possibly negative) that uses $$$x$$$ ones in total.

## Examples
```input
24
```
```output
6
```
-----
```input
102
```
```output
7
```

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: 10.0 seconds
Memory limit: 1024.0 MB

# Problem
You have $$$c_1$$$ letters 'a', $$$c_2$$$ letters 'b', ..., $$$c_{26}$$$ letters 'z'. You want to build a beautiful string of length $$$n$$$ from them (obviously, you cannot use the $$$i$$$-th letter more than $$$c_i$$$ times). Each $$$c_i$$$ is greater than $$$\frac{n}{3}$$$.

A string is called beautiful if there are no palindromic contiguous substrings of odd length greater than $$$1$$$ in it. For example, the string "abacaba" is not beautiful, it has several palindromic substrings of odd length greater than $$$1$$$ (for example, "aca"). Another example: the string "abcaa" is beautiful.

Calculate the number of different strings you can build, and print the answer modulo $$$998244353$$$.

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

The second line contains $$$26$$$ integers $$$c_1$$$, $$$c_2$$$, ..., $$$c_{26}$$$ ($$$\frac{n}{3} < c_i \le n$$$).

## Output Format
Print one integer — the number of strings you can build, taken modulo $$$998244353$$$.

## Examples
```input
4
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
```
```output
422500
```
-----
```input
3
2 2 2 2 2 2 3 3 3 2 2 2 2 2 2 3 3 3 2 2 3 2 2 3 2 2
```
```output
16900
```
-----
```input
400
348 322 247 158 209 134 151 267 268 176 214 379 372 291 388 135 147 304 169 149 193 351 380 368 181 340
```
```output
287489790
```

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
There is a square field of size $$$n \times n$$$ in which two cells are marked. These cells can be in the same row or column.

You are to mark two more cells so that they are the corners of a rectangle with sides parallel to the coordinate axes.

For example, if $$$n=4$$$ and a rectangular field looks like this (there are asterisks in the marked cells):

$$$$$$ \begin{matrix} . & . & * & . \\ . & . & . & . \\ * & . & . & . \\ . & . & . & . \\ \end{matrix} $$$$$$

Then you can mark two more cells as follows

$$$$$$ \begin{matrix} * & . & * & . \\ . & . & . & . \\ * & . & * & . \\ . & . & . & . \\ \end{matrix} $$$$$$

If there are several possible solutions, then print any of them.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 400$$$). Then $$$t$$$ test cases follow.

The first row of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 400$$$) — the number of rows and columns in the table.

The following $$$n$$$ lines each contain $$$n$$$ characters '.' or '*' denoting empty and marked cells, respectively.

It is guaranteed that the sums of $$$n$$$ for all test cases do not exceed $$$400$$$.

It is guaranteed that there are exactly two asterisks on the field. They can be in the same row/column.

It is guaranteed that the solution exists.

## Output Format
For each test case, output $$$n$$$ rows of $$$n$$$ characters — a field with four asterisks marked corresponding to the statements. If there multiple correct answers, print any of them.

## Examples
```input
6
4
..*.
....
*...
....
2
*.
.*
2
.*
.*
3
*.*
...
...
5
.....
..*..
.....
.*...
.....
4
....
....
*...
*...
```
```output
*.*.
....
*.*.
....
**
**
**
**
*.*
*.*
...
.....
.**..
.....
.**..
.....
....
....
**..
**..
```

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 number $$$n$$$ and an array $$$b_1, b_2, \ldots, b_{n+2}$$$, obtained according to the following algorithm:

- some array $$$a_1, a_2, \ldots, a_n$$$ was guessed;
- array $$$a$$$ was written to array $$$b$$$, i.e. $$$b_i = a_i$$$ ($$$1 \le i \le n$$$);
- The $$$(n+1)$$$-th element of the array $$$b$$$ is the sum of the numbers in the array $$$a$$$, i.e. $$$b_{n+1} = a_1+a_2+\ldots+a_n$$$;
- The $$$(n+2)$$$-th element of the array $$$b$$$ was written some number $$$x$$$ ($$$1 \le x \le 10^9$$$), i.e. $$$b_{n+2} = x$$$; The
- array $$$b$$$ was shuffled.

For example, the array $$$b=[2, 3, 7, 12 ,2]$$$ it could be obtained in the following ways:

- $$$a=[2, 2, 3]$$$ and $$$x=12$$$;
- $$$a=[3, 2, 7]$$$ and $$$x=2$$$.

For the given array $$$b$$$, find any array $$$a$$$ that could have been guessed initially.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second row of each test case contains $$$n+2$$$ integers $$$b_1, b_2, \ldots, b_{n+2}$$$ ($$$1 \le b_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output:

- "-1", if the array $$$b$$$ could not be obtained from any array $$$a$$$;
- $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, otherwise.

If there are several arrays of $$$a$$$, you can output any.

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

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
A permutation is a sequence of $$$n$$$ integers from $$$1$$$ to $$$n$$$, in which all the numbers occur exactly once. For example, $$$[1]$$$, $$$[3, 5, 2, 1, 4]$$$, $$$[1, 3, 2]$$$ are permutations, and $$$[2, 3, 2]$$$, $$$[4, 3, 1]$$$, $$$[0]$$$ are not.

Polycarp was given four integers $$$n$$$, $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le n)$$$ and $$$s$$$ ($$$1 \le s \le \frac{n (n+1)}{2}$$$) and asked to find a permutation $$$p$$$ of numbers from $$$1$$$ to $$$n$$$ that satisfies the following condition:

- $$$s = p_l + p_{l+1} + \ldots + p_r$$$.

For example, for $$$n=5$$$, $$$l=3$$$, $$$r=5$$$, and $$$s=8$$$, the following permutations are suitable (not all options are listed):

- $$$p = [3, 4, 5, 2, 1]$$$;
- $$$p = [5, 2, 4, 3, 1]$$$;
- $$$p = [5, 2, 1, 3, 4]$$$.

Help Polycarp, for the given $$$n$$$, $$$l$$$, $$$r$$$, and $$$s$$$, find a permutation of numbers from $$$1$$$ to $$$n$$$ that fits the condition above. If there are several suitable permutations, print any of them.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$). Then $$$t$$$ test cases follow.

Each test case consist of one line with four integers $$$n$$$ ($$$1 \le n \le 500$$$), $$$l$$$ ($$$1 \le l \le n$$$), $$$r$$$ ($$$l \le r \le n$$$), $$$s$$$ ($$$1 \le s \le \frac{n (n+1)}{2}$$$).

It is guaranteed that the sum of $$$n$$$ for all input data sets does not exceed $$$500$$$.

## Output Format
For each test case, output on a separate line:

- $$$n$$$ integers — a permutation of length $$$n$$$ that fits the condition above if such a permutation exists;
- -1, otherwise.

If there are several suitable permutations, print any of them.

## Examples
```input
5
5 2 3 5
5 3 4 1
3 1 2 4
2 2 2 2
2 1 1 3
```
```output
1 2 3 4 5 
-1
1 3 2 
1 2 
-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: 512.0 MB

# Problem
Let us denote by $$$d(n)$$$ the sum of all divisors of the number $$$n$$$, i.e. $$$d(n) = \sum\limits_{k | n} k$$$.

For example, $$$d(1) = 1$$$, $$$d(4) = 1+2+4=7$$$, $$$d(6) = 1+2+3+6=12$$$.

For a given number $$$c$$$, find the minimum $$$n$$$ such that $$$d(n) = c$$$.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.

Each test case is characterized by one integer $$$c$$$ ($$$1 \le c \le 10^7$$$).

## Output Format
For each test case, output:

- "-1" if there is no such $$$n$$$ that $$$d(n) = c$$$;
- $$$n$$$, otherwise.

## Examples
```input
12
1
2
3
4
5
6
7
8
9
10
39
691
```
```output
1
-1
2
3
-1
5
4
7
-1
-1
18
-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
A number is called 2050-number if it is $$$2050$$$, $$$20500$$$, ..., ($$$2050 \cdot 10^k$$$ for integer $$$k \ge 0$$$).

Given a number $$$n$$$, you are asked to represent $$$n$$$ as the sum of some (not necessarily distinct) 2050-numbers. Compute the minimum number of 2050-numbers required for that.

## Input Format
The first line contains a single integer $$$T$$$ ($$$1\le T\leq 1\,000$$$) denoting the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 10^{18}$$$) denoting the number to be represented.

## Output Format
For each test case, output the minimum number of 2050-numbers in one line.

If $$$n$$$ cannot be represented as the sum of 2050-numbers, output $$$-1$$$ instead.

## Examples
```input
6
205
2050
4100
20500
22550
25308639900
```
```output
-1
1
2
1
2
36
```

## Note
In the third case, $$$4100 = 2050 + 2050$$$.

In the fifth case, $$$22550 = 20500 + 2050$$$.

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
Fillomino is a classic logic puzzle. (You do not need to know Fillomino in order to solve this problem.) In one classroom in Yunqi town, some volunteers are playing a board game variant of it:

Consider an $$$n$$$ by $$$n$$$ chessboard. Its rows are numbered from $$$1$$$ to $$$n$$$ from the top to the bottom. Its columns are numbered from $$$1$$$ to $$$n$$$ from the left to the right. A cell on an intersection of $$$x$$$-th row and $$$y$$$-th column is denoted $$$(x, y)$$$. The main diagonal of the chessboard is cells $$$(x, x)$$$ for all $$$1 \le x \le n$$$.

A permutation of $$$\{1, 2, 3, \dots, n\}$$$ is written on the main diagonal of the chessboard. There is exactly one number written on each of the cells. The problem is to partition the cells under and on the main diagonal (there are exactly $$$1+2+ \ldots +n$$$ such cells) into $$$n$$$ connected regions satisfying the following constraints:

1. Every region should be connected. That means that we can move from any cell of a region to any other cell of the same region visiting only cells of the same region and moving from a cell to an adjacent cell.
2. The $$$x$$$-th region should contain cell on the main diagonal with number $$$x$$$ for all $$$1\le x\le n$$$.
3. The number of cells that belong to the $$$x$$$-th region should be equal to $$$x$$$ for all $$$1\le x\le n$$$.
4. Each cell under and on the main diagonal should belong to exactly one region.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1\le n \le 500$$$) denoting the size of the chessboard.

The second line contains $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$. $$$p_i$$$ is the number written on cell $$$(i, i)$$$. It is guaranteed that each integer from $$$\{1, \ldots, n\}$$$ appears exactly once in $$$p_1$$$, ..., $$$p_n$$$.

## Output Format
If no solution exists, output $$$-1$$$.

Otherwise, output $$$n$$$ lines. The $$$i$$$-th line should contain $$$i$$$ numbers. The $$$j$$$-th number on the $$$i$$$-th line should be $$$x$$$ if cell $$$(i, j)$$$ belongs to the the region with $$$x$$$ cells.

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

## Note
The solutions to the examples are illustrated in the following pictures:

Now solve the problem and return the code.