{"problem":{"name":"D. Frequency of String","description":{"content":"You are given a string $s$. You should answer $n$ queries. The $i$\\-th query consists of integer $k_i$ and string $m_i$. The answer for this query is the minimum length of such a string $t$ that $t$ i","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF963D"},"statements":[{"statement_type":"Markdown","content":"You are given a string $s$. You should answer $n$ queries. The $i$\\-th query consists of integer $k_i$ and string $m_i$. The answer for this query is the minimum length of such a string $t$ that $t$ is a substring of $s$ and $m_i$ has at least $k_i$ occurrences as a substring in $t$.\n\nA substring of a string is a continuous segment of characters of the string.\n\nIt is guaranteed that for any two queries the strings $m_i$ from these queries are different.\n\n## Input\n\nThe first line contains string $s$ $(1 \\leq \\left | s \\right | \\leq 10^{5})$.\n\nThe second line contains an integer $n$ ($1 \\leq n \\leq 10^5$).\n\nEach of next $n$ lines contains an integer $k_i$ $(1 \\leq k_i \\leq |s|)$ and a non-empty string $m_i$ — parameters of the query with number $i$, in this order.\n\nAll strings in input consists of lowercase English letters. Sum of length of all strings in input doesn't exceed $10^5$. All $m_i$ are distinct.\n\n## Output\n\nFor each query output the answer for it in a separate line.\n\nIf a string $m_{i}$ occurs in $s$ less that $k_{i}$ times, output _\\-1_.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给定一个字符串 $s$。你需要回答 $n$ 个查询。第 $i$ 个查询由整数 $k_i$ 和字符串 $m_i$ 组成。该查询的答案是满足以下条件的最短字符串 $t$ 的长度：$t$ 是 $s$ 的子串，且 $m_i$ 在 $t$ 中作为子串至少出现 $k_i$ 次。\n\n字符串的子串是指该字符串中连续的一段字符。\n\n保证任意两个查询中的字符串 $m_i$ 都不相同。\n\n第一行包含字符串 $s$ $(1 lt.eq | s | lt.eq 10^5)$。\n\n第二行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$)。\n\n接下来的 $n$ 行中，每行包含一个整数 $k_i$ $(1 lt.eq k_i lt.eq | s |)$ 和一个非空字符串 $m_i$ —— 第 $i$ 个查询的参数，按此顺序给出。\n\n输入中的所有字符串均由小写英文字母组成。输入中所有字符串的长度之和不超过 $10^5$。所有 $m_i$ 互不相同。\n\n对于每个查询，在单独一行中输出其答案。\n\n如果字符串 $m_i$ 在 $s$ 中出现的次数少于 $k_i$ 次，则输出 _-1_。\n\n## Input\n\n第一行包含字符串 $s$ $(1 lt.eq | s | lt.eq 10^5)$。第二行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$)。接下来的 $n$ 行中，每行包含一个整数 $k_i$ $(1 lt.eq k_i lt.eq | s |)$ 和一个非空字符串 $m_i$ —— 第 $i$ 个查询的参数，按此顺序给出。输入中的所有字符串均由小写英文字母组成。输入中所有字符串的长度之和不超过 $10^5$。所有 $m_i$ 互不相同。\n\n## Output\n\n对于每个查询，在单独一行中输出其答案。如果字符串 $m_i$ 在 $s$ 中出现的次数少于 $k_i$ 次，则输出 _-1_。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s \\in \\Sigma^* $ be the input string, where $ \\Sigma $ is the set of lowercase English letters.  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of queries.  \nFor each query $ i \\in \\{1, \\dots, n\\} $, let $ k_i \\in \\mathbb{Z}^+ $ and $ m_i \\in \\Sigma^* \\setminus \\{\\varepsilon\\} $ be the query parameters, with all $ m_i $ distinct.\n\nLet $ \\text{occ}_s(m) $ denote the number of occurrences of substring $ m $ in $ s $, counted with overlap.\n\n**Constraints**  \n1. $ 1 \\le |s| \\le 10^5 $  \n2. $ 1 \\le n \\le 10^5 $  \n3. For each $ i $, $ 1 \\le k_i \\le |s| $  \n4. All $ m_i $ are non-empty and distinct  \n5. $ \\sum_{i=1}^n |m_i| \\le 10^5 $\n\n**Objective**  \nFor each query $ i $:  \n- If $ \\text{occ}_s(m_i) < k_i $, output $ -1 $.  \n- Otherwise, compute:  \n$$\n\\min \\left\\{ |t| \\;\\middle|\\; t \\text{ is a substring of } s \\text{ and } \\text{occ}_t(m_i) \\ge k_i \\right\\}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF963D","tags":["hashing","string suffix structures","strings"],"sample_group":[["aaaaa\n5\n3 a\n3 aa\n2 aaa\n3 aaaa\n1 aaaaa","3\n4\n4\n-1\n5"],["abbb\n7\n4 b\n1 ab\n3 bb\n1 abb\n2 bbb\n1 a\n2 abbb","\\-1\n2\n-1\n3\n-1\n1\n-1"]],"created_at":"2026-03-03 11:00:39"}}