yl-9/probench huggingface dataset:
# Sakurako and Chefir

## Problem Description

Given a tree with $ n $ vertices rooted at vertex $ 1 $ . While walking through it with her cat Chefir, Sakurako got distracted, and Chefir ran away.

To help Sakurako, Kosuke recorded his $ q $ guesses. In the $ i $ -th guess, he assumes that Chefir got lost at vertex $ v_i $ and had $ k_i $ stamina.

Also, for each guess, Kosuke assumes that Chefir could move along the edges an arbitrary number of times:

- from vertex $ a $ to vertex $ b $ , if $ a $ is an ancestor $ ^{\text{∗}} $ of $ b $ , the stamina will not change;
- from vertex $ a $ to vertex $ b $ , if $ a $ is not an ancestor of $ b $ , then Chefir's stamina decreases by $ 1 $ .

If Chefir's stamina is $ 0 $ , he cannot make a move of the second type.

For each assumption, your task is to find the distance to the farthest vertex that Chefir could reach from vertex $ v_i $ , having $ k_i $ stamina.

 $ ^{\text{∗}} $ Vertex $ a $ is an ancestor of vertex $ b $ if the shortest path from $ b $ to the root passes through $ a $ .

## Input Format

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

Each test case is described as follows:

- The first line contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree.
- The next $ n-1 $ lines contain the edges of the tree. It is guaranteed that the given edges form a tree.
- The next line consists of a single integer $ q $ $ (1\le q\le 2 \cdot 10^5) $ , which denotes the number of guesses made by Kosuke.
- The next $ q $ lines describe the guesses made by Kosuke, with two integers $ v_i $ , $ k_i $ $ (1\le v_i \le n, 0 \le k_i\le n) $ .

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

## Output Format

For each test case and for each guess, output the maximum distance to the farthest vertex that Chefir could reach from the starting point $ v_i $ having $ k_i $ stamina.

## Sample #1

### Sample Input #1

```
3
5
1 2
2 3
3 4
3 5
3
5 1
3 1
2 0
9
8 1
1 7
1 4
7 3
4 9
3 2
1 5
3 6
7
6 0
2 3
6 2
8 2
2 4
9 2
6 3
6
2 1
2 5
2 4
5 6
4 3
3
3 1
1 3
6 5
```

### Sample Output #1

```
2 1 2 
0 5 2 4 5 5 5 
1 3 4
```

## Hint

In the first example:

- In the first query, you can go from vertex $ 5 $ to vertex $ 3 $ (after which your stamina will decrease by $ 1 $ and become $ 0 $ ), and then you can go to vertex $ 4 $ ;
- In the second query, from vertex $ 3 $ with $ 1 $ stamina, you can only reach vertices $ 2 $ , $ 3 $ , $ 4 $ , and $ 5 $ ;
- In the third query, from vertex $ 2 $ with $ 0 $ stamina, you can only reach vertices $ 2 $ , $ 3 $ , $ 4 $ , and $ 5 $ ;

## Limit



Time Limit
4.00s

Memory Limit
250.00MB

Tags: data structures, dfs and similar, dp, greedy, trees
Difficulty: 2200
# Kosuke's Sloth

## Problem Description

Kosuke is too lazy. He will not give you any legend, just the task:

Fibonacci numbers are defined as follows:

- $ f(1)=f(2)=1 $ .
- $ f(n)=f(n-1)+f(n-2) $ $ (3\le n) $

 We denote $ G(n,k) $ as an index of the $ n $ -th Fibonacci number that is divisible by $ k $ . For given $ n $ and $ k $ , compute $ G(n,k) $ .As this number can be too big, output it by modulo $ 10^9+7 $ .

For example: $ G(3,2)=9 $ because the $ 3 $ -rd Fibonacci number that is divisible by $ 2 $ is $ 34 $ . $ [1,1,\textbf{2},3,5,\textbf{8},13,21,\textbf{34}] $ .

## Input Format

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

The first and only line contains two integers $ n $ and $ k $ ( $ 1 \le n \le 10^{18} $ , $ 1 \le k \le 10^5 $ ).

It is guaranteed that the sum of $ k $ across all test cases does not exceed $ 10^6 $ .

## Output Format

For each test case, output the only number: the value $ G(n,k) $ taken by modulo $ 10^9+7 $ .

## Sample #1

### Sample Input #1

```
3
3 2
100 1
1000000000000 1377
```

### Sample Output #1

```
9
100
999244007
```

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, math, number theory
Difficulty: 1800
# Sakurako, Kosuke, and the Permutation

## Problem Description

Sakurako's exams are over, and she did excellently. As a reward, she received a permutation $ p $ . Kosuke was not entirely satisfied because he failed one exam and did not receive a gift. He decided to sneak into her room (thanks to the code for her lock) and spoil the permutation so that it becomes simple.

A permutation $ p $ is considered simple if for every $ i $ $ (1\le i \le n) $ one of the following conditions holds:

- $ p_i=i $
- $ p_{p_i}=i $

For example, the permutations $ [1, 2, 3, 4] $ , $ [5, 2, 4, 3, 1] $ , and $ [2, 1] $ are simple, while $ [2, 3, 1] $ and $ [5, 2, 1, 4, 3] $ are not.

In one operation, Kosuke can choose indices $ i,j $ $ (1\le i,j\le n) $ and swap the elements $ p_i $ and $ p_j $ .

Sakurako is about to return home. Your task is to calculate the minimum number of operations that Kosuke needs to perform to make the permutation simple.

## Input Format

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

Each test case is described by two lines.

- The first line contains one integer $ n $ ( $ 1\le n \le 10^6 $ ) — the length of the permutation $ p $ .
- The second line contains $ n $ integers $ p_i $ ( $ 1\le p_i\le n $ ) — the elements of the permutation $ p $ .

It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 10^6 $ .

It is guaranteed that $ p $ is a permutation.

## Output Format

For each test case, output the minimum number of operations that Kosuke needs to perform to make the permutation simple.

## Sample #1

### Sample Input #1

```
6
5
1 2 3 4 5
5
5 4 3 2 1
5
2 3 4 5 1
4
2 3 4 1
3
1 3 2
7
2 3 1 5 6 7 4
```

### Sample Output #1

```
0
0
2
1
0
2
```

## Hint

In the first and second examples, the permutations are already simple.

In the fourth example, it is sufficient to swap $ p_2 $ and $ p_4 $ . Thus, the permutation will become $ [2, 1, 4, 3] $ in $ 1 $ operation.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, data structures, dfs and similar, dsu, graphs, greedy, math
Difficulty: 1400
# Kousuke's Assignment

## Problem Description

After a trip with Sakurako, Kousuke was very scared because he forgot about his programming assignment. In this assignment, the teacher gave him an array $ a $ of $ n $ integers and asked him to calculate the number of non-overlapping segments of the array $ a $ , such that each segment is considered beautiful.

A segment $ [l,r] $ is considered beautiful if $ a_l + a_{l+1} + \dots + a_{r-1} + a_r=0 $ .

For a fixed array $ a $ , your task is to compute the maximum number of non-overlapping beautiful segments.

## Input Format

The first line of input contains the number $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of $ 2 $ lines.

- The first line contains one integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the array.
- The second line contains $ n $ integers $ a_i $ ( $ -10^5 \le a_i \le 10^5 $ ) — the elements of the array $ a $ .

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

## Output Format

For each test case, output a single integer: the maximum number of non-overlapping beautiful segments.

## Sample #1

### Sample Input #1

```
3
5
2 1 -3 2 1
7
12 -4 4 43 -3 -5 8
6
0 -4 0 3 0 1
```

### Sample Output #1

```
1
2
3
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: data structures, dp, dsu, greedy, math
Difficulty: 1300
# Sakurako's Field Trip

## Problem Description

Even in university, students need to relax. That is why Sakurakos teacher decided to go on a field trip. It is known that all of the students will be walking in one line. The student with index $ i $ has some topic of interest which is described as $ a_i $ . As a teacher, you want to minimise the disturbance of the line of students.

The disturbance of the line is defined as the number of neighbouring people with the same topic of interest. In other words, disturbance is the number of indices $ j $ ( $ 1 \le j < n $ ) such that $ a_j = a_{j + 1} $ .

In order to do this, you can choose index $ i $ ( $ 1\le i\le n $ ) and swap students at positions $ i $ and $ n-i+1 $ . You can perform any number of swaps.

Your task is to determine the minimal amount of disturbance that you can achieve by doing the operation described above any number of times.

## Input Format

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

Each test case is described by two lines.

- The first line contains one integer $ n $ ( $ 2 \le n \le 10^5 $ ) — the length of the line of students.
- The second line contains $ n $ integers $ a_i $ ( $ 1\le a_i\le n $ ) — the topics of interest of students in line.

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

## Output Format

For each test case, output the minimal possible disturbance of the line that you can achieve.

## Sample #1

### Sample Input #1

```
9
5
1 1 1 2 3
6
2 1 2 2 1 1
4
1 2 1 1
6
2 1 1 2 2 4
4
2 1 2 3
6
1 2 2 1 2 1
5
4 5 5 1 5
7
1 4 3 5 1 1 3
7
3 1 3 2 2 3 3
```

### Sample Output #1

```
1
2
1
0
0
1
1
0
2
```

## Hint

In the first example, it is necessary to apply the operation to $ i=2 $ , thus the array will become $ [1, \textbf{2}, 1, \textbf{1}, 3] $ , with the bold elements indicating those that have swapped places. The disturbance of this array is equal to $ 1 $ .

In the fourth example, it is sufficient to apply the operation to $ i=3 $ , thus the array will become $ [2, 1, \textbf{2}, \textbf{1}, 2, 4] $ . The disturbance of this array is equal to $ 0 $ .

In the eighth example, it is sufficient to apply the operation to $ i=3 $ , thus the array will become $ [1, 4, \textbf{1}, 5, \textbf{3}, 1, 3] $ . The disturbance of this array is equal to $ 0 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: dp, greedy, two pointers
Difficulty: 1400
# Sakurako and Water

## Problem Description

During her journey with Kosuke, Sakurako and Kosuke found a valley that can be represented as a matrix of size $ n \times n $ , where at the intersection of the $ i $ -th row and the $ j $ -th column is a mountain with a height of $ a_{i,j} $ . If $ a_{i,j} < 0 $ , then there is a lake there.

Kosuke is very afraid of water, so Sakurako needs to help him:

- With her magic, she can select a square area of mountains and increase the height of each mountain on the main diagonal of that area by exactly one.

More formally, she can choose a submatrix with the upper left corner located at $ (i, j) $ and the lower right corner at $ (p, q) $ , such that $ p-i=q-j $ . She can then add one to each element at the intersection of the $ (i + k) $ -th row and the $ (j + k) $ -th column, for all $ k $ such that $ 0 \le k \le p-i $ .

Determine the minimum number of times Sakurako must use her magic so that there are no lakes.

## Input Format

The first line contains a single integer $ t $ ( $ 1 \le t \le 200 $ ) — the number of test cases.

Each test case is described as follows:

- The first line of each test case consists of a single number $ n $ ( $ 1 \le n \le 500 $ ).
- Each of the following $ n $ lines consists of $ n $ integers separated by spaces, which correspond to the heights of the mountains in the valley $ a $ ( $ -10^5 \le a_{i,j} \le 10^5 $ ).

It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 1000 $ .

## Output Format

For each test case, output the minimum number of times Sakurako will have to use her magic so that all lakes disappear.

## Sample #1

### Sample Input #1

```
4
1
1
2
-1 2
3 0
3
1 2 3
-2 1 -1
0 0 -1
5
1 1 -1 -1 3
-3 1 4 4 -4
-1 -1 3 0 -5
4 5 3 -3 -1
3 1 -3 -1 5
```

### Sample Output #1

```
0
1
4
19
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, constructive algorithms, greedy
Difficulty: 900
# Sakurako and Kosuke

## Problem Description

Sakurako and Kosuke decided to play some games with a dot on a coordinate line. The dot is currently located in position $ x=0 $ . They will be taking turns, and Sakurako will be the one to start.

On the $ i $ -th move, the current player will move the dot in some direction by $ 2\cdot i-1 $ units. Sakurako will always be moving the dot in the negative direction, whereas Kosuke will always move it in the positive direction.

In other words, the following will happen:

1. Sakurako will change the position of the dot by $ -1 $ , $ x = -1 $ now
2. Kosuke will change the position of the dot by $ 3 $ , $ x = 2 $ now
3. Sakurako will change the position of the dot by $ -5 $ , $ x = -3 $ now
4. $ \cdots $

They will keep on playing while the absolute value of the coordinate of the dot does not exceed $ n $ . More formally, the game continues while $ -n\le x\le n $ . It can be proven that the game will always end.

Your task is to determine who will be the one who makes the last turn.

## Input Format

The first line contains one integer $ t $ ( $ 1\le t\le 100 $ ) — the number of games that Sakurako and Kosuke played.

Each game is described by one number $ n $ ( $ 1 \le n\le 100 $ ) — the number that defines the condition when the game ends.

## Output Format

For each of the $ t $ games, output a line with the result of that game. If Sakurako makes the last turn, output "Sakurako" (without quotes); else output "Kosuke".

## Sample #1

### Sample Input #1

```
4
1
6
3
98
```

### Sample Output #1

```
Kosuke
Sakurako
Kosuke
Sakurako
```

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: constructive algorithms, implementation, math
Difficulty: 800
# Balanced

## Problem Description

You are given a cyclic array $ a $ with $ n $ elements, where $ n $ is odd. In each operation, you can do the following:

- Choose an index $ 1 \le i \le n $ and increase $ a_{i - 1} $ by $ 1 $ , $ a_i $ by $ 2 $ , and $ a_{i + 1} $ by $ 1 $ . The element before the first element is the last element because this is a cyclic array.

A cyclic array is called balanced if all its elements are equal to each other.

Find any sequence of operations to make this cyclic array balanced or determine that it is impossible. Please note that you do not have to minimize the number of operations.

## Input Format

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 2 \cdot 10^5 $ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n < 2 \cdot 10^5 $ , $ n $ is odd) — the length of the array $ a $ .

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^{6} $ ) — the elements of the array $ a $ .

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:

- If it is impossible to make the cyclic array balanced, output $ -1 $ .
- Otherwise, output $ n $ integers $ v_1, v_2, \ldots, v_n $ ( $ 0 \leq v_i \leq 10^{18} $ ) — where $ v_i $ denotes the number of operations applied to index $ i $ . It can be proved that if any solution exists, then there exists a solution under the given constraints. If there are several solutions under the given constraints, output any of them.

## Sample #1

### Sample Input #1

```
6
3
2 1 2
3
1 2 3
5
1 2 1 2 1
7
1 2 1 2 1 3 1
9
10000 10000 10000 10000 10000 10001 10002 10001 10000
1
10
```

### Sample Output #1

```
0 1 0 
2 1 0 
2 0 3 0 2 
4 2 7 0 8 0 6 
1 1 1 1 1 1 0 1 1 
0
```

## Hint

In the first test case:

- After $ 1 $ operation applied to index $ i = 2 $ , the array $ a = [3, 3, 3] $ .

In the second test case:

- After $ 2 $ operations applied to index $ i = 1 $ , the array $ a = [5, 4, 5] $ .
- After $ 1 $ operation applied to index $ i = 2 $ , the array $ a = [6, 6, 6] $ .

In the third test case:

- After $ 2 $ operations applied to index $ i = 1 $ , the array $ a = [5, 4, 1, 2, 3] $ .
- After $ 3 $ operations applied to index $ i = 3 $ , the array $ a = [5, 7, 7, 5, 3] $ .
- After $ 2 $ operations applied to index $ i = 5 $ , the array $ a = [7, 7, 7, 7, 7] $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, data structures, greedy, implementation, math
Difficulty: 2400
# Trinity

## Problem Description

You are given an array $ a $ of $ n $ elements $ a_1, a_2, \ldots, a_n $ .

You can perform the following operation any number (possibly $ 0 $ ) of times:

- Choose two integers $ i $ and $ j $ , where $ 1 \le i, j \le n $ , and assign $ a_i := a_j $ .

Find the minimum number of operations required to make the array $ a $ satisfy the condition:

- For every pairwise distinct triplet of indices $ (x, y, z) $ ( $ 1 \le x, y, z \le n $ , $ x \ne y $ , $ y \ne z $ , $ x \ne z $ ), there exists a non-degenerate triangle with side lengths $ a_x $ , $ a_y $ and $ a_z $ , i.e. $ a_x + a_y > a_z $ , $ a_y + a_z > a_x $ and $ a_z + a_x > a_y $ .

## Input Format

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — the number of elements in the array $ a $ .

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of the array $ a $ .

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 a single integer — the minimum number of operations required.

## Sample #1

### Sample Input #1

```
4
7
1 2 3 4 5 6 7
3
1 3 2
3
4 5 3
15
9 3 8 1 6 5 3 8 2 1 4 2 9 4 7
```

### Sample Output #1

```
3
1
0
8
```

## Hint

In the first test case, one of the possible series of operations would be:

- Assign $ a_1 := a_4 = 4 $ . The array will become $ [4, 2, 3, 4, 5, 6, 7] $ .
- Assign $ a_2 := a_5 = 5 $ . The array will become $ [4, 5, 3, 4, 5, 6, 7] $ .
- Assign $ a_7 := a_1 = 4 $ . The array will become $ [4, 5, 3, 4, 5, 6, 4] $ .

It can be proven that any triplet of elements with pairwise distinct indices in the final array forms a non-degenerate triangle, and there is no possible answer using less than $ 3 $ operations.

In the second test case, we can assign $ a_1 := a_2 = 3 $ to make the array $ a = [3, 3, 2] $ .

In the third test case, since $ 3 $ , $ 4 $ and $ 5 $ are valid side lengths of a triangle, we don't need to perform any operation to the array.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, math, sortings, two pointers
Difficulty: 1400
# Penchick and Desert Rabbit

## Problem Description

Dedicated to pushing himself to his limits, Penchick challenged himself to survive the midday sun in the Arabian Desert!

While trekking along a linear oasis, Penchick spots a desert rabbit preparing to jump along a line of palm trees. There are $ n $ trees, each with a height denoted by $ a_i $ .

The rabbit can jump from the $ i $ -th tree to the $ j $ -th tree if exactly one of the following conditions is true:

- $ j < i $ and $ a_j > a_i $ : the rabbit can jump backward to a taller tree.
- $ j > i $ and $ a_j < a_i $ : the rabbit can jump forward to a shorter tree.

For each $ i $ from $ 1 $ to $ n $ , determine the maximum height among all trees that the rabbit can reach if it starts from the $ i $ -th tree.

## Input Format

The first line contains the number of test cases $ t $ ( $ 1 \le t \le 5 \cdot 10^5 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 5 \cdot 10^5 $ ) — the number of trees.

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

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

## Output Format

For each test case, output $ n $ integers. The $ i $ -th integer should contain the maximum height among all trees that the rabbit can reach if it starts from the $ i $ -th tree.

## Sample #1

### Sample Input #1

```
5
4
2 3 1 4
5
5 4 3 2 1
4
2 1 1 3
4
1 1 3 1
8
2 4 1 6 3 8 5 7
```

### Sample Output #1

```
3 3 3 4 
5 5 5 5 5 
2 2 2 3 
1 1 3 3 
8 8 8 8 8 8 8 8
```

## Hint

In the first test case, the initial heights of trees are $ a = [2, 3, 1, 4] $ .

- If the rabbit starts from the first tree, it can jump to the third tree as $ 3 > 1 $ and $ 1 < 2 $ . Then, the rabbit can jump to the second tree as $ 2 < 3 $ and $ 3 > 1 $ . It can be proved that the rabbit cannot reach the fourth tree; hence, the maximum height of the tree that the rabbit can reach is $ a_2 = 3 $ .
- If the rabbit starts from the fourth tree, it does not need to jump anywhere as it is already at the highest tree.

In the second test case, the rabbit can jump to the first tree regardless of which tree it starts from.

In the fifth test case, if the rabbit starts from the fifth tree, it can jump to the fourth tree. Then the rabbit can jump to the seventh tree and finally reach the sixth tree. Therefore, the maximum height of the tree that the rabbit can reach is $ 8 $ .

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: binary search, data structures, dfs and similar, dp, dsu, greedy, implementation, two pointers
Difficulty: 1700
# Penchick and BBQ Buns

## Problem Description

Penchick loves two things: square numbers and Hong Kong-style BBQ buns! For his birthday, Kohane wants to combine them with a gift: $ n $ BBQ buns arranged from left to right. There are $ 10^6 $ available fillings of BBQ buns, numbered from $ 1 $ to $ 10^6 $ . To ensure that Penchick would love this gift, Kohane has a few goals:

- No filling is used exactly once; that is, each filling must either not appear at all or appear at least twice.
- For any two buns $ i $ and $ j $ that have the same filling, the distance between them, which is $ |i-j| $ , must be a perfect square $ ^{\text{∗}} $ .

Help Kohane find a valid way to choose the filling of the buns, or determine if it is impossible to satisfy her goals! If there are multiple solutions, print any of them.

 $ ^{\text{∗}} $ A positive integer $ x $ is a perfect square if there exists a positive integer $ y $ such that $ x = y^2 $ . For example, $ 49 $ and $ 1 $ are perfect squares because $ 49 = 7^2 $ and $ 1 = 1^2 $ respectively. On the other hand, $ 5 $ is not a perfect square as no integer squared equals $ 5 $

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 2\cdot 10^5 $ ). The description of the test cases follows.

The only line of each test case contains a single integer $ n $ ( $ 1\le n\le 2\cdot 10^5 $ ) — the number of BBQ buns.

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, if no valid choice of fillings exists, output $ -1 $ . Otherwise, output $ n $ integers, where the $ i $ -th integer represents the filling of the $ i $ -th BBQ bun. If there are multiple solutions, print any of them.

## Sample #1

### Sample Input #1

```
2
3
12
```

### Sample Output #1

```
-1
1 2 3 6 10 2 7 6 10 1 7 3
```

## Hint

In the first test case, the choice of fillings "1 1 1" is not allowed because buns $ 1 $ and $ 3 $ have the same filling, but are distance $ 2 $ apart, which is not a perfect square. The choice of fillings "1 1 2" is also not allowed as filling $ 2 $ is only used once.

In the second test case, the solution is valid because no filling is used exactly once, and any two buns with the same filling are spaced at a distance equal to a perfect square. For example, buns $ 1 $ and $ 10 $ both have filling $ 1 $ and are spaced at a distance of $ 9=3^2 $ . Similarly, buns $ 5 $ and $ 9 $ both have filling $ 10 $ and are spaced at a distance of $ 4=2^2 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, math, number theory
Difficulty: 1300