MMMAGIC6  Mickey Mouse Magic Trick v6
MMMAGIC6
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=725 and k=6. There are also problems with different values: MMMAGIC3, MMMAGIC4, MMMAGIC5
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 < 10^{6}).
Every of next M lines contains k distinct integers from range [1, n]  the values on cards given to Mickey. The values are sorted in ascending order.
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 5 6 2 4 6 100 200 500 4 7 8 111 222 666 
5 4 3 2 1 6 500 4 100 200 4 111 7 8 222 
Input 2  Output 2 
0 3 5 4 3 2 1 6 500 4 100 200 4 111 7 8 222 
6 2 666 
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 5 6 leave on the table 5 4 3 2 1, then Donald for given cards 5 4 3 2 1 should answer with the number 6).
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
suhash:
20201018 07:19:29
miodziu@: Very nice problem. :) Btw... just curious how you wrote a custom judge which waits for all test output files to be ready and then compute the result, instead of the usual per test file judge. (There is not much documentation available about SPOJ custom judges). 

Mateusz Radecki:
20150505 15:12:14
In two different tests must Mickey answer the same for this same questions? I mean from set 1,2,3,4,5,6 must he always make this same permutation?


Vamsi Krishna Avula:
20150109 19:15:42
kind of strange that my solution passes for v4 and v5 but wa here :/ 

at_work:
20140228 08:25:04
What a beautiful problem !!! Besides, I've learned a new magic trick :)

Added by:  miodziu 
Date:  20140109 
Time limit:  99s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  http://mwpz.poznan.pl 