{"problem":{"name":"D. Dumb feature","description":{"content":"Naum's cellphone has a keypad just like on the image below. When he's typing someone's name, Naum needs to press just once the key that contains the letter which he's typing at the moment. Everyone w","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10202D"},"statements":[{"statement_type":"Markdown","content":"Naum's cellphone has a keypad just like on the image below. When he's typing someone's name, Naum needs to press just once the key that contains the letter which he's typing at the moment.\n\nEveryone was very impressed by this amazing functionality, except for you. So, Naum challenged you to solve this problem, if you really want to prove that this functionality isn't that awesome after all.\n\nGiven a list of $N$ Naum's cellphone contacts and $Q$ sequences of pressed keys, you must answer, for each sequence, the number of contacts whose name could actually be being typed by Naum.\n\nFormally, Naum could be typing a name $s$ with the sequence of letters $t$ if there is a replacement of the keys in $t$ for the letters they represent, resulting in string $t '$, where $t '$ is a prefix of $s$.\n\nThe first line of input contains two integers $N$ and $Q$ ($1 <= N <= 10^5$, $1 <= Q <= 2 dot.op 10^5$), being the size of Naum's cellphone contact list and the number of sequences to be analyzed, respectively.\n\nThen, $N$ lines follow, where the $i$-th of them contain a string $s_i$ $(0 < s_i <= 10^5)$, the name of the $i$-th contact, which consists only in lowercase english letters, from A to Z.\n\nFinally, $Q$ lines follow, where the $i$-th of them contains a string $t_i$ ($0 < t_i <= 10^5$), the $i$-th sequence of keys typed by Naum, which consists of numbers from $0$ to $9$ (inclusive).\n\nIt is guaranteed that $sum_{i = 1}^N | s_i | <= 10^6$ and $sum_{i = 1}^Q | t_i | <= 10^6$.\n\nYou must output $Q$ integers, the answer for each one of the given sequences of keys.\n\n## Input\n\nThe first line of input contains two integers $N$ and $Q$ ($1 <= N <= 10^5$, $1 <= Q <= 2 dot.op 10^5$), being the size of Naum's cellphone contact list and the number of sequences to be analyzed, respectively.Then, $N$ lines follow, where the $i$-th of them contain a string $s_i$ $(0 < s_i <= 10^5)$, the name of the $i$-th contact, which consists only in lowercase english letters, from A to Z.Finally, $Q$ lines follow, where the $i$-th of them contains a string $t_i$ ($0 < t_i <= 10^5$), the $i$-th sequence of keys typed by Naum, which consists of numbers from $0$ to $9$ (inclusive).It is guaranteed that $sum_{i = 1}^N | s_i | <= 10^6$ and $sum_{i = 1}^Q | t_i | <= 10^6$.\n\n## Output\n\nYou must output $Q$ integers, the answer for each one of the given sequences of keys.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ a, b, r, d \\in \\mathbb{R}^+ $ be given:  \n- $ a $: width of the car (in inches)  \n- $ b $: length of the car (in inches)  \n- $ r $: radius of the circular arc (internal boundary)  \n- $ d $: central angle of the arc in degrees  \n\nLet $ \\theta = \\frac{d \\pi}{180} $ be the central angle in radians.  \n\nThe car is modeled as a rectangle of width $ a $ and length $ b $, with its right front corner tracing the arc of radius $ r $. The car's orientation is always tangential to the arc.  \n\n**Constraints**  \n$ 0 < a, b, r < 100 $, $ 0 < d < 180 $  \n\n**Objective**  \nCompute the minimal lane width $ w $ such that the entire car remains within the lane during the turn.  \n\nThe outer boundary of the lane is the locus of the farthest point of the car from the center of the arc. The farthest point is the **left rear corner** of the car.  \n\nLet $ O $ be the center of the circular arc.  \nAt any instant, the right front corner $ P $ lies on the arc of radius $ r $.  \nThe car’s orientation is tangential to the arc at $ P $.  \n\nThe vector from $ P $ to the left rear corner $ Q $ is:  \n- $ -a $ units perpendicular to the tangent (leftward, normal direction),  \n- $ -b $ units opposite to the tangent direction (backward).  \n\nThus, the distance from $ O $ to $ Q $ is:  \n$$\n\\| \\vec{OQ} \\| = \\sqrt{ (r - a)^2 + b^2 }\n$$  \n\nThe minimal lane width $ w $ is the difference between the maximum distance from $ O $ to any point on the car and the radius $ r $:  \n$$\nw = \\sqrt{(r - a)^2 + b^2} - r\n$$  \n\n**Output**  \nFor each test case, output $ w = \\sqrt{(r - a)^2 + b^2} - r $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10202D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}