| Codeforces Beta Round 90 |
|---|
| Закончено |
Через несколько минут Васе предстоит сдать первый в своей студенческой жизни экзамен — и не просто экзамен, а экзамен по математическому анализу. Разумеется, Вася сейчас думает только об одном: что его ждет при встрече с экзаменатором...
К экзамену необходимо было выучить доказательства n теорем. Известно, что на экзамене будет k билетов, в каждом из которых содержится 
различных теорем. Каждая теорема при этом входит не более чем в один билет (то есть 
теорем не попадут ни в один билет). В ходе экзамена один и тот же билет может достаться нескольким студентам.
Точное распределение теорем по билетам неизвестно, однако студенты, сдававшие экзамен до Васи, рассказали ему о содержании своих билетов. Сам Вася оценивает свой уровень знаний по i-ой теореме некоторым числом ai. Уровнем знаний по билету называется среднее арифметическое уровней знаний по всем теоремам из этого билета. Теперь на основе сведений, полученных от других студентов, Вася хочет определить минимально и максимально возможные уровни своих знаний по билету, который попадется ему на экзамене. К сожалению, у Васи уже нет времени на подсчеты, поэтому он попросил о помощи вас.
В первой строке записаны два целых числа n и k (1 ≤ k ≤ n ≤ 100) — количество теорем и количество билетов соответственно. Во второй строке содержится n целых чисел ai (0 ≤ ai ≤ 100), i-ое число (1 ≤ i ≤ n) соответствует уровню знаний Васи по i-ой теореме.
В третьей строке записано число q (0 ≤ q ≤ 100) — количество человек, сдававших экзамен до Васи. В каждой из последующих q строк находится описание билета очередного человека: целых чисел от 1 до n включительно — номера теорем из билета в соответствии с порядком их перечисления во входных данных. Номера могут быть заданы в произвольном порядке. Гарантируется, что заданные билеты корректны (то есть все теоремы в пределах одного билета различны, а билеты, доставшиеся разным людям, или не содержат одинаковых теорем, или совпадают с точностью до перестановки теорем).
Выведите два вещественных числа — минимальный и максимальный уровни знаний Васи по билету, который достанется ему на экзамене. Абсолютная или относительная погрешность не должна превосходить 10 - 6.
7 3
7 15 0 19 10 5 12
2
1 6
7 4
5.0000000000 15.5000000000
4 2
10 8 1 17
2
2 3
3 2
4.5000000000 13.5000000000
Разберем первый пример. Уровни знаний Васи по тем билетам, содержание которых уже известно, составляют 6 и 15.5 соответственно. Из оставшихся трех теорем можно сформировать только один билет. Рассмотрев все возможные варианты содержания этого билета, можно понять, что при наиболее благоприятном исходе экзамена Васе достанется билет, содержащий теоремы 4 и 7 (уровень знаний 15.5), а при наименее благоприятном — теоремы 3 и 5 (уровень знаний 5).
Операция ⌊ x⌋ обозначает взятие целой части вещественного числа x (округление вниз).
