Problem: Vasya is about to take his first university exam in about several minutes. And it's not just some ordinary exam, it's on mathematical analysis. Of course, right now Vasya can only think of one thing: what the result of his talk with the examiner will be...

To prepare for the exam, one has to study proofs of n theorems. It is known that there will be k examination cards on the exam and each card contains <image> distinct theorems. Besides, no theorem is mentioned in more than one card (that is, <image> theorems won't be mentioned in any card). During the exam several students may get the same card.

We do not know the exact way theorems are distributed by cards, however the students that took the exam before Vasya told him what theorems their cards contained. Vasya evaluates his level of proficiency in the i-th theorem by some number ai. The level of proficiency in some card is the average of the levels of proficiency in the theorems that are included in the card. Now Vasya wants to know the minimally and maximally possible levels of his proficiency in the card he gets on the exam. Vasya wants to determine it by the data he has collected from other students. Unfortunately, Vasya has no time left to do the math and he asked you to help him.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 100) — the number of theorems and the number of cards correspondingly. The second line contains n integers ai (0 ≤ ai ≤ 100), the i-th number (1 ≤ i ≤ n) corresponds to Vasya's proficiency in the i-th theorem.

The third line contains number q (0 ≤ q ≤ 100) — the number of people that have taken the exam before Vasya. Each of the following q lines contains the description of a student's card: <image> integers from 1 to n inclusive. They are the numbers of theorems included in the card in the order in which they are enumerated in the input data. The numbers are given in an arbitrary order. It is guaranteed that the given cards are valid (that is, that all theorems in one card are different and that different people get cards that either don't contain the same theorems or coincide up to the theorems' permutation).

Output

Print two real numbers, representing Vasya's minimum and maximum proficiency in the card he will get on the exam. The absolute or relative error should not exceed 10 - 6.

Examples

Input

7 3
7 15 0 19 10 5 12
2
1 6
7 4


Output

5.0000000000 15.5000000000

Input

4 2
10 8 1 17
2
2 3
3 2


Output

4.5000000000 13.5000000000

Note

Let's analyze the first sample. Vasya's proficiency in the cards whose content he already knows equals 6 and 15.5 correspondingly. The three theorems that are left are only enough to make one exam card. If we consider all possible variants of theorems included in the card we can see that in the best case scenario Vasya gets the card that contains theorems 4 and 7 (his proficiency would equal 15.5) and in the worst case scenario he gets theorems 3 and 5 (his proficiency would equal 5).

The ⌊ x⌋ operation denotes taking integer part of real number x (rounding down).

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long int MOD = 1e9 + 7;
long long int INF = 1e18;
long long int power(long long int base, long long int exp) {
  long long int res = 1;
  while (exp > 0) {
    if (exp % 2 == 1) res = (res * base);
    base = (base * base);
    exp /= 2;
  }
  return res;
}
long long int bitc(long long int n, long long int x) { return ((n >> x) & 1); }
long long int __gcd(long long int a, long long int b) {
  return b == 0 ? a : __gcd(b, a % b);
}
long long int fsub(long long int a, long long int b, long long int p = MOD) {
  return ((a % p) - (b % p) + p) % p;
}
long long int fmult(long long int a, long long int b, long long int p = MOD) {
  return ((a % p) * (b % p)) % p;
}
long long int fadd(long long int a, long long int b, long long int p = MOD) {
  return (a % p + b % p) % p;
}
long long int fpow(long long int n, long long int k, long long int p = MOD) {
  long long int r = 1;
  while (k > 0) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
    k = k >> 1;
  }
  return r;
}
long long int inv(long long int a, long long int p = MOD) {
  return fpow(a, p - 2, p);
}
long long int fdiv(long long int a, long long int b, long long int p = MOD) {
  long long int yinv = inv(b);
  long long int ans = (a * yinv) % p;
  return ans;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &a) {
  for (auto &item : a) {
    in >> item;
  }
  return in;
}
template <typename T, typename U>
ostream &operator<<(ostream &out, pair<T, U> &a) {
  cout << a.first << " " << a.second;
  return out;
}
template <typename T, typename U>
istream &operator>>(istream &out, pair<T, U> &a) {
  cin >> a.first >> a.second;
  return out;
}
template <typename T, typename U>
ostream &operator<<(ostream &out, map<T, U> &a) {
  for (auto &item : a) {
    out << item << "\n";
  }
  return out;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &a) {
  for (auto &item : a) {
    out << item << " ";
  }
  return out;
}
template <typename T>
ostream &operator<<(ostream &out, vector<vector<T>> &a) {
  for (auto &item : a) {
    out << item << "\n";
  }
  return out;
}
template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
  static_assert(D >= 1, "Vector dimension must be greater than zero!");
  template <typename... Args>
  Vec(int n = 0, Args... args)
      : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};
template <typename T>
struct Vec<1, T> : public vector<T> {
  Vec(int n = 0, T val = T()) : vector<T>(n, val) {}
};
std::vector<bool> is_prime;
std::vector<long long int> primes;
void sieve(long long int n) {
  is_prime.resize(n + 2, true);
  primes.clear();
  long long int p;
  for (p = 2; p * p <= n; p++) {
    if (is_prime[p]) {
      long long int i;
      for (i = p * p; i <= n; i += p) {
        is_prime[i] = false;
      }
    }
  }
  is_prime[0] = is_prime[1] = false;
  long long int i;
  for (i = 2; i <= n; i++) {
    if (is_prime[i]) {
      primes.emplace_back(i);
    }
  }
}
map<long long int, long long int> prime_factors(long long int n) {
  map<long long int, long long int> s;
  long long int i;
  long long int tc = 0;
  while (n % 2 == 0) {
    tc++;
    n /= 2;
  }
  if (tc > 0) {
    s[2] = tc;
  }
  for (i = 3; i <= sqrt(n); i += 2) {
    tc = 0;
    while (n % i == 0) {
      tc++;
      n /= i;
    }
    if (tc > 0) {
      s[i] = tc;
    }
  }
  if (n > 2) {
    s[n] += 1;
  }
  return s;
}
std::vector<long long int> fact_vec;
void fact_fun(long long int n) {
  fact_vec.resize(n + 10);
  long long int i;
  fact_vec[0] = 1;
  for (i = 1; i <= n + 2; i++) {
    fact_vec[i] = (fact_vec[i - 1] * i) % MOD;
  }
}
std::vector<long long int> p2;
void power_2(long long int n, long long int m = MOD) {
  long long int i;
  MOD = m;
  p2.emplace_back(1);
  for (i = 0; i < n; i++) {
    p2.emplace_back(fmult(p2.back(), 2));
  }
}
long long int ncr(long long int n, long long int r) {
  if (r > n) return 0;
  return fdiv(fact_vec[n], fmult(fact_vec[r], fact_vec[n - r]));
}
std::vector<long long int> spf;
void sieve2(long long int MAXN) {
  MAXN += 10;
  spf.resize(MAXN, 0);
  spf[1] = 1;
  for (long long int i = 2; i < MAXN; i++) spf[i] = i;
  for (long long int i = 4; i < MAXN; i += 2) spf[i] = 2;
  for (long long int i = 3; i * i < MAXN; i++) {
    if (spf[i] == i) {
      for (long long int j = i * i; j < MAXN; j += i) {
        if (spf[j] == j) spf[j] = i;
      }
    }
  }
}
std::vector<long long int> getFactorization(long long int x) {
  std::vector<long long int> ret;
  while (x != 1) {
    ret.emplace_back(spf[x]);
    x = x / spf[x];
  }
  return ret;
}
int main() {
  long long int i, j;
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long int ti;
  ti = 1;
  while (ti--) {
    long long int n, k;
    cin >> n >> k;
    std::vector<long long int> v(n);
    cin >> v;
    long double mn = INF, mx = 0;
    set<long long int> s;
    for (i = 0; i < n; i++) {
      s.insert(i);
    }
    long long int qt;
    cin >> qt;
    long long int oa = qt;
    while (qt--) {
      std::vector<long long int> q(n / k);
      cin >> q;
      long long int sum = 0;
      bool cool = false;
      for (auto &p : q) {
        --p;
        sum += v[p];
        if (!s.count(p)) {
          oa--;
          cool = true;
          break;
        }
        s.erase(p);
      }
      if (cool) {
        continue;
      }
      mn = min(mn, (long double)sum / (n / k));
      mx = max(mx, (long double)sum / (n / k));
    }
    if (!s.empty() && k - oa > 0) {
      std::vector<long long int> vp;
      for (auto p : s) {
        vp.emplace_back(v[p]);
      }
      sort((vp).begin(), (vp).end());
      long long int sum = 0;
      for (i = 0; i < n / k && i < vp.size(); i++) {
        sum += vp[i];
      }
      mn = min(mn, (long double)sum / (n / k));
      mx = max(mx, (long double)sum / (n / k));
      sum = 0;
      long long int cnt = n / k;
      i = vp.size() - 1;
      while (cnt-- && i >= 0) {
        sum += vp[i];
        i--;
      }
      mn = min(mn, (long double)sum / (n / k));
      mx = max(mx, (long double)sum / (n / k));
    }
    cout << fixed << setprecision(9) << mn << " " << mx << "\n";
  }
}