{"problem":{"name":"H. Singhal and String","description":{"content":"_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from code","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10276H"},"statements":[{"statement_type":"Markdown","content":"_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck._\n\nSinghal has a string $S$ consisting of lowercase English letters. He wants to form lexicographical smallest string by applying a operation atmost once.\n\nOperation is —\n\nChoose three distinct indices $i_1, i_2, i_3$ such that $1 <= i_i < i_2 < i_3 <= | S |$, where $| S |$ is the length of string and perform cyclic right shift on these indices.\n\nIf value at $i_1, i_2, i_3$ is $s_1, s_2, s_3$, then after performing right cyclic shift on these indices, value at indices will change to $i_2 arrow.r s_1, i_3 arrow.r s_2, i_1 arrow.r s_3$.\n\nExample - $S =$ \"codedigger\". Chosen indices is $1, 2, 3$ then resultant string will be $S =$ \"dcoedigger\".\n\nA string a is lexicographical smaller than a string b if and only if one of the following holds:\n\nThe first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.\n\nEach query contains a string $S (1 <= | S | <= 10^5)$ consisting of lowercase English letters. $| S |$ is the length of the string.\n\nIt is guaranteed that the total sum of $| S |$ is at most $10^5$.\n\nPrint $t$ answers to the test cases. Each answer must be consisting of single lexicographical smallest possible string.\n\nIn the first query, apply right cyclic shift on indices $1, 2, 3$ to get the smallest possible string $S =$ _aab_.\n\nIn the second or third query , if we apply operation we get lexicographical larger string. So we will not apply any operation.\n\n## Input\n\nThe first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.Each query contains a string $S (1 <= | S | <= 10^5)$ consisting of lowercase English letters. $| S |$ is the length of the string.It is guaranteed that the total sum of $| S |$ is at most $10^5$.\n\n## Output\n\nPrint $t$ answers to the test cases. Each answer must be consisting of single lexicographical smallest possible string.\n\n[samples]\n\n## Note\n\nIn the first query, apply right cyclic shift on indices $1, 2, 3$ to get the smallest possible string $S =$ _aab_.In the second or third query , if we apply operation we get lexicographical larger string. So we will not apply any operation.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of sequences.  \nLet $ S_n $ be the set of all $ n $-holy sequences (defined as all sequences of length $ n $ with elements in $ \\{1, 2, \\dots, n\\} $).  \nFor a sequence $ p \\in S_n $ and $ t \\in \\{1, 2, \\dots, n\\} $, let $ \\mathrm{cnt}(p, t) $ denote the number of occurrences of $ t $ in $ p $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 3000 $  \n2. $ 1 \\leq m \\leq 10^9 $  \n3. Total sum of $ n $ across test cases $ \\leq 10^4 $  \n\n**Objective**  \nFor each $ t \\in \\{1, 2, \\dots, n\\} $, compute:  \n$$\n\\sum_{p \\in S_n} \\mathrm{cnt}(p, t)^2 \\mod m\n$$  \nOutput the result for each $ t = 1 $ to $ n $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10276H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}