Ultimate Football Formation Selection

In the year 3014, the World Cup is about to begin. As the coach of the defending champion Chinese football team, you have the privilege of choosing the strongest 11-man lineup for each game. In football, a lineup always consists of exactly 11 players: one goalkeeper and 10 outfield players. The outfield players are divided among defenders, midfielders, and forwards according to a given formation. A formation is specified in the format d-m-f (for example, 3-5-2, which means 3 defenders, 5 midfielders and 2 forwards) where the sum d + m + f = 10.

Every player specializes in exactly one position among the four: goalkeeper (G), defender (D), midfielder (M) and forward (F). In other words, a player can only be selected if his specialty matches the required position.

The coaching staff proposes Q formations in sequence. For the first formation, you choose the best available players from the entire pool. For the second formation, you select from the remaining players after removing those chosen for the first formation, and so on. For each formation, you must choose:

• 1 goalkeeper
• d defenders
• m midfielders
• f forwards

After selecting the required 11 players for each formation, output the average overall rating of the 11 chosen players. The average should be computed as:

$$\text{Average} = \frac{\text{sum of ratings of chosen players}}{11} $$

You can assume that the pool of players is sufficient to form every formation as required.

inputFormat

The first line contains two integers N and Q where N is the number of players and Q is the number of formations. The following N lines each contain an integer and a character separated by a space, representing the overall rating and the player's position respectively. The position is one of 'G', 'D', 'M', or 'F'. It is guaranteed that every player is specialized in exactly one position.

Following the player information, there are Q lines. Each line contains a formation string in the format d-m-f (for example, 3-5-2). Note that d + m + f = 10, because the goalkeeper (G) is not included in the formation string.

outputFormat

Output Q lines. Each line should contain the average overall rating of the 11 players selected for that formation. The average must be printed as a floating-point number with 6 decimal places.

sample

11 1
90 G
80 D
75 D
60 D
55 D
88 M
77 M
66 M
90 F
85 F
70 F
4-3-3

76.000000