CARD - Cardsharper

Zenek is a well known (at least in Byteotia) card-sharper. He spent most of his best years practicing one card shuffle with his deck of n cards, which for simplicity we will call 1, 2, ..., n. Unfortunately, it turns out that knowing this one card shuffle a is not enough to earn a good living. To become rich and famous Zenek needs to know k shuffles c1, ..., ck. As he doesn't have enough time to learn all of them, he decided to learn only one shuffle b so that using both a and b he will be able to perform as many of ci as it is possible.

Each shuffle is described by n numbers t1, t2, ..., tn. Such description means that after performing shuffle, card that was originally at position i will be at position ti.

Task

Find shuffle b maximizing number of shuffles that can be performed.

Input

First line contains n (2 ≤ n ≤ 52). Second line contains n numbers a1, a2, ..., an describing shuffle that Zenek already knows. Third line contains k (2 ≤ k ≤ 6). i-th of the next k lines contains description of ci.

Output

First line contains description of the shuffle b that Zenek should learn. i-th of the next k lines contains:

  • -1 when it is not possible to perform ci using only a and b
  • m, r1, r2, ..., rm (0 ≤ m ≤ 500000, 0 ≤ ri ≤ 106) meaning that applying a r1 times, then b r2 times, then a r3 times and so on is the same as applying shuffle ci once.

Examples

Input

5
2 3 4 5 1
3
1 3 2 4 5
1 2 3 4 5
5 4 3 2 1

Output

2 1 3 4 5
3 4 1 1
0
9 1 1 3 1 4 1 1 1 1

Input

5
1 2 3 4 5
3
1 3 2 4 5
5 4 3 2 1
1 2 5 4 3

Output

1 3 2 4 5
2 0 1
-1
-1

Added by:gawry
Date:2007-09-20
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Fajne Zawody Informatyczne

hide comments
2020-05-14 18:01:09
the problem is so good. there even exists one conceptually simple solution, a solution with few explicit steps. i loved it!
2016-12-05 07:32:50
great problem.

Last edit: 2016-12-06 04:40:40
2015-09-15 14:24:14 gawry
Mark Gritter: any b such that every c_i can be produced as specified in the statement will be accepted.
2015-04-04 22:29:02 taleb.alali
Output
First line contains description of the shuffle b that Zenek shoud learn
/////////////////////////////////////////
How do I choose shuffle b?
Are there conditions !!!!!!!!!!!!!!!!!!!!!!!!
2014-12-08 13:25:01 Mark Gritter
I think I overstated the case, only the conjugates aba^-1 a^2ba^-2 etc. are alternate solutions.
2014-12-08 13:25:01 Mark Gritter
If 'b' is a solution, then isn't 'aba^-1' also a solution? Or 'ab'? Or 'a^2ba^3'? Is there some additional restriction on the number of shuffles performed (the word length) or would all these possibilities be accepted as valid answers?
2014-12-08 13:25:01 gawry
He can learn any shuffle, doesn't have to be one from the input.
2014-12-08 13:25:01 Darth Vadar
shoudn't he learn one of the shuffles provided in the i/p or any type of shuffle he can learn????
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.