Имеется набор данных, состоящий из пар положительных целых чисел. Для каждой пары чисел находится значение А – наибольший общий делитель.
Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять, какое значение А встречалось чаще всего. Если несколько значений А встречается одинаковое наибольшее количество раз, вывести их в порядке убывания.
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 100 килобайт.
Входные данные
На вход программе в первой строке подаётся количество пар N (\(1 <= N <= 100000\)). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000.