Description

The 3014 World Cup is about to begin! As the coach of the defending champion, the Chinese national football team, every player under your command is a powerhouse. Figuring out the strongest 11-player lineup is a happy kind of trouble.

As is well known, the 11 players in a football lineup are each assigned to a particular position, which are mainly divided into four types: goalkeeper, defender, midfielder, and forward. There is exactly one goalkeeper, and the number of defenders, midfielders, and forwards depends on the formation you set. A formation is expressed as $A$-$B$-$C$ from defenders to forwards, not counting the goalkeeper. For example, a 3-5-2 formation means there are three defenders, five midfielders, and two forwards. Due to fierce competition, each player is trained only for one position, so each person can play only one of the four positions.

As a coach who knows the players’ abilities inside out, you have quantified each player’s overall rating. To better arrange the formations, your coaching team decides to use the following strategy to assign players: first, propose $Q$ formations in order, representing the first formation, the second formation, …, the $Q$-th formation. Then, for each formation, choose from the players not yet selected the best available numbers of goalkeeper(s), defenders, midfielders, and forwards. For example, for the first formation, select from all players; for the second formation, select from all players except those chosen for the first formation; for the third formation, select from all players except those chosen for the first and second formations; and so on.

Now that the $Q$ formations are fixed, what you need to know is the average overall rating for each formation.

Input Format

The first line contains four integers $K, D, M, F$, representing the number of available goalkeepers, defenders, midfielders, and forwards.

The second line contains $K$ integers $k_i$, representing the overall rating of each goalkeeper.

The third line contains $D$ integers $d_i$, representing the overall rating of each defender.

The fourth line contains $M$ integers $m_i$, representing the overall rating of each midfielder.

The fifth line contains $F$ integers $f_i$, representing the overall rating of each forward.

The sixth line contains an integer $Q$, representing the number of formations proposed by the coaching team.

Each of the following $Q$ lines contains three integers $A_i, B_i, C_i$ separated by spaces, indicating that the $i$-th formation is the $A_i$-$B_i$-$C_i$ formation.

Output Format

Output $Q$ lines. For the $i$-th formation, output a real number representing the maximum possible average overall rating for that formation, rounded to $2$ decimal places.

3 10 12 4
76 60 87
78 84 84 84 81 82 72 51 77 57
85 84 62 87 88 64 81 90 80 66 88 85
65 83 63 79
2
4 5 1
4 4 2

85.64
78.00

Hint

For $30\%$ testdata, $K, D, M, F \le 1000$, $Q \le 10$.

For $100\%$ testdata, $1 \le K, D, M, F \le 10^5$, $0 \le k_i, d_i, m_i, f_i \le 10^8$, $1 \le Q \le K$, $0 \le A_i, B_i, C_i \le 10$, $A_i + B_i + C_i = 10$, $\sum A_i \le D$, $\sum B_i \le M$, $\sum C_i \le F$.

Translated by ChatGPT 5