San Sanych was a famous numismatist. Every time he came to another country
he would find a shop for collectors at once and buy there all local coins missing
in his collection.
When he came to Japan and found such a shop, he
figured which Japanese coins were interesting to him. He was going to buy them
when he noticed that all the coins in that shop were packed in transparent
boxes, several coins in one box, and one could buy whole boxes only. The price
for all boxes was the same—200 yen. San Sanych was ready to buy some
extra coins if eventually every coin that he needed would cost him no more than
100 yen. He started to examine the boxes. The required coins were present in
many boxes in different combinations. It was not easy to make the choice.
Seeing the customer's confusion, the shopkeeper offered her help and asked
which coins he wanted. San Sanych named the coins and added that he would buy
several boxes if their total cost didn't exceed the value of the purchase. In
order to determine the value of a purchase, San Sanych counts the number of
different new coins in the purchase and multiplies the number by 100 yen.
The shopkeeper said that she would select a suitable set of
boxes and let San Sanych have it at half-price if he bought the whole set. Of
course, in this case he might have to buy some redundant boxes—those that
could be excluded without decreasing the value of the set. San Sanych couldn't
miss the chance to get a discount and agreed to buy a set with the total cost,
the discount taken into account, not exceeding its value. The shopkeeper was
very kind and promised not to include into the set boxes that contained none
of the required coins. Naturally, San Sanych left the shop with the largest set
satisfying the above conditions.
Your task is to determine which boxes the shopkeeper included in the set.
Input
In the first line there are two integers: the number n of kinds of Japanese
coins in the shop (1 ≤ n ≤ 100) and the number k of boxes
in the shop (1 ≤ k ≤ 50). The boxes are described in the following
k lines. Each of these lines starts with the number ki
of coins in a box (1 ≤ ki ≤ 100). Then there are
exactly ki numbers denoting coins. The numbers are separated
with a space. The coins are numbered from 1 to n. All coins in each box
are different.
In the last line you are given the list of coins that San Sanych wants to buy.
The first number in this line is the number m of coins in the list
(1 ≤ m ≤ 100). Then there are m numbers from 1 to n
separated with a space. All numbers in the list are different.
Output
In the first line output the number of boxes San Sanych bought. In the next
line, give the numbers of these boxes separated with a space. The boxes are
numbered from 1 to k as they are given in the input. If there are
several possible answers, output any of them.
Sample
input | output |
---|
10 4
5 2 7 6 1 3
6 6 7 10 2 9 4
5 1 8 3 9 2
5 4 3 7 6 1
4 8 5 4 9
| 3
2 3 4
|
Problem Author: prepared by Vladimir Yakovlev, special thanks to Vladislav Isenbaev
Problem Source: USU Open Personal Contest 2009 (February 28, 2009)