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 n-k 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 k-1 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 k-1 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 k-1 cards on the table, then help Donald to guess the hidden card value basing only on k-1 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 single-space 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 < 106).

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 k-1 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 k-1 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 "a1 a2 ... ak" You should reply "b1 b2 ... bk-1", such that {b1, b2, ..., bk-1} is subset of {a1, a2, ..., ak}
  • for Donald's query "b1 b2 ... bk-1" reply the number c, such that {b1, b2, ..., bk-1, c} = {a1, a2, ..., ak}

 

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: 2020-10-18 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: 2015-05-05 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?

EDIT(miodziu): I think, that there is no solution with different permutations for the same cards set. But maybe I'm wrong :)

Last edit: 2015-07-03 16:22:22
Vamsi Krishna Avula: 2015-01-09 19:15:42

kind of strange that my solution passes for v4 and v5 but wa here :/

at_work: 2014-02-28 08:25:04

What a beautiful problem !!! Besides, I've learned a new magic trick :-)
Thanks miodziu !

EDIT(miodziu): Perfect solution, congratulations ;-)

Last edit: 2014-02-28 08:25:51

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