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.
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
input | output |
---|
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