---{"category_name":"easy","problem_code":"MGSTR121","problem_name":"K - Magical String","problemComponents":{"constraints":"- $1 \\leq T \\leq 100$\n- $1 \\leq N \\leq 10^5$\n- $1 \\leq Q \\leq 10^5$\n- $1 \\leq L \\leq R \\leq N$\n- $1 \\leq K \\leq N$\n- The sum of $( R - L + 1 )$ over all $Q$ queries over all test cases whose answer is `\u0022Yes\u0022` is less than or equal to $10^6$.","constraintsState":true,"subtasks":"","subtasksState":false,"inputFormat":"- The first line contains $T$ denoting the number of test cases.\n- The first line of each test case contains an integer $N$ denoting the length of the string.\n- The second line of each test case contains the string $S$ given in question.\n- The third line of the test case contains an integer $Q$ denoting the number of queries.\n- Next, $Q$ lines contain three space-separated integers $L, R,$ and $K$.\n\n","inputFormatState":true,"outputFormat":"For each query in each test case, print `\u0022Yes\u0022` if it is possible to rearrange the characters of that substring such that it can be converted into $K$-Magical string and print the rearranged string else print `\u0022No\u0022` without quotes.\n\nYou may print each character of the string in uppercase or lowercase (for example, the strings \u0022yEs\u0022, \u0022yes\u0022, \u0022Yes\u0022 and \u0022YES\u0022 will all be treated as identical).","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"1\n9\nEFDAABCBD\n4\n1 9 6\n6 8 1\n4 7 3\n1 2 1","output":"Yes\nFEDAABBCD\nNo\nYes\nCAAB\nYes\nFE","explanation":"**Test case $1$**: \n\n**For the first query :** \n$L = 1, R = 9, K = 6$ , the substring we are concerned with is `\u0022EFDAABCBD\u0022`, we can rearrange its characters to `\u0022FEDAABBCD\u0022`. Now, as it has the longest non-decreasing subsequence of size exactly $K = 6$ (The longest non decreasing subsequence being `\u0022AABBCD\u0022`). Therefore, the answer to this query is \u0022Yes\u0022.\n\n**For the second query:** \n$L = 6, R = 8, K = 1$, the substring is `\u0022BCB\u0022`, as there is no way in which we could rearrange the characters such that the longest non decreasing subsequence could become of size exactly $K = 1$. Therefore, the answer to this query is \u0022No\u0022.\n\n**For the third query:**\n$L = 4, R = 7, K = 3$ , the substring is `\u0022AABC\u0022`, we can rearrange its characters to `\u0022CAAB\u0022`. Now, as this string has the longest non-decreasing subsequence of size exactly $K = 3$ and the subsequence will be `\u0022AAB\u0022`. Therefore the answer to this query is \u0022Yes\u0022.\n\n**For the fourth query:**\n $L = 1, R = 2, K = 1$, the substring is `\u0022EF\u0022`, we can rearrange its characters to `\u0022FE\u0022` . Now, as this string has the longest non-decreasing subsequence of size exactly $K = 1$ and the subsequence will be `\u0022F\u0022`. Therefore the answer to this query is \u0022Yes\u0022.","isDeleted":false}}},"video_editorial_url":"https://youtu.be/5hace8uYXPc","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"mystic_ankush","problem_tester":"mexomerf","date_added":"24-09-2021","tags":{"0":"easy","1":"mystic_ankush","2":"prefix","3":"start16"},"problem_difficulty_level":"Easy","best_tag":"Prefix Sum","editorial_url":"https://discuss.codechef.com/problems/MGSTR121","time":{"view_start_date":1634751002,"submit_start_date":1634751002,"visible_start_date":1634751002,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=MGSTR121","is_proctored":false,"visitedContests":{},"layout":"problem"}---You have been given a string $S$ of size $N$ which consists of **uppercase characters** only. A $K$-Magical String is a string in which the longest **non - decreasing subsequence** is of size exactly $K$.You have been given $Q$ queries where each query is in the form $L, R,$ and $K$.For each query, check whether substring from index $L$ to index $R$ can be converted into a $K$-Magical String or not by rearranging its characters and print the final rearranged string too.If there exist multiple answers, print the **lexicographically largest** string possible.**Note:**- Each query will be treated independently i.e. after each query the string will remain the same as it was initially.- The input files are large. The use of Fast I/O is recommended.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>