Deal or No Deal is played in many different ways around the world. Many different countries have their own version or versions of the show, each with their own twists on the same general format. The general format is the following.

The game revolves around the opening of a set of numbered briefcases, each of which contains a different prize (cash or otherwise). The contents of all of the cases are known at the start of the game, but the specific location of any prize is unknown. The value of each of the cases is indicated by a label or card sealed within it. The contestant claims (or is assigned) a case to begin the game. The case's value is not revealed until the conclusion of the game.

The contestant then begins choosing cases to be removed from play. The amount inside each choice is immediately revealed; by process of elimination, the amount revealed cannot be inside the player's chosen case. Throughout the game, after a predetermined number of cases have been opened, the banker offers the contestant an amount of money and/or prizes to quit the game, the offer based roughly on the amounts remaining in play and the contestant's demeanor. The player then answers the titular question, choosing:

• "Deal", accepting the offer presented and ending the game, or
• "No Deal", rejecting the offer and continuing the game.

This process of removing cases and receiving offers continues, until either the player accepts an offer to 'deal', or all offers have been rejected and the values of all unselected cases are revealed. The player wins the value of the deal taken, or if no deal is taken, the contents of the player's case.

For the sake of this problem we will consider that the banker offers are deal before each removing of cases. Also we will assume that banker follows the particular model of contestants behaviour which is - if the banker offers the contestant the prize x the probability that the contestant accepts the deal is:

where min and max are the minimum and maximum prizes left in the game respectively. The banker wants to minimize the expexted prize the contestant wins. Help the banker calculate the expected prize the contestant is going to win if the banker offers optimal deals.

Input

The first line of input is n - the number of briefcases. Next lines consists of n integers a₁, a₂, …, a_n - the prizes in the briefcases. Number q follows - the amount of situations the banker needs to evaluate. The description of each sitation follows: k – the number of prizes still in the game; b₁, b₂, …, b_k – the prizes themselves.

Constraints

2 <= n <= 16
1 <= q <= 100
2 <= k <= n
1 <= a_i, b_i <= 10⁶

Output

For each situation print the expected prize the contestant is going to win and also the optimal deal the banker should offer. Both numbers should be printed with two digits after the dot.

Example

Input:
4
10 20 30 40
4
2 10 20
2 20 30
2 40 10
4 20 30 10 40

Output:
14.59 12.66
24.59 22.66
23.76 17.99
22.40 17.08