CF346E.Doodle Jump
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
In Doodle Jump the aim is to guide a four-legged creature called "The Doodler" up a never-ending series of platforms without falling. — Wikipedia.
It is a very popular game and xiaodao likes it very much. One day when playing the game she wondered whether there exists a platform that the doodler couldn't reach due to the limits of its jumping ability. Consider the following problem.
There are n platforms. The height of the x -th ( 1<=x<=n ) platform is a⋅x mod p , where a and p are positive co-prime integers. The maximum possible height of a Doodler's jump is h . That is, it can jump from height h1 to height h2 ( h_{1}<h_{2} ) if h2−h1<=h . Initially, the Doodler is on the ground, the height of which is 0. The question is whether it can reach the highest platform or not.
For example, when a=7 , n=4 , p=12 , h=2 , the heights of the platforms are 7 , 2 , 9 , 4 as in the picture below. With the first jump the Doodler can jump to the platform at height 2 , with the second one the Doodler can jump to the platform at height 4 , but then it can't jump to any of the higher platforms. So, it can't reach the highest platform.
User xiaodao thought about the problem for a long time but didn't solve it, so she asks you for help. Also, she has a lot of instances of the problem. Your task is solve all of these instances.
输入格式
The first line contains an integer t (1<=t<=104) — the number of problem instances. Each of the next t lines contains four integers a , n , p and h ( 1<=a<=109 , 1<=n<p<=10^{9} , 0<=h<=109 ). It's guaranteed that a and p are co-prime.
输出格式
For each problem instance, if the Doodler can reach the highest platform, output "YES", otherwise output "NO".
输入输出样例
输入#1
3 7 4 12 2 7 1 9 4 7 4 12 3
输出#1
NO NO YES