Задание1:
Джон Доу предложил своей сестре Джейн Доу найти gcd некоторого набора чисел a.

Gcd — это целое положительное число g такое, что все числа из набора делятся на g нацело и не существует g' (g'?>?g), такого, что все числа набора делятся на g' нацело.

К сожалению, Джейн не смогла справиться с заданием и Джон предложил ей найти ghd того же набора чисел.

Ghd — это целое положительное число g такое, что не менее половины чисел из набора делятся на g нацело и не существует g' (g'?>?g), такого, что не менее половины чисел из набора делятся на g' нацело.

С таким заданием Джейн справилась всего за два часа. Попробуйте и вы.
Входные данные

В первой строке записано целое число n (1???n???106) — количество чисел в наборе a. Во второй строке через пробел записаны целые числа a1,?a2,?...,?an (1???ai???1012). Обратите внимание, среди чисел могут быть одинаковые.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать спецификатор %I64d.
Выходные данные

Выведите единственное число g — ghd набора a.

Примеры тестов:
Входные данные

6
6 2 3 4 5 6

Выходные данные

3

Входные данные

5
5 5 6 10 15

Выходные данные

5
/////////////////////////////////////////////////////////////////////////////////////////////////////////
Задание 2:
У ослика Иа-Иа сегодня день рождения. Его друг, Винни-Пух, хочет сделать ему самый лучший подарок — горшочек меда. Конечно, медвежонок понимает, что полный горшочек до ослика донести не удастся, потому что по пути он съест весь мед. А раз уж Винни собрался перекусить по пути, то изначально в горшочке должно быть как можно больше меда.

За день до этого Винни-Пух пополнил свои запасы меда. Дома у Винни-Пуха есть n полок, на каждой из которых находится некоторое, возможно нулевое, количество горшочков с медом. В течение дня Винни q раз подходил к полкам с медом; в i-тый раз он подходил к некоторой полке ui, брал с нее некоторое количество горшочков ki, пробовал мед из каждого из них и ставил все эти горшочки на некоторую полку vi. Выбирая горшочки, Винни руководствовался интуицией, а, значит, можно считать, что среди всех наборов из ki горшочков на полке ui, он равновероятно выбирает один.

Сейчас Винни помнит все действия, которые он выполнял с горшочками меда. На праздник он хочет взять горшочек, который вчера ему не попадался. Для этого ему необходимо знать математическое ожидание m количества полок, на которых нет ни одного нетронутого медвежонком горшочка. Для того, чтобы лучше оценить свои шансы, Винни-Пух хочет знать значение m после каждого выполненного им действия.

Ваша задача — написать программу, которая найдет эти значения за него.
Входные данные

Первая строка входных данных содержит единственное целое число n (1???n???105) — количество полок у Винни-Пуха дома. Вторая строка содержит n целых чисел ai (1???i???n, 0???ai???100) — количество горшочков с медом на полке с номером i.

В следующей строке содержится целое число q (1???q???105) — количество действий, которое выполнил Винни за предыдущий день. Далее следует q строк, i-ая из которых описывает очередное в хронологическом порядке действие и содержит три целых числа ui, vi и ki (1???ui,?vi???n, 1???ki???5) — номер полки, с которой Винни взял горшочки, номер полки, на которую Винни поставил горшочки после того, как попробовал мед из каждого из них, и количество горшочков, из которых Винни-Пух попробовал мёд, соответственно.

Считайте, что полки с горшочками пронумерованы целыми числами от 1 до n. Гарантируется, что Винни-Пух никогда не пытался брать с полки больше горшков, чем на ней находится.
Выходные данные

Для каждого действия Винни-Пуха выведите величину математического ожидания m на момент окончания выполнения этого действия. Относительная или абсолютная погрешность каждого значения не должна превышать 10?-?9.
Примеры тестов
Входные данные

3
2 2 3
5
1 2 1
2 1 2
1 2 2
3 1 1
3 2 2

Выходные данные

0.000000000000
0.333333333333
1.000000000000
1.000000000000
2.000000000000