Thunder Elemental Monument Puzzle

You are given n Thunder Elemental Monuments, each having m states: 0, 1, …, m-1. When a monument is attacked, its state increases by one (and state m-1 wraps around to 0). Furthermore, each monument i has an associated list of other monuments such that when monument i is attacked, those listed monuments also increase their state by one (with the same wrap‐around rule). The goal is to change the monuments from an initial configuration to a target configuration.

Formally, when monument i is attacked, it always increments its own state by 1 modulo m and also increments the state of each monument in its given list by 1 modulo m.

You are given the initial state vector s and the target state vector t (both of length n). Let x[i] denote the number of times monument i is attacked. Attacking monument i affects monument j if either i == j or monument j is in the list for monument i. Thus, for each monument j the following congruence must hold:

Your task is to find a nonnegative integer solution vector x = [x[0], x[1], …, x[n-1]] that satisfies the above system of linear congruences modulo m. If there is no solution, output niuza.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 100, 2 ≤ m ≤ 109).

The second line contains n integers representing the initial states s[0], s[1], ..., s[n-1], where each state is in the range [0, m-1].

The third line contains n integers representing the target states t[0], t[1], ..., t[n-1], where each state is in the range [0, m-1].

Then follow n lines. The i-th line begins with an integer ki indicating the number of other monuments that are affected when monument i is attacked, followed by ki integers. These integers represent the 1-indexed indices of the monuments that are also incremented when monument i is attacked.

Note: When monument i is attacked, it always increments its own state by 1 (in addition to affecting the listed monuments).

outputFormat

If a solution exists, output a single line containing n nonnegative integers representing the number of times to attack each monument (in order from 1 to n) to achieve the target configuration. If no solution exists, output niuza.

sample

2 3
0 1
1 2
1 2
0

1 0