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, element type.

Suppose there are ~4~ elements in the game: Pyro, Hydro, Cryo, Electro. Each element can react with another element to create an elemental reaction which can highly boost the damage a character deals in that attack.

The elemental reaction's coefficient is listed as the table below:

You are given a list of attacks of characters on a boss. 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. On each attack turn, only one character can perform his/her attack. The list is already in the order of attack turn. Your task is to write a program to print out the top ~K~ character dealing the most total damage on the boss.

Output damage formula:

• Output Damage = character's attack damage * (~1~ + elemental reaction's coefficient) - If the attack is not a critical attack.
• Output Damage = character's critical damage * (~1~ + elemental reaction's coefficient) - If character landed a critical hit.

Explain on how elemental reaction works (check the sample below to see an example):

• On each attack, a character's attack will apply an element on the boss based on the character's element.
• When the boss is applied an element, an elemental reaction occurs if the next character's element is different from the boss's applied element.
• After an elemental reaction, the boss will have no applied element until a character attack it.

Suppose that the boss has unlimited amount of Health Point which means it cannot die.

Input

• The first line contains three integers ~N~ - the number of attacks, ~M~ - the number of characters, ~K~ ~(1 \leq N, M, K \leq 10^5)~.

• Each line in the next ~M~ lines represents a character, contains a string, followed by two integers, then followed by a string: ~CN_i, AD_i, CD_i~ and ~E_i~ which are the character's name, attack damage, critical damage and element type. 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 total amount of damage the character deals on the boss. The list should be sorted in descending order of the total amount of damage.
• Note that, if there are characters who have the same total amount of output damage as the Kth character's total damage, print them too and they should be sorted in ascending order of name.

Sample Input

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

Sample Output

Ayaka 5600
RaidenShogun 2520

Explanation

• Steps:

1. Ayaka performs critical attack (apply Cryo on boss)
2. Ayaka performs normal attack (no elemental reaction occur)
3. Raiden Shogun performs normal attack (elemental reaction: Superconduct occurs - Electro & Cryo)
   • Note that the boss now has no applied element due to elemental reaction occured (step 3)
4. Raiden Shogun performs critical attack (apply Electro on boss)
5. Ayaka performs critical hit (elemental reaction: Superconduct occurs - Cryo & Electro)

• Ayaka total damage: ~2000 + 1000 + 2000\times(1+0.3) = 5600~
• RaidenShogun total damage: ~900 \times (1+0.3) + 1350 = 2520~

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