Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Boom

time limit per test

1 secondmemory limit per test

256 megabytesinput

input.txtoutput

output.txtLet's consider the famous game called Boom (aka Hat) with simplified rules.

There are *n* teams playing the game. Each team has two players. The purpose of the game is to explain the words to the teammate without using any words that contain the same root or that sound similarly.

Player *j* from team *i* (1 ≤ *i* ≤ *n*, 1 ≤ *j* ≤ 2) is characterized by two numbers: *a*_{ij} and *b*_{ij}. The numbers correspondingly represent the skill of explaining and the skill of understanding this particular player has.

Besides, *m* cards are used for the game. Each card has a word written on it. The card number *k* (1 ≤ *k* ≤ *m*) is characterized by number *c*_{k} — the complexity of the word it contains.

Before the game starts the cards are put in a deck and shuffled. Then the teams play in turns like that: the 1-st player of the 1-st team, the 1-st player of the 2-nd team, ... , the 1-st player of the *n*-th team, the 2-nd player of the 1-st team, ... , the 2-nd player of the *n*-th team, the 1-st player of the 1-st team and so on.

Each turn continues for *t* seconds. It goes like that: Initially the time for each turn is *t*. While the time left to a player is more than 0, a player takes a card from the top of the deck and starts explaining the word it has to his teammate. The time needed for the *j*-th player of the *i*-th team to explain the word from the card *k* to his teammate (the *q*-th player of the *i*-th team) equals *max*(1, *c*_{k} - (*a*_{ij} + *b*_{iq}) - *d*_{ik}) (if *j* = 1, then *q* = 2, else *q* = 1). The value *d*_{ik} is the number of seconds the *i*-th team has already spent explaining the word *k* during the previous turns. Initially, all *d*_{ik} equal 0. If a team manages to guess the word before the end of the turn, then the time given above is substracted from the duration of the turn, the card containing the guessed word leaves the game, the team wins one point and the game continues. If the team doesn't manage to guess the word, then the card is put at the bottom of the deck, *d*_{ik} increases on the amount of time of the turn, spent on explaining the word. Thus, when this team gets the very same word, they start explaining it not from the beginning, but from the point where they stopped. The game ends when words from all *m* cards are guessed correctly.

You are given *n* teams and a deck of *m* cards. You should determine for each team, how many points it will have by the end of the game and which words the team will have guessed.

Input

The first line contains two integers *n*, *t* (1 ≤ *n*, *t* ≤ 100), which correspondingly denote the number of teams and a turn's duration.

Next *n* lines of the input file contain four integers each: *a*_{i1}, *b*_{i1}, *a*_{i2}, *b*_{i2} (1 ≤ *a*_{ij}, *b*_{ij} ≤ 100) — the skills of the first and the second player of the *i*-th team. The teams are given in the order in which they play.

The next line of the input file contains integer *m* (1 ≤ *m* ≤ 100) the number of cards.

Next 2*m* lines contain the cards' descriptions. Two lines describe each card. The first line of the description contains the word that consists of no more than 20 characters. The words only contain small Latin letters. The second line of the description contains an integer *c*_{k} (1 ≤ *c*_{k} ≤ 100) — the complexity of the word written on the *k*-th card. The cards are listed in the order in which the lie in the deck from top to bottom. The words on all cards are different.

Output

Print *n* lines. On the *i*-th line first print number *s*_{i} the number of points the *i*-th team wins. Then print *s*_{i} space-separated words — the words from the cards guessed by team *i* in the order in which they were guessed.

Examples

Input

2 2

1 1 1 1

1 1 1 1

3

home

1

car

1

brother

1

Output

2 home car

1 brother

Input

2 4

1 2 2 1

2 3 2 2

4

armchair

3

quetzalcoatl

10

pilotage

5

defibrillator

7

Output

2 armchair quetzalcoatl

2 pilotage defibrillator

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/23/2020 06:45:28 (e2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|