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 nn platforms. The height of the xx -th ( 1<=x<=n1<=x<=n ) platform is axa·x mod pp , where aa and pp are positive co-prime integers. The maximum possible height of a Doodler's jump is hh . That is, it can jump from height h1h_{1} to height h2h_{2} ( h_{1}<h_{2} ) if h2h1<=hh_{2}-h_{1}<=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=7a=7 , n=4n=4 , p=12p=12 , h=2h=2 , the heights of the platforms are 77 , 22 , 99 , 44 as in the picture below. With the first jump the Doodler can jump to the platform at height 22 , with the second one the Doodler can jump to the platform at height 44 , 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 tt (1<=t<=104)(1<=t<=10^{4}) — the number of problem instances. Each of the next tt lines contains four integers aa , nn , pp and hh ( 1<=a<=1091<=a<=10^{9} , 1<=n<p<=10^{9} , 0<=h<=1090<=h<=10^{9} ). It's guaranteed that aa and pp 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
    
首页