ساعت شنی


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

یک ساعت شنی داریم که اگر همه‌ی شن‌های داخل آن کاملاً در سمت بالا باشد، MM دقیقه طول می‌کشد تا شن‌ها به قسمت پایین منتقل شوند. ما این ساعت شنی را در لحظه‌ی ۰ روی میز قرار دادیم و راس دقیقه‌ی TT این ساعت شنی را روی میز بر می‌داریم. در لحظه‌ی ۰ همه‌ی شن‌ها در قسمت بالایی ساعت قرار دارد.

تصویر اصلی

همچنین nn لحظه t1,t2,,tnt_1, t_2, \dots, t_n\, از قبل به ما داده شده و می‌توانیم در این لحظه‌ها ساعت شنی را برعکس کنیم، یا هیچ تغییری ندهیم. (در بقیه لحظه‌ها این کار ممکن نیست.) می‌خواهیم طوری این فرآیند را انجام دهیم که هیچ یک دقیقه‌ی متوالی در این TT دقیقه پیش نیاید که ساعت شنی روی میز باشد و همه‌ی شن‌هایش به قسمت پایین رفته باشد و حرکتی نکند (توجه کنید یک لحظه خالی شدن مهم نیست). از شما می‌خواهیم برنامه‌ای بنویسید که بررسی کند آیا می‌توانیم این کار را انجام دهیم یا خیر؟

برای بهتر متوجه شدن سوال، به توضیح نمونه‌ها توجه کنید.

ورودی🔗

در سطر اول ورودی، عدد صحیح tt آمده که تعداد تست‌های یک ورودی را نشان می‌دهد. 1t1001 \leq t \leq 100

در سطر اول هر تست سه عدد صحیح nn، MM و TT با فاصله از هم داده می‌شوند. 1n,M1001 \leq n, M \leq 100 1T3001 \leq T \leq 300

در سطر دوم هر تست nn عدد صحیح t1,t2,,tnt_1, t_2, \dots, t_n\, داده می‌شود. 0<t1<t2<<tn<T0 \lt t_1 \lt t_2 \lt \dots \lt t_n \lt T

خروجی🔗

برای هر تست، در صورتی که این کار شدنی است YES و در غیر این صورت NO چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

2
2 6 10
3 6
1 10 25
11
Plain text

خروجی نمونه ۱🔗

YES
NO
Plain text
توضیح نمونه ۱

در تست اول، M=6M = 6 دقیقه طول می‌کشد تا ساعت شنی کاملاً خالی شود. ساعت شنی را در دقیقه‌ی ۰ روی میز قرار می‌دهیم و در دقیقه‌ی T=10T = 10 از روی میز بر می‌داریم. در دقیقه‌های t1=3t_1 = 3 و t2=6t_2 = 6 می‌توانیم ساعت شنی را برعکس کنیم.

اگر در لحظه‌ی t2=6t_2 = 6 برعکس کنیم هیچ وقت ساعت یک دقیقه متوالی بی‌حرکت نخواهد بود. چون از دقیقه‌ی ۰ تا ۶ در حال خالی شدن است و درست در همان لحظه، ساعت برعکس می‌شود و در دقیقه‌ی ۱۰، هنوز به اندازه‌ی ۲ دقیقه شن دارد و هیچ‌وقت ساعت از حرکت نیفتاده است.

در تست اول، M=10M = 10 دقیقه طول می‌کشد تا ساعت شنی کاملاً خالی شود. ساعت شنی را در دقیقه‌ی ۰ روی میز قرار می‌دهیم و در دقیقه‌ی T=25T = 25 از روی میز بر می‌داریم. در دقیقه‌ی t1=11t_1 = 11 می‌توانیم ساعت شنی را برعکس کنیم.

قبل از رسیدن به اولین زمان ممکن برای تغییر وضعیت ساعت، در بازه‌ی دقیقه‌ی ۱۰ تا ۱۱ ساعت شنی بی‌حرکت می‌ماند. پس نمی‌توانیم به هدفمان برسیم.