| Codeforces Round 201 (Div. 1) |
|---|
| Закончено |
Цель игры Doodle Jump — Главная цель игры — помочь «Дудлеру» (Doodler) взобраться как можно выше по платформам. — Wikipedia.
Это очень популярная игра и xiaodao обожает ее. Однажды она играла в игру и подумала: а есть ли платформа, до которой Дудлер не сможет допрыгнуть ввиду своей низкой прыгучести? Рассмотрим следующую задачу.
Есть n платформ. Высота x-ой (1 ≤ x ≤ n) платформы равняется a·x mod p, где a и p — положительные взаимно простые числа. Максимальная высота прыжка Дудлера равняется h. Иными словами, он может допрыгнуть с высоты h1 до высоты h2 (h1 < h2), если h2 - h1 ≤ h. Вначале Дудлер стоит на земле, где высота равна 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» в противном случае.
3
7 4 12 2
7 1 9 4
7 4 12 3
NO
NO
YES
