Description

While Johnny was studying a biology course he found a chapter about genetics and he started reading about it. Genetics is the study of genes, and studies what genes are and how they work. Genes are how living organisms inherit features from their ancestors; for example, children usually look like their parents because they have inherited their parents' genes. Genetics tries to identify which features are inherited, and explain how these features are passed from generation to generation. Genes are made from a long molecule called DNA, which is copied and inherited across generations. DNA is made of simple units that line up in a particular order within this large molecule. The order of these units carries genetic information, similar to how the order of letters on a page carries information. A chromosome is an organized structure of DNA. It is a single piece of coiled DNA containing many genes, regulatory elements and other nucleotide sequences. Chromosomes also contain DNA-bound proteins, which serve to package the DNA and control its functions.

Johnny decided to run an experiment to simulate the behavior of inheritance of a chromosome C that can be modeled as an array of integers each element C[i] of the array represents a gene of that chromosome. The value of each gene will be between 0 and 1,000,000,006. Since Johnny does not like programming he requested your help to run a simulation for a very large number of generations to check the values of the chromosome after G generations. On each generation T the value of each gene is the summation of some genes from the generation T-1 mod 1,000,000,007. For example if the chromosome of length 3, has values of genes 4, 7, and 12 initially and the 1^st gene in new generation calculated as sum of 1^st gene and 2^nd gene in previous generation and 2^nd gene in new generation calculated as sum of 2^nd gene and 3^rd gene in previous generation and 3^rd gene in new generation calculated as sum of 3^rd gene and 1^st gene in previous generation. So after 1^st generation chromosome will be 11, 19, and 16 and after 2^nd generation chromosome will be 30, 35, and 27 and so on till generation G.

Input Format

Input will start with T number of test cases. The first line of each test case will contain two integers G, N where 0 <= G < 10¹⁸ representing number of generations and 1 <= N <= 100 representing length of the chromosome. Followed by a line containing N integers n[i] separated by space where 0 <= i < N and 0 <= n[i] < 1,000,000,007 representing the value of each gene in the given chromosome. Followed by N lines, each line i start with integer M[i] representing the number of genes from the previous generation that is going to be added together to get the value of the new gene i at the new generation, followed by M[i] numbers x[j] where 0 <= j < M[i] and 0 <= x[j] < N representing the indices of genes to be added. The value of the gene at the new generation is

Output Format

For each test case, output the result using the following format:

k. n[0] n[1] …. n[N-1]

Where k is the test case number (starting at 1), a single period, a single space, and n[i] is the value of i^th gene after G generations.

Sample Input

Sample

Input
1
2 3
4 7 12
2 0 1
2 1 2
2 2 0

Output
1. 30 35 27