CF346E.Doodle Jump

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 _h_1 to height _h_2 (_h_1 < _h_2) if _h_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 = 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.

在《涂鸦跳跃》（Doodle Jump）中，玩家的目标是引导一个名为“涂鸦者”（The Doodler）的四足生物，在一系列永无止境的平台间不断向上跳跃，且不能坠落。——维基百科。

这是一款非常流行的游戏，小道非常喜欢它。某天，她在游玩时突然想到：由于涂鸦者跳跃能力有限，是否可能存在某个平台，使其永远无法抵达？请考虑如下问题：

共有 $n$ 个平台。第 $x$ 个平台（$1 \le x \le n$）的高度为 $a \cdot x \bmod p$，其中 $a$ 和 $p$ 是互质的正整数。涂鸦者单次跳跃所能达到的最大高度差为 $h$，即：若当前位于高度 $h_1$，则可跳至更高处的平台高度 $h_2$（$h_1 < h_2$），当且仅当 $h_2 - h_1 \le h$。初始时，涂鸦者位于地面，高度为 $0$。问题是：它能否抵达所有平台中最高的那个平台？

例如，当 $a = 7$、$n = 4$、$p = 12$、$h = 2$ 时，各平台高度依次为 $7, 2, 9, 4$，如下图所示。涂鸦者第一次跳跃可到达高度为 $2$ 的平台，第二次跳跃可到达高度为 $4$ 的平台；但此后无法再跳至任何更高的平台。因此，它无法抵达最高平台。

用户小道思考该问题许久却未能解决，于是向你求助。此外，她手头还有大量此类问题实例。你的任务是解决所有这些实例。

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 ≤ 109, 0 ≤ h ≤ 109). It's guaranteed that a and p are co-prime.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 问题实例的个数。接下来的 $t$ 行中，每行包含四个整数 $a$、$n$、$p$ 和 $h$（$1 \leq a \leq 10^9$，$1 \leq n < p \leq 10^9$，$0 \leq h \leq 10^9$）。保证 $a$ 与 $p$ 互质。

For each problem instance, if the Doodler can reach the highest platform, output "YES", otherwise output "NO".

对于每个问题实例，如果涂鸦者能够到达最高的平台，则输出 “YES”，否则输出 “NO”。