{"raw_statement":[{"iden":"statement","content":"Jonas is reading the book called “Algorithms and Data Structures (for extremely experienced computer scientists edition)”. He learned a new data structure - the array of lowercase letters. As Jonas is innovative and you are his good friend, he assigned you the task to implement and to use the array of uppercase letters. This data structure is mainly a string with only uppercase letters which can operate two types of queries: \n\nThe first line contains the number of test cases _T_ (T ≤ 5). The first line of each test case contains the string of only uppercase letters (1 ≤ thelength ≤ 105). The second line of each test case contains the number of queries _q_ (0 ≤ q ≤ 6000). The following q lines contain “_s l r_” or “_g l r_” (quotes for clarity only).\n\nNote: the sum of all r - l in the queries of “Sort” won’t exceed 105 in the whole input file.\n\nFor each test case output one line containing “_Case #tc:_”, where _tc_ is the number of the test case (starting from 1). Then for each query “_g l r_” output a line containing 26 numbers (frequences of letters from A to Z in the given subinterval [l;r]).\n\n"},{"iden":"input","content":"The first line contains the number of test cases _T_ (T ≤ 5). The first line of each test case contains the string of only uppercase letters (1 ≤ thelength ≤ 105). The second line of each test case contains the number of queries _q_ (0 ≤ q ≤ 6000). The following q lines contain “_s l r_” or “_g l r_” (quotes for clarity only).Note: the sum of all r - l in the queries of “Sort” won’t exceed 105 in the whole input file."},{"iden":"output","content":"For each test case output one line containing “_Case #tc:_”, where _tc_ is the number of the test case (starting from 1). Then for each query “_g l r_” output a line containing 26 numbers (frequences of letters from A to Z in the given subinterval [l;r])."},{"iden":"examples","content":"Input1BCA11g 0 0g 1 1g 2 2s 1 2g 1 1g 2 2s 0 2g 1 2g 0 0g 1 1g 2 2OutputCase #1:0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ S_k \\in \\{A, B, \\dots, Z\\}^* $ be a string of uppercase letters.  \n- Let $ q_k \\in \\mathbb{Z}_{\\geq 0} $ be the number of queries.  \n- Each query is of type:  \n  - **Sort**: $ \\texttt{\"s l r\"} $ — sort the substring $ S_k[l:r] $ (inclusive) in non-decreasing order.  \n  - **Get**: $ \\texttt{\"g l r\"} $ — compute the frequency vector of letters A–Z in substring $ S_k[l:r] $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 5 $  \n2. For each test case $ k $:  \n   - $ 1 \\leq |S_k| \\leq 10^5 $  \n   - $ 0 \\leq q_k \\leq 6000 $  \n3. The sum of $ (r - l + 1) $ over all **Sort** queries across all test cases $ \\leq 10^5 $  \n\n**Objective**  \nFor each test case $ k $:  \n- Output: `\"Case #k:\"`  \n- For each **Get** query $ \\texttt{\"g l r\"} $, output a 26-tuple $ (f_A, f_B, \\dots, f_Z) $, where $ f_X $ is the number of occurrences of letter $ X \\in \\{A, \\dots, Z\\} $ in $ S_k[l:r] $.","simple_statement":"You are given a string of uppercase letters. For each test case, process queries of two types:  \n- \"s l r\": sort the substring from index l to r (inclusive) in increasing order.  \n- \"g l r\": output the frequency of each letter A to Z in the substring from l to r (inclusive).  \n\nOutput \"Case #tc:\" for each test case, then for each \"g\" query, print 26 space-separated numbers (counts of A, B, ..., Z).","has_page_source":false}