Угода?!
Угода?! — російська версія телевізійної гри 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) — суми, які залишились.
Вихідні дані
Для кожної ситуації виведіть математичне очікування виграшу гравця, а також розмір угоди, яку повинен запропонувати банкір гравцю. Обидва числа потрібно виводити округленими до двох знаків після коми.