Задача №1391. Шестеренки
На каждой из трех осей установлено по одной вращающейся шестеренке и неподвижной стрелке. Шестеренки соединены последовательно. На первой шестеренке n зубцов, на второй — m, на третьей — k. На каждом зубце первой, второй и третьей шестеренок по часовой стрелке написаны в порядке возрастания числа от 1 до n, от 1 до m и от 1 до k соответственно. Стрелки зафиксировали таким образом, что когда стрелка первой оси указывает на число, стрелки двух других осей также указывают на числа. Витя записывает три числа (a1,a2,a3), на которые указывают стрелки. После этого он поворачивает первую шестеренку на угол 360°/n против часовой стрелки, чтобы напротив стрелки на первой оси оказался следующий (по часовой стрелке) зубец. При этом вторая шестеренка поворачивается на угол 360°/m по часовой стрелке (размеры зубцов у шестеренок одинаковые, поэтому размеры самих шестеренок разные, чтобы на границе шестеренок равномерно уложилось разное число одинаковых по размеру зубцов), а третья шестеренка поворачивается на угол 360°/k против часовой стрелки. Витя опять записывает три числа, на которые указывают стрелки.
Поступая и далее таким образом, Витя заметил, что после некоторого количества таких действий стрелки показывают на три первоначальных числа.
Теперь его очень интересует, как по двум данным тройкам чисел определить, принадлежат ли они к одной последовательности, то есть можно ли некоторым количеством поворотов перейти от первой тройки ко второй. Он попросил вас написать программу, которая отвечает на этот вопрос.
В первой строке содержатся четыре числа T, n, m, k (1 ≤ T ≤ 10, 1 ≤ n, m, k ≤ 1018) — количество пар троек, которые хочет проверить Витя и количества зубцов соответственно на первой, второй и третьей шестеренках.
В следующих T строках записаны шесть натуральных чисел a1, a2, a3, b1, b2, b3 (1 ≤ a1, b1 ≤ n, 1 ≤ a2, b2 ≤ m, 1 ≤ a3, b3 ≤ k).
Для каждой пары троек в выходной файл выведите YES, если обе тройки принадлежат одной последовательности, и NO иначе. Каждое слово должно быть в отдельной строке, в порядке, соответствующем входному файлу.
Комментарии к примерам тестов
1. В первой и второй парах вторая тройка получается из первой за один поворот первой шестеренки против часовой стрелки.
В третьем случае из второй конфигурации просто получить первую опять же одним поворотом первой шестеренки против часовой стрелки.
Очевидно, что тогда из первой можно каким-то образом получить вторую.
2. В первой паре тройки нельзя перевести друг в друга.
Во второй тройки переходят друг в друга при одном повороте.
3. (1, 1, 1) — (семь поворотов первой против часовой стрелки шестеренки) — (1, 4, 2) — (еще семь таких же поворотов) — (1, 2, 3) — (один поворот) — (2, 1, 1)
Частичные ограничения
Первая группа состоит из тестов, в которых произведение nmk ≤ 106.
Вторая группа состоит из тестов, в которых n, m, k ≤ 109.
Примечание
Не гарантируется, что описанную в условии задачи систему шестеренок и стрелок можно реально построить.
3 11 13 15 5 5 5 6 4 6 11 13 15 1 12 1 2 13 2 1 1 1
YES YES YES
2 2 2 2 1 1 1 1 1 2 1 1 1 2 2 2
NO YES
1 7 5 3 1 1 1 2 1 1
YES