In the Kingdom of Singing, everyone's name is a non-empty string consisting only of integers from $1$ to $n$.

A large group of Gulu soldiers lives in the kingdom, and they gain power by continuously singing the names of their leaders—the Great Chiefs. A Gulu soldier's singing process works as follows: First, they obtain a number from an integer generator, then spend one unit of time singing this number. If they discover that the name of a Great Chief has already been sung (i.e., this name is a contiguous substring of the singing sequence), the singing process ends immediately.

Definitions

• Singing Sequence: If someone has sung $x$ numbers, and the $i$-th number sung is $a_i$, then the singing sequence is $(a_1, a_2, \dots, a_x)$.
• Integer Generator: A sacred object in the Kingdom of Singing. It has a button; if you press it, it returns an integer from $1$ to $n$ with equal probability.
• Singing Time: The time spent during one singing process.

The singing time is random and unpredictable; however, the expected value of the singing time is fixed. This expected value is the average length of the singing time, also known as the average singing time.

The people of the kingdom love to sing and want the singing time to be as long as possible. Therefore, they decided to dismiss some Great Chiefs to make the average singing time longer. However, they cannot dismiss all the Great Chiefs, otherwise, their singing would never stop, and they would be unable to gain power. Thus, they decided to keep only one Great Chief and dismiss the rest.

Your task is: given $n$, the number of Great Chiefs $t$, and the name of each Great Chief, tell the people of the kingdom, for each $1 \le i \le t$, what the average singing time would be if they kept the $i$-th Great Chief and dismissed the others.

Note: This number is a non-negative integer! Output Requirement: Since this number can be very large, you only need to output the last 4 digits of the number. If it has fewer than 4 digits, pad with leading zeros (see examples).

Input

The first line contains two integers $n$ and $t$. The following $t$ lines describe the names of the $t$ Great Chiefs. The format of the $(i+1)$-th line ($1 \le i \le t$) is as follows: The first number is $m_i$, representing the length of the $i$-th Great Chief's name. After a space, there are $m_i$ numbers describing the name of this Great Chief, with adjacent integers separated by a space.

Output

There are $t$ lines in total. The $i$-th line contains an integer representing the last 4 digits of the average singing time if the $i$-th Great Chief is kept and the others are dismissed.

Constraints

• $1 \le n \le 10^5$, $t \le 50$, $1 \le m_i \le 10^5$.
• 30% of the data satisfies $n \le 10^3$, $m_i \le 10^3$.
• 50% of the data satisfies $n \le 10^4$, $m_i \le 10^4$.

Examples

Input 1

2 2
1 1
3 1 2 1

Output 1

0002
0010

Note 1

When keeping the 1st Great Chief and dismissing the others, the possible singing sequences when the singing ends are: "1", "2,1", "2,2,1", "2,2,2,1", ..., with probabilities $1/2, 1/4, 1/8, 1/16, \dots$, and singing times $1, 2, 3, 4, \dots$. It is not difficult to prove that $\sum_{i \ge 1} \frac{i}{2^i} = 2$. When keeping the 2nd Great Chief and dismissing the others, the average singing time is 10.

Input 2

26 1
6 1 2 3 1 2 3

Output 2

3352

Note 2

The average singing time is 308933352.