There is a game called Genshin Impact and there are tons of characters in the game. Each character has the following attributes: name, attack damage and critical damage.

You are given a list of attacks of characters on Dvalin (aka. Stormterror) which is a strong boss in the game. Each of attack includes character's name and a number ~0~ or ~1~, ~1~ – the attack is a critical attack, ~0~ – not a critical attack. Your task is to write a program to print out the average amount of damage each character dealt of each attack on the boss.

Output damage formula:

• Output Damage = character's attack damage - If the attack is not a critical attack
• Output Damage = character's critical damage - If character landed a critical hit.
• Suppose that the boss has unlimited amount of Health Point (HP) which means it cannot die.

Input

• The first line contains two integers ~N~ - the number of attacks, ~M~ - the number of characters ~(1 \leq N, M \leq 10^5)~.
• Each line in the next ~M~ lines represents a character, contains a string, followed by two integers: ~CN_i, AD_i,~ and ~CD_i,~ which are the character's name, attack damage and critical damage. All integers don't exceed ~10^9~.
• Each line in the next ~N~ lines represents an attack, contains a string which is the character's name, followed by a number (~0~ or ~1~) to indicate a critical hit or a normal hit.

Output

• The required sorted list. Each line in the output contains the character's name and the average amount of damage of each attack (rounded to the unit) the character deals on the boss. The list should be sorted in descending order of the average amount of damage.
• If there are characters who have the same average amount of output damage, they should be sorted in ascending order of name.

Sample Input

5 2
Ayaka 1000 2000
RaidenShogun 900 1350
Ayaka 1
Ayaka 0
RaidenShogun 0
RaidenShogun 1
Ayaka 1

Sample Output

Ayaka 1667
RaidenShogun 1125

Explanation

• Ayaka attacks ~3~ times: critical hit, normal hit, and critical hit.
• Average Damage ~= (2000 + 1000 + 2000)/3 = 1667~.

https://drive.google.com/file/d/1mvM67vAJ1KGCH6V8iZyzr1pNgaNN0sdJ/view?usp=sharing