- 14

## Statement

## Goal

You must output the result of an Einstein's riddle.An Einstein's riddle is a logical puzzle where

`nbPeople`people are assumed to all have different names, different characteristics...

It means if Georges eats Salad, then none of the others can eat Salad. And also, if Georges eats Salad, then he cannot eat anything other than Salad.

Each line of input contains a list of characteristics that are all in the same category. For example, in the first test case, the first category is the individual's first name, the second is their means of transportation, the third is the type of plant they like, and finally the pet they own.

Each category of characteristic has

`nbPeople`different possibilities. For example, the second line lists various means of transportation, and it has 4 possibilities (

You are given a number of relational links that can be either in the format:

or

The relational links can be on any two characteristics, and permit the riddle to be solved using logic. The relational links are guaranteed to be sufficient to solve the riddle, and are always non-contradictory. For example, we can't have

The goal is to solve the riddle and print it as a grid, separated by space and newline, with each person in their own column and each characteristic category on its own line.

The characteristics in the first line will be ordered alphabetically, and each subsequent line will have the characteristics of that category ordered such that they match up correctly with the characteristics in the first line of output. In this way, each column of the output corresponds to the same person, with each person associated with one characteristic from each category.

Input

**Line 1:**Two space separated integers

`nbCharacteristics`and

`nbPeople`for the number of characteristics and the number of people

**Next**The list of all characteristics in each characteristic category (one category per line), space separated

`nbCharacteristics`lines:**Next line:**

`N`the number of relational links

**Next**One relational link per line, with each link formatted as either

`N`lines:Output

**Line 1 to line**The grid of characteristics representing the solution to the riddle, line by line

`nbCharacteristics`:The order of the characteristic categories (the lines) is as given in the input, and the order of the people (the columns) is such that the first characteristic (which may or may not be first name) is presented in alphabetical order.

Constraints

1 <=

`nbCharacteristics`,`nbPeople`< 10Example

Input

4 4 Amelia Bob Charles Daniel Autobus Car Bicycle Roller Herb Bush Tree Flower Turtle Ant Rhinoceros Elephant 15 Charles & Bicycle Flower & Bob Elephant ! Daniel Elephant & Autobus Rhinoceros & Bicycle Amelia & Turtle Tree & Turtle Herb ! Car Bush ! Daniel Elephant & Bob Tree & Car Roller & Ant Flower ! Daniel Tree ! Elephant Tree ! Bob

Output

Amelia Bob Charles Daniel Car Autobus Bicycle Roller Tree Flower Bush Herb Turtle Elephant Rhinoceros Ant

A higher resolution is required to access the IDE

Online Participants

### Channels

### Direct Messages

No private conversations