E. Амьтны үсрэлт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Амьтны үсрэлт тоглоомын зорилго нь "The Doodler" гэж нэрлэгдэх дөрвөн хөлтэй амьтныг төгсгөлгүй үргэлжлэх хавтгайнуудаар доош унагалгүй дээшээ үсэргэх юм. Эх сурвалж Википедиа.

Энэ маш алдартай тоглоом ба шидао энэ тоглоомонд маш их дуртай. Нэг өдөр шидао уг тоглоомыг тоглож байгаад үсрэгч амьтны үсрэх чадварын хязгаар шууд хүрч чадахгүй хавтгай байдаг болов уу гэж бодсон. Дараах бодлогыг авч үзье.

$n$ хавтгай байна. $x$-р ($1 ≤ x ≤ n$) хавтгайн өндөр нь $a*x$ тоог $p$ тоонд хуваагаад гарсан үлдэгдэл байна. Энд $a$ болон $p$ нь эерэг харилцан анхны тоонууд байна. Үсрэгч амьтны боломжит хамгийн өндөр үсрэлтийн өндөр нь $h$. Хэрвээ $h_{2} - h_{1} ≤ h$ байвал үсрэгч амьтан $h_{1}$ өндрөөс $h_{2}$ ($h_{1} < h_{2}$) өндөррүү үсэрч чадна. Анх үсрэгч газар дээр байсан буюу өндөр нь 0 байсан. Асуулт бол тэр хамгийн өндөр хавтгай дээр гарч чадах уу эсвэл үгүй юу.

Жишээлбэл $a = 7$, $n = 4$, $p = 12$, $h = 2$ үед хавтгайнуудын өндөр зурагт үзүүлсэнчлэн $7$, $2$, $9$, $4$ байна. Эхний үсрэлтэнд үсрэгч амьтан $2$ өндөртэй хавтгайруу үсэрч чадна, хоёрдугаар үсрэлтэнд үсрэгч амьтан $4$ өндөртэй хавтгайруу үсэрч чадна. Гэвч тэр үүнээс өндөр аль ч хавтгайруу үсэрч чадахгүй. Иймээс тэр хамгийн өндөр хавтгайруу үсэрч чадахгүй.

Хэрэглэгч шидао энэ бодлогын талаар удаан хугацааны туршид бодож байгаа боловч шийдэж чадаагүй байгаа иймд тэр таны тусламжийг хүсч байна. Мөн түүнд бодлогын маш олон тохиолдол байгаа. Таны ажил бол эдгээр бүх тохиолдлыг шийдэх явдал юм.

Оролт

Эхний мөрөнд бүхэл тоон утга $t$ $(1 ≤ t ≤ 10^{4})$ байх ба бодлогын тохиолдлуудын тоо. Дараагийн $t$ мөр бүрт дөрвөн бүхэл тоон утга $a$, $n$, $p$ ба $h$ ($1 ≤ a ≤ 10^{9}$, $1 ≤ n < p ≤ 10^{9}$, $0 ≤ h ≤ 10^{9}$) байна. Энд $a$ болон $p$ нь харилцан анхны байна.

Гаралт

Бодлогын тохиолдол бүрийн хувьд Үсрэгч амьтан хамгийн өндөр хавтгайд хүрч чадах бол "$YES$" гэж хэвлэ бусад тохиолдолд "$NO$" гэж хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3
7 4 12 2
7 1 9 4
7 4 12 3
Гаралт
NO
NO
YES
Сэтгэгдлүүдийг ачааллаж байна...