ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Awakening

Time limit: 2.0 second
Memory limit: 64 MB
Nikolai was commuting home from work on the train. He preferred to walk on foot, staring at the Earth hanging just above the horizon, but today he was in a hurry. The train silently slid over magnetic rail, moving people on the ring route along the Dome wall. If you look out one window, you can see majestic skyscrapers and multilevel highways of a huge city; in the opposite window all you can see is a desert, desolate lunar desert all the way to the horizon. It was crowded in the railcar. The majority of passengers were similar to Nikolai in appearance — inexpensive-looking gray suit, slim briefcase and a fancy communicator on the left wrist. That was very typical for a working bee of the Moon's information society. Some of them idly chatted, others wearily looked out the windows. Yet another few stood frozen, with deadpans and glass eyes. One could notice that each of them had a thin white cable running from the communicator to the head, ending somewhere behind the left ear.
At the next stop a seat near Nikolai become empty. He took the seat, stretched out comfortably and pulled the same thin white cable out of his pocket. He connected one end to the communicator and the other one to his neuroport behind the ear. Immediately, standard desktop interface appeared. Everything his eyes saw was contained in a window titled “Real World”. Nikolai switched to that window and turned off the sound button. The noise of the railcar and passengers faded out. Nothing could distract him from reading mail. Unfortunately, there were only spam messages in his mailbox. But one of these letters has drawn his attention. It was an advertisement of some exclusive club for succeessful young men. A man in a picture glowed with joy and incessantly repeated: “I am happy to be here!” Nikolai highlighted the address of the club and copied it to his address book.
Nikolai disconnected from the communicator when the train approached his station. He got off the rail and hurried to his apartment building. His apartment was on the seventeenth floor. It was cramped, but had windows on the sunny side, which was highly valued. Inside, it was clean, almost void of any traces of a living being. If a spy infiltrated the apartment, he'd fail to find any object that bears the traits of Nikolai's personality. To tell the truth, Nikolai himself didn't know what kind of man was he.
It didn't take him long time before he left the apartment. He put on different clothes, now he looked like unemployeed dweller of the lower levels — long sleeves hid his communicator and the hood hid his neuroport. Nikolai has gone directly to one of the three huge elevators which connected the domed city with the underground levels, where all industry and life-support systems were concentrated and where majority of the population lived. The elevator operated similiar to terrestrial ferries — cars drove in and parked in rows, passengers bought tickets and took their seats. Finally, the bell ringed, red lights flashed out and the machine started to creep downwards. For some, it was an adventurous journey in search of forbidden pleasures; for others, it was a one-way trip home accompanied by shattered dreams and ruined plans.
It wasn't the first time Nikolai visited the lower levels. He quickly figured out where the exclusive club from the ad was located. It was in old mines, where the first colonists mined for water ice. The web of tunnels spread for many miles and was considered one of the most dangerous places for the surface folk. But Nikolai knew how to merge with the crowd and move around without attracting needless attention. The crowd carried him to the front of a dilapidated mansion. Nikolai just stood there in hesitation, then he had checked the address and came in.
The inside of the club was very different. A visitor found himself in a large, fully illuminated hall with high ceiling. The interior was laid out with simplicity and style, which gave an impression of enormous wealth. There was a reception desk on the other end of the hall. A beautiful, exquisite girl sat behind it. When Nikolai approached the desk, she smiled wide and softly asked:
“Good day to you, sir. Can I have your membership card, please?”
Nikolai had lost his concentration for a moment, but braced himself and confidently said:
“I am happy to be here.”
The girl smiled even more wide, stood up and said:
“We're glad to see you too. Please follow me.”
They walked down through the twisting corridor past numerous doors, until the girl had stopped in front of a red curtain. She invited him to come inside. Nikolai moved the curtain aside and entered the room.
А rather large room was partitioned into small cabins by red translucent veils. There were a couch and a small table inside every cabin. Although the room was poorly illuminated, Nikolai could see that some of the couches were occupied by people. Thin smoke curled up at the ceiling, the air was filled with intoxicating and sweet aroma. A lit lamp was standing on the table in one of the cabins. Nikolai moved there and sat on the couch.
Less than 5 minutes later, a man entered the neighbouring cabin. Nikolai couldn't see his face, but there was enough light from the lamp for the man to see Nikolai's face. He sat down on the couch and asked in a hoarse voice:
“Have you brought the money?”
Nikolai opened his pocket and pulled a small piece of plastic out of it. He put the card on the floor under the veil. The man took the card and passed it over the reader device. The device displayed a number which, apparently, satisfied the man. He hid the card in one pocket and took something from the other. He put the thing on the floor and moved it to Nikolai with his foot.
“Do not forget two rules,” said the man. “First, the Moon has the death penalty for possession of such a device. Second, there are things worse than death penalty for those, who can't keep their mouths shut.”
Without waiting for a reply, the man stood up and left the room.
Nikolai picked up the device from the floor. It was a polished blue cube with two neuroports on opposite sides. Nikolai was amazed how simple this notorious device looked. The official name of the device was “Associations Control Module (ACM)”, also known as “Brainwasher”. Using it, one could force the creditor to forgive debt, or force arrogant supermodel to fall in love with a hobo. But Nikolai wasn't planning to use it on other people. All that he wanted was to know himself. He wanted to remember more than the last three years of his life.
Problem illustration
Nikolai came back home in the middle of the night. He decided not to waste any time and plugged himself to the cube. Using his personal terminal, he started to explore his own brain. Memories of the last three years were easy to locate. But when he tried to go deeper, he was puzzled. The memory was not wiped out, but it surely didn't look like a memory of a human being. Meaningless chains of associations running for absurd lengths, branching and merging, but inevitably ending in one of the five vivid images. Those images were a whale, a penguin, a piano, a jackboot, and a train.
Nikolai unplugged himself and began to think. Someone (maybe himself) had messed with his head. Chains of associations were thoroughly mixed on all levels. But these five objects had to mean something. Quite possible, it was a code and he had to find a key. Maybe, the key was something that connected them together. Nikolai decided to write a program searching for common associations of a set of objects.

Input

The first line contains a number n of objects (2 ≤ n ≤ 1000). Each of the following n lines contains a name of an object, a colon, a space, and a space-separated set of associations for this object. All object names and associations contains Latin lowercase letters only. The next line contains a number m of object sets (1 ≤ m ≤ 1000). You are to find common associations for each of these sets. Each of the following m lines describing sets contains space-separated object names. Each set contains two or more objects. Each line in the input is no longer than 250 characters.

Output

For each object set, put all common associations for this set on a single line, space-separated and sorted in lexicographic order. If the objects in the set have no common association, output a line containing “No solution.”

Sample

inputoutput
6
whale: big black water animal
penguin: black white ice beak
piano: keyboard black white wire
jackboot: leather heel black
train: rail wheel black
rose: red green thorn
3
whale penguin piano jackboot train
penguin piano
jackboot rose
black
black white
No solution.
Problem Author: Pavel Atnashev
Problem Source: The 13th Urals Collegiate Programing Championship, April 04, 2009
To submit the solution for this problem go to the Problem set: 1700. Awakening