MMMAGIC4 - Mickey Mouse Magic Trick v4

no tags 

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 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=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 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
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 "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
gamer496: 2015-06-25 11:20:19

Time limit is too lenient even for slow languages like python,

Vamsi Krishna Avula: 2014-12-27 07:24:43

just a few modifications from v3, thanks for the time limit! :D

રચિત (Rachit): 2014-01-29 18:52:43

@miodziu Awesome Question! :D
//A (wrong) logic similar to MMMAGIC3 costed me 3 WA

EDIT (miodziu):
The idea of WA solutions seems to be good, but You probably made some implementation bugs. I'm impressed with your AC solution ;-)

Last edit: 2014-01-29 21:12:16

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