MMMAGIC4  Mickey Mouse Magic Trick v4
MMMAGIC4
Mickey Mouse and Donald Duck love magic. They spacialize with card tricks. Mickey invented a new trick and they are going to surprise the world. They've contracted series of shows on whole the globe, worth many milion of dolars $$. The first show is coming up but unfortunately Mickey lost secret of the trick. He remembers only trick description, but it's not enough to satisfy the contract conditions. Help them!
Trick description
Mickey has n cards with values 1, 2, ..., n. He invites a spectator from the audience, Donald is outside the stage and see nothing on the stage. The spectator chooses randomly k cards from the pack and discard the remaining nk cards. Mickey chooses one card from this k cards, shows it to everyone (except Donald) and hides it to the spectator's pocket. Next Mickey leaves the remaining k1 cards in some order on the table. Donald is coming back. He is the only person, who don't know, what is the number in the hiden card. He can see only k1 cards on the table. Donald thinks for a while, the drum rumbles, at the begining very silent, then lauter and lauter, everyone is waiting, the drum stops, a few seconds of deep silence and... Donald says the number on the hidden card. It's correct, applause! How did he discover the number? It's magic!
Help request
Mickey and Donald know, that's not magic only smart math manipulations. They asked You to help them. You have to write computer program, that can help them with the trick. The program should be able to do two things: help Mickey to select one card from given k cards and describe order of remaining k1 cards on the table, then help Donald to guess the hidden card value basing only on k1 cards left by Mickey on the table. You can use any strategy that You want, but remember  Donald needs to guess the number during the show, because the huge profit $$ depends on it.
Input
All integers in the same line are singlespace separated (the same concerns problem output).
Values n, k are constant. In this problem n=27 and k=4. There are also problems with different values: MMMAGIC3, MMMAGIC5, MMMAGIC6
The first line of input contains two integers M, D, where M is the number of test cases in which Mickey needs help, D is the number of test cases in which Donald needs help (M+D < 40000).
Every of next M lines contains k distinct integers from range [1, n]  the values on cards given to Mickey. The order of values is casual.
Every of next D lines contains k1 distinct integers from range [1, n]  the cards left to Donald on the table. The order is the same, as on the table, from left to right.
Output
For each Mickey's query write a line with k1 integers  the values on the cards, that Mickey have to leave on the table, from left to right.
For each Donald's query write a line with one integer  the value of hidden card or (if in Your strategy such situation is impossible) any of remaining values.
Example
Input 1  Output 1 
3 0 1 2 3 4 4 13 6 2 8 20 7 4 
3 2 1 13 4 6 4 20 7 
Input 2  Output 2 
0 3 3 2 1 13 4 6 4 20 7 
4 2 8 
Explanation
The example above don't show any concrete strategy. It just shows, that strategy must be coherent (when Mickey for given set of cards 1 2 3 4 leave on the table 3 2 1, then Donald for given cards 3 2 1 should answer with the number 4).
Generally You can implement Your own strategy satisfying the conditions below:
 for Mickey's query "a_{1} a_{2} ... a_{k}" You should reply "b_{1} b_{2} ... b_{k1}", such that {b_{1}, b_{2}, ..., b_{k1}} is subset of {a_{1}, a_{2}, ..., a_{k}}
 for Donald's query "b_{1} b_{2} ... b_{k1}" reply the number c, such that {b_{1}, b_{2}, ..., b_{k1}, c} = {a_{1}, a_{2}, ..., a_{k}}
Note
The similar problems appeared in MWPZ 2007 contest in Poland, with different story (in original problems there was Polish characters Bolek, Lolek and Jacek, Placek). The main page of contest is http://mwpz.poznan.pl
hide comments
gamer496:
20150625 11:20:19
Time limit is too lenient even for slow languages like python, 

Vamsi Krishna Avula:
20141227 07:24:43
just a few modifications from v3, thanks for the time limit! :D 

રચિત (Rachit):
20140129 18:52:43
@miodziu Awesome Question! :D

Added by:  miodziu 
Date:  20140109 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 