+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- استاد امروز شئ شبیه به کیک از دوستش دریافت کرده. شئ شبیه به کیک شامل $n$ ستون است که ستون $i$ام آن (با شماره‌گذاری از چپ به راست) $a_{i}$ لایه دارد. استاد برای این که بفهمد آیا شئ شبیه به کیک واقعا کیک است یا نه تصمیم گرفته فرایند زیر را انجام دهد: او در هر مرحله می‌تواند $k$ ستون متوالی از شئ که در هر کدام از این ستون‌ها حداقل یک لایه باقی مانده را انتخاب کند و از هرکدام از این ستون‌ها یک لایه حذف کند. اگر پس از تعدادی مرحله تمام ستون‌ها خالی شدند (تمام لایه‌های هر ستون حذف شدند) استاد به این نتیجه می‌رسد که شئ شبیه به کیک واقعاً کیک بوده. در غیر این صورت متوجه می‌شود که شئ واقعاً کیک نبوده (و در نتیجه در کمال تعجب نه واقعی بوده و نه کیک). استاد که به دلیلی خودش نمی‌خواهد این فرایند را انجام دهد از شما خواسته تا با گرفتن اطلاعات مربوط به کیک و عدد $k$ به او بگویید که آیا شئ کیک است یا نه. # ورودی ورودی شامل $t$ سناریو است. اطلاعات سناریوها در خطوط متمایز و متوالی به شرح زیر برای هر سناریو می‌آید. خط اول سناریو $s$ شامل دو عدد $n_s$ و $k_s$ می‌شود. خط بعدی شامل $n_s$ عدد $a_{1}, a_{2}, ... a_{n}$ می‌شود که در آن، $a_{i}$ نشان دهنده‌ی تعداد لایه‌های ستون $i$ام از شئ است. $$1 \leq t \leq 10^4$$ $$1 \leq k_{s} \leq n_{s} \leq 10^6$$ $$0 \leq a_{i} \leq 10^9$$ $$\sum_{s=1}^{t} n_{s} \leq 10^6$$ # خروجی در خروجی در صورتی که شیئ واقعا کیک است عبارت `Cake` و در غیر این صورت عبارت `Fake` را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۳۰ | $\sum_{s=1}^{t} n_{s} \leq 3000$ | | ۲ | ۷۰ | $\sum_{s=1}^{t} n_{s} \leq 10^6$ | # مثال ## ورودی نمونه ۱ ``` 3 7 3 1 2 3 4 3 2 1 7 4 1 2 3 4 3 2 1 6 2 3 4 1 0 1 2 ``` ## خروجی نمونه ۱ ``` Fake Cake Fake ``` توضیحات نمونه: در سناریوی دوم استاد می‌تواند با انجام دادن عملیات‌های زیر به وضعیتی برسد که تمام ستون‌ها خالی‌اند: 1. از ستون سوم تا ششم یک لایه کم کند تا شئ به صورت `1 2 2 3 2 1 1` دراید. 2. از ستون دوم تا پنجم یک لایه کم کند تا شئ به صورت `1 1 1 2 1 1 1` دراید. 3. از ستون چهارم تا هفتم یک لایه کم کند تا شئ به صورت `1 1 1 1 0 0 0` دراید. 4. از ستون اول تا چهارم یک لایه کم کند تا شئ به صورت `0 0 0 0 0 0 0` دراید. به راحتی می‌توان دید که در سناریوهای اول و سوم استاد با هیچ روشی نمی‌تواند به وضعیتی که همه‌ی ستون‌ها خالی‌اند برسد.

حل سؤال در بانک سؤالات