Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3979
Secure Password

Time Limit: 1 Second      Memory Limit: 65536 KB      Special Judge

DreamGrid has \(m\) types of letters which are numbered from \(1\) to \(m\), and there are infinitely many letters for each type. He would like to generate a most secure password in the world using these letters. He thinks that the security is related to the number of distinct Lyndon substrings it contains. The more, the better.

Given two integers \(n\) and \(m\), DreamGrid would like to find a string of length \(n\) containing the most number of distinct Lyndon substrings using \(m\) types of letters. If there are multiple such strings, output any of them.

Note that a Lyndon word is a non-empty string that is strictly smaller in lexicographic order than all of its rotations (we say string \(b\) is a rotation of string \(a\), if and only if there exists some \(k\) such that \(1 \le k \le |a|\) and \(a_ka_{k+1}\dots a_{|a|}a_1a_2\dots a_{k-1}\) is equal to \(b\), where \(a_i\) indicates the \(i\)-th character of string \(a\)). A Lyndon substring of \(s\) is a continuous substring of \(s\) which is a Lyndon word.


There are multiple test cases. The first line of input contains an integer \(T\), indicating the number of test cases. For each test case:

The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 1000\)).

It is guaranteed that the sum of all \(n\) does not exceed \(2 \times 10^6\).


For each test case, output \(n\) integers denoting the password.

Sample Input

1 1
4 4
3 2

Sample Output

1 2 3 4
1 1 2


For the second sample, there are \(10\) distinct Lyndon substrings: \(\{1\}\), \(\{1,2\}\), \(\{1,2,3\}\), \(\{1,2,3,4\}\), \(\{2\}\), \(\{2,3\}\), \(\{2,3,4\}\), \(\{3\}\), \(\{3,4\}\), \(\{4\}\).

For the third sample, there are \(4\) distinct Lyndon substrings: \(\{1\}\), \(\{1,2\}\), \(\{1,1,2\}\), \(\{2\}\).

Author: LIN, Xi
Source: The 2017 China Collegiate Programming Contest, Qinhuangdao Site, Practice
Submit    Status