Background

Original link: https://oier.team/problems/X5E.

epitaxy - かめりあ

Problem Description

You are given two positive integers $n, m$.

Define the value of a permutation $p$ of $1 \sim n$ as the greatest common divisor of the maximum values of all $n - m + 1$ consecutive subarrays of length $m$.
(By definition, the greatest common divisor of a single number is the number itself.)

Please find a permutation of $1 \sim n$ with the maximum value among all such permutations. If there are multiple, output any one.

This problem will use a custom checker to verify whether the permutation you construct is correct, so outputting any permutation with the maximum value will be accepted.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, denoting the number of test cases.

For each test case:

The first line contains two positive integers $n, m$.

Output Format

For each test case, output one line with $n$ positive integers, denoting a permutation $p_1, p_2, \ldots, p_n$ that meets the requirement.

This problem will use a custom checker to verify whether the permutation you construct is correct, so outputting any permutation with the maximum value will be accepted.

4
2 2
4 2
7 5
10 3

1 2
1 2 4 3
5 3 6 7 1 2 4
6 3 5 8 1 2 4 10 9 7

Hint

Sample Explanation.

In the first test case, when $n = 2, m = 2$, the permutation $p = [1, 2]$ has the maximum value, which is $2$. It can also be proven that when $n = 2, m = 2$, there is no permutation with value $> 2$.

In the second test case, when $n = 4, m = 2$, the permutation $p = [1, 2, 4, 3]$ has the maximum value, which is $2$, because the maximum values of all subarrays of length $2$ are $2, 4, 4$, whose greatest common divisor is $2$. It can also be proven that when $n = 4, m = 2$, there is no permutation with value $> 2$.

Constraints.

This problem uses bundled tests and enables subtask dependencies.

• Special Property A: $m = 2$.
• Special Property B: $m = n$.

For all testdata, it holds that $1 \le T \le 10^5$, $1 \le m \le 10^6$, $2 \le n, \sum n \le 10^6$, and $m \le n$.

Translated by ChatGPT 5