Сделка?!
Сделка?! — российская версия телевизионной игры Deal or No Deal, выходящей во многих странах мира. Рассмотрим правила этой игры. В начале игры есть n чемоданов с различными суммами денег. Никто, кроме непосредственно того, кто раскладывал суммы, не знает какая сумма в каком чемодане. Игрок выбирает чемодан и берет себе, но не открывает. Далее игрок начинает открывать оставшиеся чемоданы в любом порядке. Тут в игру вступает банкир. Перед каждым открытием чемодана банкир предлагает игроку сделку. Банкир предлагает игроку некоторую сумму денег. Если игрок соглашается, он забирает деньги, предложенные банкиром, и заканчивает игру. Если нет, то он продолжает открывать чемоданы. Когда в игре остаются два чемодана, если игрок отказывается от сделки, он может выбрать один из чемоданов и забрать его содержимое. В любом случае игрок уходит с некоторой суммой. Его задача выиграть больше. Задача банкира заставить игрока забрать сумму поменьше. Будем считать, что банкир исходит из следующей модели поведения игрока. Если банкир предлагает игроку денег, то вероятность, что игрок заберет эту сумму, равна:
где min и max — минимальная и максимальная суммы, которые остались в игре соответственно. Помогите банкиру вычислить математическое ожидание того, что заберет игрок.
Входные данные
Первая строка входного файла содержит n (2 ≤ n ≤ 16) — общее количество чемоданов. В следующей строке записаны целые числа a_1, a_2, ..., a_n — суммы в каждом чемодане. Далее идет число q (1 ≤ q ≤ 100) — количество ситуаций, которые интересуют банкира. В следующих строках идут описания каждой ситуации: k (2 ≤ k ≤ n) — количество оставшихся в игре сумм; b_1, b_2, ..., b_k (1 ≤ a_i, b_i ≤ 10^6) — суммы, которые остались.
Для каждой ситуации выведите математическое ожидание выигрыша игрока, а также размер сделки, которую должен предложить банкир игроку. Оба числа нужно выводить округленными до двух знаков после запятой.