
ZOJ Problem Set  3979
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 nonempty 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_{k1}\) 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. InputThere 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\). OutputFor each test case, output \(n\) integers denoting the password. Sample Input3 1 1 4 4 3 2 Sample Output1 1 2 3 4 1 1 2 HintFor 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 