{"problem":{"name":"G. Cutie Pie","description":{"content":"Consider a NxM small-letters grid. SVU asked you to check whether this grid is a Cutie Pie or not  A grid is a cutie pie if you can find the word \"pie\" in any direction (vertical, horizontal, and radi","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10102G"},"statements":[{"statement_type":"Markdown","content":"Consider a NxM small-letters grid. SVU asked you to check whether this grid is a Cutie Pie or not  A grid is a cutie pie if you can find the word \"pie\" in any direction (vertical, horizontal, and radial).  Your program should output \"Cutie Pie!\" if the grid contains the word \"pie\" or \"Sorry Man\" otherwise\n\nThe first line contains T 1<=T<=10000 the number of test cases.  The followed T lines represent the test cases, each one contains two integers 0 < N,M  ≤  20 then N lines each of them contains M English small-letter separated by space characters. There is a blank line between each two successive test cases. \n\nFor each test case output \"Cutie Pie!\" if the grid in the test case contains the word \"pie\" or \"Sorry Man\" otherwise.\n\n## Input\n\nThe first line contains T 1<=T<=10000 the number of test cases.  The followed T lines represent the test cases, each one contains two integers 0 < N,M  ≤  20 then N lines each of them contains M English small-letter separated by space characters. There is a blank line between each two successive test cases. \n\n## Output\n\nFor each test case output \"Cutie Pie!\" if the grid in the test case contains the word \"pie\" or \"Sorry Man\" otherwise.\n\n[samples]","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, let $ h, w, d \\in \\mathbb{Z} $ denote:  \n- $ h $: height of the tower (number of floors),  \n- $ w $: width of the tower (number of rooms per floor),  \n- $ d $: room index (1-based) on the ground floor (floor 1) where the monster is located.  \n\nThe hero starts at position $ (h, 1) $ (top-left room).  \nThe stone moves diagonally down-right until it hits the right border ($ w $), then diagonally down-left until it hits the left border ($ 1 $), and so on, alternating direction upon hitting a vertical border.  \nThe stone stops when it reaches floor 1 (ground floor).  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unknown} $ (but input size implies practical limits)  \n2. $ 2 \\leq h, w \\leq 10^9 $  \n3. $ 1 \\leq d \\leq 10^9 $  \n\n**Objective**  \nDetermine whether the stone, starting at $ (h, 1) $ and moving diagonally with reflection at vertical boundaries, lands exactly on room $ d $ of floor 1.  \n\nDefine the stone’s horizontal position as a function of floor $ f $ (from $ h $ down to 1).  \nLet $ x(f) $ be the horizontal position (1-based) of the stone when it reaches floor $ f $.  \n\nThe motion is periodic with period $ 2(w - 1) $ in horizontal displacement per vertical drop of $ w - 1 $ floors.  \nThe stone moves $ \\Delta x = +1 $ per floor down while going right, and $ \\Delta x = -1 $ per floor down while going left.  \n\nThe horizontal displacement from top to bottom is equivalent to simulating a reflection path:  \n- The stone’s horizontal trajectory modulo $ 2(w - 1) $ determines its final position.  \n\nLet $ \\text{total\\_vertical\\_steps} = h - 1 $.  \nThe horizontal displacement is $ \\Delta = h - 1 $.  \n\nThe stone’s horizontal position on floor 1 is given by:  \n$$\nx(1) = 1 + \\Delta \\mod 2(w - 1)\n$$  \nBut if the result exceeds $ w $, reflect:  \nLet $ r = (h - 1) \\mod (2(w - 1)) $.  \nThen:  \n- If $ r < w $, then $ x(1) = 1 + r $  \n- Else, $ x(1) = 2w - 1 - r $  \n\nAlternatively, use the standard reflection formula:  \n$$\nx(1) = 1 + \\left| (h - 1) \\mod (2(w - 1)) - (w - 1) \\right|\n$$  \nBut simpler:  \nLet $ r = (h - 1) \\mod (2(w - 1)) $  \nThen:  \n$$\nx(1) = \n\\begin{cases}\n1 + r & \\text{if } r < w \\\\\n2w - 1 - r & \\text{if } r \\geq w\n\\end{cases}\n$$  \n\n**Objective (Formal)**  \nFor each test case, compute $ x(1) $ as above.  \nOutput \"Yes\" if $ x(1) = d $, otherwise \"No\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10102G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}