[бобс]

Задача 1. «Алгоритм Евклида» (100 баллов)

Дима недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка.
Алгоритм Евклида заключается в следующем:
1.Пусть a, b — числа, НОД которых надо найти.
2.Если b = 0,то число a — искомый НОД.
3.Если b > a, то необходимо поменять местами числа a и b.
4.Присвоить числу a значение a – b.
5.Вернуться к шагу 2.
Дима достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Поняв, что надо дальше совершенствоваться, ему пришла идея решить новую задачу. Пусть заданы числа a, b, c и d. Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.
Требуется написать программу, которая решает эту задачу.
Формат входных данных
Первая строка входного файла содержит количество наборов входных данных k (1 ___8804; k ___8804; 100). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (1 ___8804; a, b ___8804; 1018). Вторая строка – два целых числа: c, d (1 ___8804; c, d ___8804; 1018).
Все числа в строках разделены пробелом.
Формат выходных данных
Для каждого набора входных данных выведите в отдельной строке выходного файла слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d), или слово «NO» – в противном случае.



Задача 2. «Преобразование последовательности» (100 баллов)

Задана последовательность, содержащая n целых чисел. Необходимо найти число, которое встречается в этой последовательности наибольшее количество раз, а если таких чисел несколько, то найти минимальное из них, и после этого переместить все такие числа в конец заданной последовательности. Порядок расположения остальных чисел должен остаться без изменения.
Например, последовательность 1, 2, 3, 2, 3, 1, 2 после преобразования должна превратиться в последовательность 1, 3, 3, 1, 2, 2, 2.
Требуется написать программу, которая решает названную задачу.
Формат входных данных
Первая строка входного файла содержит число n — количество чисел во входной последовательности (3 ___8804; n ___8804; 200000). Следующая строка содержит входную последовательность, состоящую изn целых чисел, не превышающих по модулю 109. Все числа в строке разделены пробелом.
Формат выходных данных
В выходной файл выводится последовательность чисел, которая получается в результате названного преобразования. Все числа в последовательности должны быть разделены пробелом.