Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Power Puff Girls!

Limits: 1s, 512 MB

You all have heard of the power puff girls. Or maybe you are the next new generation and I am getting old! Anyway the legend goes something like this: There lived a stupid professor who wanted to create the perfect little girls by mixing sugar, spice and everything nice. But the stupid also mixed something called chemical X into the mix. He is a professor and he keeps chemical X with sugar, spice and everything nice! That’s like keeping acid with salt, pepper and oil in your kitchen. Even detergents have labels to not put them near children! I am going off track again. So what happened next was, he got three mutant kids who could fly, shoot laser out of their eyes and what not. They were basically what every 6 year old girl dreams she could do.

You are the super villain Mojo and would like to create super human freaks of your own. But you don’t necessarily know what mixture of what to use. And you being the most intelligent creature would like to defeat the stupid professor and his power puff girls. You already have one thing going for you. You are not going to use just 3 or 4 ingredients to create your minions. You are above that. In particular, you have researched and created N elements which you are going to use in 4 stages to create the ultimate super minion.

As mentioned above, the 4 stages will focus on 4 steps of development. First, you will define their core, then their strength, then their loyalty and then comes their exterior. The last part is important, because for too long heroes have been loved and adored for their flawless beauty. You want your minions to be lovable at first sight as well. You might be thinking that’s absurd. Nobody goes for looks! But who knows?

Now let’s focus, shall we? For each stage, you will be given a list of compounds. Why compounds? Because they are made up of some subset of the original N elements that you are using. You are using an automated machine to create all possible combinations of the compounds from each stage.

The merging of stages works like this. There is a mixing pot which is empty at the beginning of the first stage. At the beginning of any stage, the machine may add any compound from the list of compounds in that stage randomly. Some compounds may appear more than once in one stage as all of them are kept in boxes and you didn’t bother to only supply the machine with unique compounds. The compound added at any stage and the compound already on the pot mixes together and only the common elements of the compounds remain. For example, if you mix a compound consisting of A, C, D elements with a compound consisting of C, D, I elements the result would be a compound consisting of C and D element.

Now you know each subset of N elements create a compound. You would like to find the probability of the resultant compound. Namely, for each possible compound, you would like to find the probability of it being the resultant compound.

Input

The first line of the input will contain N(1 < N < 19), the number of elements you are going to use. Then there will be 4 groups of numbers, each representing a stage in the creation. Each group will start with a number M(1 < M ≤ 200000) representing the number of compounds in that stage. Next follows M integers, representing what that compound is made of. The binary representation of the number tells which elements this compound is made of. For example, a number 11, whose binary form is 1011 tells that this compound is made of elements 1, 2 and 4. All the compound numbers are valid and are from 1 to 2N-1 inclusive.

Output

For each possible compound starting from 0 to 2N-1, print the probability that this compound is going to be the end result. If the probability is of form a/b, then print a number a*b-1 mod 1000000009.

Samples

InputOutput
3
6
2
3
3
1
1
4
6
6
5
6
7
1
6
6
5
2
3
3
3
7
6
1
4
5
3
2
6
516975314
311728398
311728398
549382721
310185188
0
0
0

Notes

The final compound with description 0 means that during the creation everything was lost and you are left with nothing!

Author
  • triploblastic's Avatar

    triploblastic

Discussion
Submit

Login to submit