An Array and Several More Arrays#222

An Array and Several More Arrays

2 secondes
256 mégaoctets
Hard

There are arrays of integers a_1, a_2, \ldots, a_k, where the array with index contains l_i elements. Let n = l_1 + l_2 + \ldots + l_k.

You need to find integers d_1, d_2, \ldots, d_k such that the numbers (a_{i,j} + d_i) are pairwise distinct and satisfy 1 \leq a_{i,j} + d_i \leq n.

Input

The first line contains two integers and (1 \le n \le 10^4, 1 \le k \le 5) – the total number of elements in the arrays and the number of arrays, respectively.

The next lines contain the arrays. The -th line contains an integer l_i (1\le l_i\le n) and l_i integers a_{i,1},a_{i,2},\ldots,a_{i,l_i} (1 \le a_{i,j} \le n) – the length and elements of the -th array, respectively.

It is guaranteed that n = l_1 + l_2 + \ldots + l_k.

Output

If the required values of do not exist, output a single line "No".

Otherwise, output "Yes" on the first line.

On the second line, output integers d_1,d_2,\ldots,d_k – the values that need to be added to the elements of the arrays to form a total of distinct integers from to .

If there are multiple correct answers, any one of them may be output.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading

Note

In the first example, d = [0,0,0,0,0] satisfies the condition, since after adding the corresponding values, the arrays , , , , are formed.

In the second example, d = [1,-5,1,1] satisfies the condition, since after adding the corresponding values, the arrays , , , are formed.

In the third example, d = [0,1] satisfies the condition, since after adding the corresponding values, the arrays [1,4,5,6] and [2,3,7] are formed.

Scoring

  1. ( points): k=1;

  2. ( points): a_{i,j}+1=a_{i,j+1} for 1 \le i \le k, 1 \le j < l_i;

  3. ( points): k \le 2;

  4. ( points): k \le 3;

  5. ( points): a_{i,j}+2=a_{i,j+1} for 1 \le i \le k, 1 \le j < l_i;

  6. ( points): (\max_{j \in [1;l_i]} a_{i,j}) - (\min_{j \in [1;l_i]} a_{i,j})=(n-k) for 1 \le i \le k;

  7. ( points): n \le 30;

  8. ( points): without additional constraints.