{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nThe College of Biological Sciences of Marjar University is famous for genetic engineering. After years of research, the scientists of Marjar University find some facts about genes.\n\u003c/p\u003e\n\n\u003cp\u003e\u003c/p\u003e\u003col\u003e\n \u003cli\u003eGenes are composed of simpler units called nucleotides.\u003c/li\u003e\n \u003cli\u003eThe kinds of nucleotides are limited. For now, there are only \u003cvar\u003eM\u003c/var\u003e kinds nucleotides.\u003c/li\u003e\n \u003cli\u003eFor different genes, the arrangements of nucleotides are different. So the functions of the genes are also different.\u003c/li\u003e\n\u003c/ol\u003e\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003e\nKnowing the facts, the scientists use the arrangements of nucleotides to identify genes, called genome sequence. For example {1, 2, 3, 4} is a gene composed of 1-th, 2-th, 3-th and 4-th nucleotide.\n\u003c/p\u003e\n\n\u003cp\u003e\nHowever, Edward, a weird but genius scientist (he is also the headmaster of Marjar University), found that even for two different genes, their functions may be same. Edward was curious about it and studied many samples. Finally, he found the reason and called it the similarity of genes. Two genes are similar to each other, if and only if their genome sequences meet the following rules:\n\u003c/p\u003e\n\n\u003cp\u003e\u003c/p\u003e\u003col\u003e\n \u003cli\u003eThey have the same length of their genome sequence.\u003c/li\u003e\n \u003cli\u003eTheir genome sequences are cyclically equivalent.\u003c/li\u003e\n\u003c/ol\u003e\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003e\nDuring the research, Edward found that if two similar genome sequences are concatenated, then it forms a pattern called Jacobi pattern (This pattern was in memory of the great work of the mathematician K. G. J. Jacobi). For example, if {1, 2, 3, 4} and {3, 4, 1, 2} are concatenated, we will have {1, 2, 3, 4, 3, 4, 1, 2}, which forms a Jacobi pattern. Now Edward gives you a genome sequence {\u003cvar\u003eA\u003c/var\u003e\u003csub\u003e1\u003c/sub\u003e, \u003cvar\u003eA\u003c/var\u003e\u003csub\u003e2\u003c/sub\u003e, ..., \u003cvar\u003eA\u003c/var\u003e\u003csub\u003e\u003cvar\u003eN\u003c/var\u003e\u003c/sub\u003e}, he wants to know how many continuous subsequence of {\u003cvar\u003eA\u003c/var\u003e\u003csub\u003e1\u003c/sub\u003e, \u003cvar\u003eA\u003c/var\u003e\u003csub\u003e2\u003c/sub\u003e, .., \u003cvar\u003eA\u003c/var\u003e\u003csub\u003e\u003cvar\u003eN\u003c/var\u003e\u003c/sub\u003e} form a Jacobi pattern.\n\u003c/p\u003e\n\n\u003cp\u003e\nPlease note, two sequences are cyclically equivalent if one of them can be obtained from another by moving its certain suffix from the end of the string to its beginning. For example {1, 2, 1, 2, 2, 1} and {1, 2, 2, 1, 1, 2} are cyclically equivalent, whereas {1, 2, 1, 2, 1} and {1, 1, 2, 2, 1} are not. In particular, every sequence is cyclically equivalent to itself.\n\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\n\u003cp\u003eThere are multiple test cases. The first line of input contains an integer \u003cvar\u003eT\u003c/var\u003e indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003e\nThe first line contains two integers \u003cvar\u003eN\u003c/var\u003e and \u003cvar\u003eM\u003c/var\u003e (1 \u0026lt;\u003d \u003cvar\u003eN\u003c/var\u003e, \u003cvar\u003eM\u003c/var\u003e \u0026lt;\u003d 5000) indicating the length of the sequence and the number of kinds of nucleotides.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe following line contains \u003cvar\u003eN\u003c/var\u003e integers \u003cvar\u003eA\u003c/var\u003e\u003csub\u003e1\u003c/sub\u003e, \u003cvar\u003eA\u003c/var\u003e\u003csub\u003e2\u003c/sub\u003e, .., \u003cvar\u003eA\u003c/var\u003e\u003csub\u003eN\u003c/sub\u003e (1 \u0026lt;\u003d \u003cvar\u003eA\u003c/var\u003e\u003csub\u003e\u003cvar\u003ei\u003c/var\u003e\u003c/sub\u003e \u0026lt;\u003d \u003cvar\u003eM\u003c/var\u003e) indicating the given genome sequence.\n\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\n\u003cp\u003e\nFor each test case, output two integers \u003cvar\u003eX\u003c/var\u003e and \u003cvar\u003eY\u003c/var\u003e on the first line, which indicates the total number of Jacobi patterns and the number of different length of Jacobi patterns.\n\u003c/p\u003e\n\n\u003cp\u003e\nFor the next \u003cvar\u003eY\u003c/var\u003e lines, firstly output two integers \u003cvar\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e, indicating a length of Jacobi patterns and the number of Jacobi patterns at this length. Then output \u003cvar\u003eC\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e integers \u003cvar\u003eP\u003c/var\u003e\u003csub\u003ei1\u003c/sub\u003e, \u003cvar\u003eP\u003c/var\u003e\u003csub\u003ei2\u003c/sub\u003e, .., \u003cvar\u003eP\u003c/var\u003e\u003csub\u003eiC\u003csub\u003ei\u003c/sub\u003e\u003c/sub\u003e in increasing order on the same line, where \u003cvar\u003eP\u003c/var\u003e\u003csub\u003e\u003cvar\u003eij\u003c/var\u003e\u003c/sub\u003e means there is a Jacobi pattern of length \u003cvar\u003eL\u003csub\u003ei\u003csub\u003e\u003c/sub\u003e\u003c/sub\u003e\u003c/var\u003e starting from index \u003cvar\u003eP\u003c/var\u003e\u003csub\u003e\u003cvar\u003eij\u003c/var\u003e\u003c/sub\u003e (indexes are 1-based). These lines should be listed in the increasing order of \u003cvar\u003eL\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e.\n\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n12 4\n1 1 1 2 3 4 3 4 1 2 2 1\n3 4\n1 2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6 3\n2 3 1 2 10\n4 2 5 9\n8 1 3\n0 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\n\u003cp\u003e\nIn the first sample test case, there are three Jacobi patterns of length 2: {1, 1}, {1, 1}, {2, 2}, two Jacobi patterns of length 4: {3, 4, 3, 4}, {1, 2, 2, 1} and only one Jacobi pattern of length 8: {1, 2, 3, 4, 3, 4, 1, 2}.\n\u003c/p\u003e\n\n\u003cp\u003e\nIn the second sample test case, we cannot find any Jacobi pattern.\n\u003c/p\u003e\n"}}]}