{"problem":{"name":"G. Most Common Suffix","description":{"content":"You are given n strings, and q queries. For each query i, your task is to find the most common suffix of length xi, you need to print how common it is. The suffix i (or the ith suffix) of a string is","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10150G"},"statements":[{"statement_type":"Markdown","content":"You are given n strings, and q queries. For each query i, your task is to find the most common suffix of length xi, you need to print how common it is.\n\nThe suffix i (or the ith suffix) of a string is a special case of substring that goes from the ith character of the string up to the last character of the string. For example, the 4th suffix of \"_development_\" is \"_lopment_\", the 7th suffix of \"_development_\" is \"_ment_\" (0-based indexing).\n\nThe first line contains an integer T (1 ≤ T ≤ 75), where T is the number of test cases.\n\nThe first line of each test case contains two integers n and q (1 ≤ n, q ≤ 104), where n is the number of strings, and q is the number of queries.\n\nThen n lines follow, each line contains a string s, giving the strings. All strings are non-empty consisting of lowercase English letters.\n\nThen q lines follow, each line contains an integer x (1 ≤ x ≤ m), giving the queries. Where m equals the length of the longest string among the given n strings.\n\nThe total length of strings in each test case does not exceed 105.\n\nFor each query, print a single line containing the answer.\n\nAs input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use _scanf/printf_ instead of _cin/cout_ in C++, prefer to use _BufferedReader/PrintWriter_ instead of _Scanner/System.out_ in Java.\n\n## Input\n\nThe first line contains an integer T (1 ≤ T ≤ 75), where T is the number of test cases.The first line of each test case contains two integers n and q (1 ≤ n, q ≤ 104), where n is the number of strings, and q is the number of queries.Then n lines follow, each line contains a string s, giving the strings. All strings are non-empty consisting of lowercase English letters.Then q lines follow, each line contains an integer x (1 ≤ x ≤ m), giving the queries. Where m equals the length of the longest string among the given n strings.The total length of strings in each test case does not exceed 105.\n\n## Output\n\nFor each query, print a single line containing the answer.\n\n[samples]\n\n## Note\n\nAs input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use _scanf/printf_ instead of _cin/cout_ in C++, prefer to use _BufferedReader/PrintWriter_ instead of _Scanner/System.out_ in Java.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n, q \\in \\mathbb{Z} $ denote the number of strings and queries, respectively.  \n- Let $ S = \\{s_1, s_2, \\dots, s_n\\} $ be a set of strings, where each $ s_i $ is a non-empty string over the lowercase English alphabet.  \n- Let $ m = \\max_{s_i \\in S} |s_i| $ be the length of the longest string.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 75 $  \n2. For each test case:  \n   - $ 1 \\leq n, q \\leq 10^4 $  \n   - $ 1 \\leq |s_i| \\leq m $ for all $ s_i \\in S $  \n   - $ \\sum_{s_i \\in S} |s_i| \\leq 10^5 $  \n   - For each query $ x $: $ 1 \\leq x \\leq m $  \n\n**Objective**  \nFor each query $ x $, compute the maximum frequency among all suffixes of length $ x $ across all strings in $ S $.  \nThat is, for each $ x $, define:  \n$$\nf_x(t) = \\left| \\left\\{ s \\in S \\,\\middle|\\, \\text{suffix of } s \\text{ of length } x \\text{ equals } t \\right\\} \\right|\n$$  \nThen output:  \n$$\n\\max_{t \\in \\Sigma^x} f_x(t)\n$$  \nwhere $ \\Sigma $ is the set of lowercase English letters.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10150G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}