{"problem":{"name":"K. Crazy queries","description":{"content":"Given two strings S and P, and Q queries, for each query you are given a range [L, R]. For each pair of integers i and j chosen with uniform probability among all pairs where 1 ≤ i ≤ L and R ≤ j ≤ |S","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":30000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10199K"},"statements":[{"statement_type":"Markdown","content":"Given two strings S and P, and Q queries, for each query you are given a range [L, R].\n\nFor each pair of integers i and j chosen with uniform probability among all pairs where 1 ≤ i ≤ L and R ≤ j ≤ |S|, create a new string S2 that is the result of concatenating S[1... i] and S[j... |S|]. You have to find the expected number of occurrences of P in S2.\n\nNote that all occurrences of P must be counted even if they overlap. The queries are independent meaning that the string S is the same for all queries.\n\nThe first line of the input contains a single integer T the number of test cases. Each test case starts with two lines. The first line contains string S and the second line contains P, where 2 ≤ |S| ≤ 105 and 1 ≤ |P| ≤ 100. Each string consists of lowercase English letters. \n\nThe third line contains an integer Q, where 1 ≤ Q ≤ 5·104. Each of the next Q lines represents a single query with two space-separated integers L and R, where 1 ≤ L < R ≤ |S|.\n\nFor each test case output Q lines. where each line contains the answer of the corresponding query in the form p/q where p and q are the numerator and denominator of the expected value in its simplest form respectively. \n\n## Input\n\nThe first line of the input contains a single integer T the number of test cases. Each test case starts with two lines. The first line contains string S and the second line contains P, where 2 ≤ |S| ≤ 105 and 1 ≤ |P| ≤ 100. Each string consists of lowercase English letters. The third line contains an integer Q, where 1 ≤ Q ≤ 5·104. Each of the next Q lines represents a single query with two space-separated integers L and R, where 1 ≤ L < R ≤ |S|.\n\n## Output\n\nFor each test case output Q lines. where each line contains the answer of the corresponding query in the form p/q where p and q are the numerator and denominator of the expected value in its simplest form respectively. \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ S $ be a string of length $ n = |S| $, and $ P $ be a pattern string of length $ m = |P| $.  \nLet $ Q $ be the number of queries. For each query, we are given integers $ L $ and $ R $ with $ 1 \\leq L < R \\leq n $.  \n\nLet $ S[1..i] $ denote the prefix of $ S $ ending at index $ i $, and $ S[j..n] $ denote the suffix of $ S $ starting at index $ j $.  \nDefine $ S_2(i,j) = S[1..i] + S[j..n] $ for $ 1 \\leq i \\leq L $, $ R \\leq j \\leq n $.  \n\nLet $ X_{i,j} $ be the number of (possibly overlapping) occurrences of $ P $ in $ S_2(i,j) $.  \n\n**Constraints**  \n1. $ 2 \\leq |S| \\leq 10^5 $, $ 1 \\leq |P| \\leq 100 $, $ S, P \\in \\Sigma^* $, $ \\Sigma = \\{a,\\dots,z\\} $  \n2. $ 1 \\leq Q \\leq 5 \\cdot 10^4 $  \n3. For each query: $ 1 \\leq L < R \\leq |S| $  \n\n**Objective**  \nFor each query $ (L, R) $, compute the expected value:  \n$$\n\\mathbb{E}[X] = \\frac{1}{L \\cdot (n - R + 1)} \\sum_{i=1}^{L} \\sum_{j=R}^{n} X_{i,j}\n$$  \nExpress the result as a reduced fraction $ \\frac{p}{q} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10199K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}