D. Damage Calculator
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Aaron is teaching his little brother, Michael, about Pokermon battling! There are two types of Pokermons in the Pokerverse: attacking Pokermons and defending Pokermons. Attacking Pokermons can use attacks to deal damage to defending Pokermons. Each attacking Pokermon has an $$$\textit{Atk}$$$ value and can use four attacks. An attack has a base power that determines how much damage the attack will deal (referred to as $$$\textit{BP}$$$ below) and one of five elemental types (Fire, Water, Grass, Electric, or Ground). The damage dealt by an attack is proportional to both the $$$\textit{Atk}$$$ of the attacking Pokermon and the $$$\textit{BP}$$$ of the attack.

Defending Pokermons, on the other hand, cannot deal damage. Instead, they have a $$$\textit{Def}$$$ value, which is inversely proportional to the damage received, and an elemental type (also one of Fire, Water, Grass, Electric, or Ground). The elemental types of the attack used and the defending Pokermon affect how much damage is dealt. A $$$\textit{TypeEffectiveness}$$$ value is assigned for each pair of elemental types, and the damage dealt will be multiplied by the $$$\textit{TypeEffectiveness}$$$ of the two types. Below is a chart of $$$\textit{TypeEffectiveness}$$$ between all pairs of elemental types:

For example, the damage dealt by Fire-type attacks towards Water-type defending Pokermons will be halved (as Fire-type attacks have a $$$\textit{TypeEffectiveness}$$$ of $$$\frac{1}{2}$$$ towards Water-type defending Pokermons). Electric-type attacks will deal no damage to Ground-type defending Pokermons.

In summary, the damage that an attacking Pokermon can deal with a certain attack is calculated as follows:

$$$\textit{Damage} = \textit{BP} \times \frac{\textit{Atk}}{\textit{Def}} \times \textit{TypeEffectiveness}$$$,

As deciding on the best Pokermon and attack to use is the key to success in Pokermon battling, Aaron prepared a challenge for Michael: he will first give Michael $$$N$$$ attacking Pokermons, providing him with their $$$\textit{Atk}$$$ value, along with the $$$\textit{BP}$$$ and the elemental type for each of the four attacks they can use. Then, he will ask Michael $$$Q$$$ questions in the following way: he will specify a defending Pokermon's $$$\textit{Def}$$$ value and elemental type. Given that Michael can choose one Pokermon from his $$$N$$$ attacking Pokermons and use one of its attacks, what is the maximum damage that can be dealt to this defending Pokermon?

Input

The first line of the input consists of two integers $$$N$$$ $$$(1 \leq N \leq 2 \times 10^4)$$$ and $$$Q$$$ $$$(1 \leq Q \leq 2 \times 10^4)$$$, representing the number of Pokermons Aaron gave Michael and the number of questions Aaron asked Michael.

Then, $$$N$$$ groups of input follow with the following format:

  • The first line of the $$$i^{th}$$$ group consists of an integer $$$A_i$$$ $$$(1 \leq A_i \leq 1000)$$$, representing the $$$\textit{Atk}$$$ value of the $$$i^{th}$$$ attacking Pokermon.
  • The next four lines each consist of one character $$$M_{i,j}$$$ and an integer $$$B_{i,j}$$$ $$$(0 \leq B_{i,j} \leq 1000)$$$, representing the elemental type and the $$$\textit{BP}$$$ of the $$$j^{th}$$$ attack of the $$$i^{th}$$$ attacking Pokermon. $$$M_{i,j}$$$ will be one of F (Fire), W (Water), L (Grass), E (Electric), or G (Ground).

$$$Q$$$ lines of input then follow: the $$$i^{th}$$$ line consists of a character $$$T_i$$$ and an integer $$$D_i$$$ $$$(1 \leq D_i \leq 1000)$$$, representing the elemental type and the $$$\textit{Def}$$$ value of the $$$i^{th}$$$ defending Pokermon. $$$T_i$$$ will be one of F (Fire), W (Water), L (Grass), E (Electric), or G (Ground).

Output

The output should consist of $$$Q$$$ lines, each consisting of one floating point number. The $$$i^{th}$$$ number should be the maximum damage that can be dealt to the $$$i^{th}$$$ defending Pokermon. Your answer will be considered correct with absolute or relative error less than $$$10^{-6}$$$.

Examples
Input
2 1
10
F 10
W 10
L 10
G 10
15
F 5
W 6
L 7
G 8
E 10
Output
24.0000000000
Input
3 3
3
F 22
E 29
G 9
F 28
16
F 19
W 17
L 19
W 17
9
E 30
W 4
W 9
E 11
G 27
F 31
W 7
Output
22.5185185185
17.5483870968
86.8571428571
Note

For Sample 1, there is only one defending Pokermon with Electric type and a $$$\textit{Def}$$$ value of $$$10$$$. The four attacks of the first attacking Pokermon will deal $$$10$$$, $$$10$$$, $$$10$$$, and $$$20$$$ damage to the defending Pokermon respectively, and the four attacks of the second attacking Pokermon will deal $$$7.5$$$, $$$9$$$, $$$10.5$$$, and $$$24$$$ damage to the defending Pokermon respectively. Therefore, the maximum amount of damage that can be dealt is $$$24$$$.