Description

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

There lives a large group of Gurubing soldiers in the kingdom. They gain power by continuously singing the names of the leaders—the “Niuren chieftains”. Each singing process works like this: first, a soldier gets a number from the integer generator, then spends one unit of time to sing this number. If he finds that the name of some Niuren chieftain has already been sung (that is, the name appears as a contiguous substring of the singing sequence), then this singing process ends immediately.

Definitions:

• Singing sequence: If someone has sung $x$ numbers, and the number sung at the $i$-th step is $a_i$, then the singing sequence $=(a_1,a_2,\cdots,a_x)$.
• Integer generator: A divine object in the Singing Kingdom. It has a button; if you press it once, it returns a random integer from $1\sim n$ with equal probability.
• Singing time: The time spent in one singing process.

The singing time is random and unpredictable. However, its expected value is fixed. This expected value describes how long the singing time is on average, and can also be called the average singing time.

People in the kingdom love singing. They want the singing time to be as long as possible, so they decide to remove (dismiss) some Niuren chieftains to make the average singing time longer. But they cannot remove all Niuren chieftains; otherwise, each singing process would never stop, and they would not be able to gain power. Therefore, they decide to keep only one Niuren chieftain and remove all the others.

Your task is: given $n$, the number of Niuren chieftains $t$, and the name of each Niuren chieftain, for each $1\leq i\leq t$, if only the $i$-th Niuren chieftain is kept and all others are removed, output what the average singing time will be.

Hint: This number is a non-negative integer.

Output requirement: Because this number is too large, you only need to output its last $4$ digits. If it has fewer than $4$ digits, pad leading zeros (see the sample).

Input Format

The first line contains two integers $n,t$. The following $t$ lines describe the names of the $t$ Niuren chieftains.

Line $i+1$ ($1\leq i\leq t$) has the following format: the first number is $m_i$, the length of the $i$-th Niuren chieftain’s name. After a space, there are $m_i$ numbers describing this name, with one space between each pair of adjacent integers.

Output Format

Output $t$ lines. The $i$-th line contains an integer, meaning the last four digits of the maximum average singing time when keeping only the $i$-th Niuren chieftain and removing all others.

2 2
1 1
3 1 2 1

0002
0010

Hint

For $100\%$ of the testdata, $1\leq n\leq 10^5$, $t\leq 50$, $1\leq m_i\leq 10^5$.

Translated by ChatGPT 5