← 返回题目列表

Codeforces · 346/E

E. 涂鸦跳跃

中文机器翻译题面 查看原题

在《Doodle Jump》中,目标是引导一种名为“The Doodler”的四足生物在一系列永无休止的平台上攀爬而不坠落。 ——维基百科。

这是一款非常受欢迎的游戏,小刀非常喜欢它。有一天,她在玩游戏时想知道是否存在一个涂鸦者由于跳跃能力的限制而无法到达的平台。考虑以下问题。

有n个平台。第 x (1 ≤ x ≤ n) 平台的高度为 a·x mod p,其中 a 和 p 是正互质整数。涂鸦者跳跃的最大可能高度为 h。也就是说,如果 h2 - h1 ≤ h,它可以从高度 h1 跳跃到高度 h2 (h1 < h2)。最初,涂鸦者在地面上,高度为0。问题是它能否到达最高的平台。

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

用户xiaodao想了很久没有解决这个问题,所以向您寻求帮助。而且,她有很多这个问题的例子。你的任务是解决所有这些情况。

输入

第一行包含一个整数 t (1 ≤ t ≤ 104) — 问题实例的数量。接下来的 t 行每行包含四个整数 a、n、p 和 h (1 ≤ a ≤ 109, 1 ≤ n < p ≤ 109, 0 ≤ h ≤ 109)。保证a和p互质。

输出

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

示例

输入 #1

3
7 4 12 2
7 1 9 4
7 4 12 3

输出 #1

NO
NO
YES