Problem: Each item in the game has a level. The higher the level is, the higher basic parameters the item has. We shall consider only the following basic parameters: attack (atk), defense (def) and resistance to different types of impact (res).

Each item belongs to one class. In this problem we will only consider three of such classes: weapon, armor, orb.

Besides, there's a whole new world hidden inside each item. We can increase an item's level travelling to its world. We can also capture the so-called residents in the Item World

Residents are the creatures that live inside items. Each resident gives some bonus to the item in which it is currently located. We will only consider residents of types: gladiator (who improves the item's atk), sentry (who improves def) and physician (who improves res).

Each item has the size parameter. The parameter limits the maximum number of residents that can live inside an item. We can move residents between items. Within one moment of time we can take some resident from an item and move it to some other item if it has a free place for a new resident. We cannot remove a resident from the items and leave outside — any of them should be inside of some item at any moment of time.

Laharl has a certain number of items. He wants to move the residents between items so as to equip himself with weapon, armor and a defensive orb. The weapon's atk should be largest possible in the end. Among all equipping patterns containing weapon's maximum atk parameter we should choose the ones where the armor’s def parameter is the largest possible. Among all such equipment patterns we should choose the one where the defensive orb would have the largest possible res parameter. Values of the parameters def and res of weapon, atk and res of armor and atk and def of orb are indifferent for Laharl.

Find the optimal equipment pattern Laharl can get.

Input

The first line contains number n (3 ≤ n ≤ 100) — representing how many items Laharl has.

Then follow n lines. Each line contains description of an item. The description has the following form: "name class atk def res size" — the item's name, class, basic attack, defense and resistance parameters and its size correspondingly. 

  * name and class are strings and atk, def, res and size are integers. 
  * name consists of lowercase Latin letters and its length can range from 1 to 10, inclusive. 
  * class can be "weapon", "armor" or "orb". 
  * 0 ≤ atk, def, res ≤ 1000. 
  * 1 ≤ size ≤ 10. 



It is guaranteed that Laharl has at least one item of each class.

The next line contains an integer k (1 ≤ k ≤ 1000) — the number of residents.

Then k lines follow. Each of them describes a resident. A resident description looks like: "name type bonus home" — the resident's name, his type, the number of points the resident adds to the item's corresponding parameter and the name of the item which currently contains the resident. 

  * name, type and home are strings and bonus is an integer. 
  * name consists of lowercase Latin letters and its length can range from 1 to 10, inclusive. 
  * type may be "gladiator", "sentry" or "physician". 
  * 1 ≤ bonus ≤ 100. 



It is guaranteed that the number of residents in each item does not exceed the item's size.

The names of all items and residents are pairwise different.

All words and numbers in the input are separated by single spaces.

Output

Print on the first line the name of the weapon in the optimal equipping pattern; then print the number of residents the weapon contains; then print the residents' names.

Print on the second and third lines in the same form the names of the armor and defensive orb as well as the residents they contain. 

Use single spaces for separation.

If there are several possible solutions, print any of them.

Examples

Input

4
sword weapon 10 2 3 2
pagstarmor armor 0 15 3 1
iceorb orb 3 2 13 2
longbow weapon 9 1 2 1
5
mike gladiator 5 longbow
bobby sentry 6 pagstarmor
petr gladiator 7 iceorb
teddy physician 6 sword
blackjack sentry 8 sword


Output

sword 2 petr mike 
pagstarmor 1 blackjack 
iceorb 2 teddy bobby 


Input

4
sword weapon 10 2 3 2
pagstarmor armor 0 15 3 1
iceorb orb 3 2 13 2
longbow weapon 9 1 2 1
6
mike gladiator 5 longbow
bobby sentry 6 pagstarmor
petr gladiator 7 iceorb
teddy physician 6 sword
blackjack sentry 8 sword
joe physician 6 iceorb


Output

longbow 1 mike 
pagstarmor 1 bobby 
iceorb 2 petr joe 

Note

In the second sample we have no free space inside the items, therefore we cannot move the residents between them.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class Main {
	
	private static class Thing{
		String name;
		String className;
		int atk;
		int def;
		int res;
		int size;
		public Thing(String name,String className,int atk,int def,int res,int size){
			this.name = name;
			this.className = className;
			this.atk = atk;
			this.def = def;
			this.res = res;
			this.size = size;
		}
		
		public boolean equals(Object o){
			if(o!=null && o instanceof Thing){
				Thing th = (Thing)o;
				return name.equals(th.name);
			}
			return false;
		}
		public int hashCode(){
			return name.hashCode();
		}
	}
	
	private static class Resident{
		String name;
		String type;
		String home;
		int bonus;
		public Resident(String name,String type,int bonus,String home){
			this.name = name;
			this.type = type;
			this.home = home;
			this.bonus = bonus;
		}
		public boolean equals (Object o){
			if(o != null && o instanceof Resident){
				Resident res = (Resident)o;
				return name.equals(res.name);
			}
			return false;
		}
		public int hashCode(){
			return name.hashCode();
		}
	}
	
	private static final String RES_ATK = "gladiator";
	private static final String RES_DEF = "sentry";
	private static final String RES_RES = "physician";
	private static final String THG_WEAPON = "weapon";
	private static final String THG_ARMOR = "armor";
	private static final String THG_ORB = "orb";
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		ArrayList<Thing> weapons = new ArrayList<Thing>();
		ArrayList<Thing> armors = new ArrayList<Thing>();
		ArrayList<Thing> orbs = new ArrayList<Thing>();
		String[]parts = null;
		int places = 0;
		for(int i = 0; i < n; i++){
			parts = br.readLine().split("\\s+");
			Thing thing = new Thing(parts[0], parts[1], Integer.parseInt(parts[2]), Integer.parseInt(parts[3]), Integer.parseInt(parts[4]), Integer.parseInt(parts[5]));
			if(thing.className.equals(THG_WEAPON)){
				weapons.add(thing);
			}
			else if(thing.className.equals(THG_ARMOR)){
				armors.add(thing);
			}
			else{
				orbs.add(thing);
			}
			places += thing.size;
		}
		int k = Integer.parseInt(br.readLine());		
		HashMap<String, Resident> residentsMap = new HashMap<String, Resident>();
		ArrayList<String> ordAtk = new ArrayList<String>();
		ArrayList<String> ordDef = new ArrayList<String>();
		ArrayList<String> ordRes = new ArrayList<String>();
		HashMap<String, ArrayList<String>> initialResidentsInThing = new HashMap<String, ArrayList<String>>();
		for(int i = 0; i < k; i++){
			parts = br.readLine().split("\\s+");
			Resident resident = new Resident(parts[0], parts[1], Integer.parseInt(parts[2]), parts[3]);
			residentsMap.put(resident.name, resident);
			
			ArrayList<String> list = initialResidentsInThing.get(resident.home);
			if(list==null){
				list = new ArrayList<String>();
			}
			list.add(resident.name);
			initialResidentsInThing.put(resident.home,list);
			
			ArrayList<String> myList = null;
			if(resident.type.equals(RES_ATK)){
				myList = ordAtk;
			}
			else if(resident.type.equals(RES_DEF)){
				myList = ordDef;				
			}
			else {
				myList = ordRes;
			}
			boolean isIns = false;
			int cnt = 0;
			for(String resName : myList){
				Resident concurrent = residentsMap.get(resName);
				if(concurrent.bonus<resident.bonus){
					myList.add(cnt,resident.name);
					isIns = true;
					break;
				}
				cnt++;
			}
			if(!isIns){
				myList.add(resident.name);
			}
		}
		//not possible to move
		if(places==k){
			StringBuffer sb = new StringBuffer();

			int maxWeapon = Integer.MIN_VALUE; 
			String weaponName = null;
			for(Thing weapon : weapons){
				int rating = weapon.atk;
				for(String resName : ordAtk){
					Resident res = residentsMap.get(resName);
					if(res.home.equals(weapon.name)){
						rating += res.bonus;
					}
				}
				if(maxWeapon<rating){
					maxWeapon = rating;
					weaponName = weapon.name;
				}
			}
			sb = new StringBuffer();
			for(String resName : initialResidentsInThing.get(weaponName)){
				sb.append(" " + resName);
			}
			System.out.println(weaponName + " " + initialResidentsInThing.get(weaponName).size() + sb.toString());			

			int maxArmor = Integer.MIN_VALUE; 
			String armorName = null;
			for(Thing armor : armors){
				int rating = armor.def;
				for(String resName : ordDef){
					Resident res = residentsMap.get(resName);
					if(res.home.equals(armor.name)){
						rating += res.bonus;
					}
				}
				if(maxArmor<rating){
					maxArmor = rating;
					armorName = armor.name;
				}
			}
			sb = new StringBuffer();
			for(String resName : initialResidentsInThing.get(armorName)){
				sb.append(" " + resName);
			}
			System.out.println(armorName + " " + initialResidentsInThing.get(armorName).size() + sb.toString());
			
			int maxOrb = Integer.MIN_VALUE; 
			String orbName = null;
			for(Thing orb : orbs){
				int rating = orb.res;
				for(String resName : ordRes){
					Resident res = residentsMap.get(resName);
					if(res.home.equals(orb.name)){
						rating += res.bonus;
					}
				}
				if(maxOrb<rating){
					maxOrb = rating;
					orbName = orb.name;
				}
			}
			sb = new StringBuffer();
			for(String resName : initialResidentsInThing.get(orbName)){
				sb.append(" " + resName);
			}
			System.out.println(orbName + " " + initialResidentsInThing.get(orbName).size() + sb.toString());
			
		}
		else{
			int count = 0;
			
			Set<String> occupiedResidents = new HashSet<String>();
			
			int maxAtk = Integer.MIN_VALUE;
			HashMap<Integer, ArrayList<Thing>> weaponsByAtk = new HashMap<Integer, ArrayList<Thing>>();
			for(Thing thing : weapons){
				int currAtk = thing.atk;
				count = 0;
				for(String resName : ordAtk){
					if(count++>=thing.size)break;
					Resident res = residentsMap.get(resName);
					currAtk += res.bonus;
				}
				if(currAtk>maxAtk)maxAtk = currAtk;
				ArrayList<Thing> arrayThings = weaponsByAtk.get(currAtk);
				if(arrayThings==null){
					arrayThings = new ArrayList<Thing>();
				}
				arrayThings.add(thing);
				weaponsByAtk.put(currAtk, arrayThings);
			}
			ArrayList<Thing> maxWeapons = weaponsByAtk.get(maxAtk);
			Thing maxWeapon = maxWeapons.get(0);
			int countResidentsForWeapon = 0;
			ArrayList<String> resultingResidentsForWeapon = new ArrayList<String>();
			for(String resName : ordAtk){
				if(countResidentsForWeapon+1>maxWeapon.size)break;
				++countResidentsForWeapon;
				Resident res = residentsMap.get(resName);
				resultingResidentsForWeapon.add(res.name);
				occupiedResidents.add(res.name);
			}
			//System.out.println(maxWeapon.name + " " + count + resultingResidentsForWeapon.toString());
			
			int maxDef = Integer.MIN_VALUE;
			HashMap<Integer, ArrayList<Thing>> armorsByDef = new HashMap<Integer, ArrayList<Thing>>();
			for(Thing thing : armors){
				int currDef= thing.def;
				count = 0;
				for(String resName : ordDef){
					if(count++>=thing.size)break;
					Resident res = residentsMap.get(resName);
					currDef += res.bonus;
				}
				if(currDef>maxDef)maxDef = currDef;
				ArrayList<Thing> arrayThings = armorsByDef.get(currDef);
				if(arrayThings==null){
					arrayThings = new ArrayList<Thing>();
				}
				arrayThings.add(thing);
				armorsByDef.put(currDef, arrayThings);
			}
			ArrayList<Thing> maxArmors = armorsByDef.get(maxDef);
			Thing maxArmor = maxArmors.get(0);
			int countResidentsForArmor = 0;
			ArrayList<String> resultingResidentsForArmor = new ArrayList<String>();
			for(String resName : ordDef){
				if(countResidentsForArmor+1>maxArmor.size)break;
				++countResidentsForArmor;
				Resident res = residentsMap.get(resName);
				resultingResidentsForArmor.add(res.name);
				occupiedResidents.add(res.name);
			}
			//System.out.println(maxArmor.name + " " + count + resultingResidentsForArmor.toString());
			
			int maxRes = Integer.MIN_VALUE;
			HashMap<Integer, ArrayList<Thing>> ordByRes = new HashMap<Integer, ArrayList<Thing>>();
			for(Thing thing : orbs){
				int currRes= thing.res;
				count = 0;
				for(String resName : ordRes){
					if(count++>=thing.size)break;
					Resident res = residentsMap.get(resName);
					currRes += res.bonus;
				}
				if(currRes>maxRes)maxRes = currRes;
				ArrayList<Thing> arrayThings = ordByRes.get(currRes);
				if(arrayThings==null){
					arrayThings = new ArrayList<Thing>();
				}
				arrayThings.add(thing);
				ordByRes.put(currRes, arrayThings);
			}
			ArrayList<Thing> maxOrds = ordByRes.get(maxRes);
			Thing maxOrd = maxOrds.get(0);
			int countResidentsForOrd = 0;
			ArrayList<String> resultingResidentsForOrd = new ArrayList<String>();
			for(String resName : ordRes){
				if(countResidentsForOrd+1>maxOrd.size)break;
				++countResidentsForOrd;
				Resident res = residentsMap.get(resName);
				resultingResidentsForOrd.add(res.name);
				occupiedResidents.add(res.name);
			}
			//System.out.println(maxOrd.name + " " + count + resultingResidentsForOrd.toString());
			Iterator<String> weaponIter = residentsMap.keySet().iterator();
			while(weaponIter.hasNext()){
				if(countResidentsForWeapon>=maxWeapon.size)break;
				String resName = weaponIter.next();
				if(!occupiedResidents.contains(resName)){
					countResidentsForWeapon++;
					resultingResidentsForWeapon.add(resName);
					occupiedResidents.add(resName);
				}
			}
			Iterator<String> armorIter = residentsMap.keySet().iterator();
			while(armorIter.hasNext()){
				if(countResidentsForArmor>=maxArmor.size)break;
				String resName = armorIter.next();
				if(!occupiedResidents.contains(resName)){
					countResidentsForArmor++;
					resultingResidentsForArmor.add(resName);
					occupiedResidents.add(resName);
				}
			}
			Iterator<String> ordIter = residentsMap.keySet().iterator();
			while(ordIter.hasNext()){
				if(countResidentsForOrd>=maxOrd.size)break;
				String resName = ordIter.next();
				if(!occupiedResidents.contains(resName)){
					countResidentsForOrd++;
					resultingResidentsForOrd.add(resName);
					occupiedResidents.add(resName);
				}
			}
			
			StringBuffer sbWeapon = new StringBuffer();
			for(String resName : resultingResidentsForWeapon){
				sbWeapon.append(" " + resName);
			}
			System.out.println(maxWeapon.name + " " + countResidentsForWeapon + sbWeapon.toString());
			StringBuffer sbArmor = new StringBuffer();
			for(String resName : resultingResidentsForArmor){
				sbArmor.append(" " + resName);
			}
			System.out.println(maxArmor.name + " " + countResidentsForArmor + sbArmor.toString());
			StringBuffer sbOrd = new StringBuffer();
			for(String resName : resultingResidentsForOrd){
				sbOrd.append(" " + resName);
			}
			System.out.println(maxOrd.name + " " + countResidentsForOrd + sbOrd.toString());
		}		
	}
}