A city contains N stations. Also in the city circulate M buses. The i-th bus has an itinerary consisting of $t_i$ stations: $s_{i,1}, s_{i,2}, ... ,s_{i,t_i}$. At moment 0 it is at the station $s_{i,1}$, and then each minute he travels to the next station. When it reaches the end it goes back to the begging and starts again. At moment 0 you are at station 1. If at any moment you and a bus are at the same station, you can get on it and travel with it. You can get off at any station. The same station can appear multiple times in the itinerary of the bus, but not adjacent to each other (in particular, the last station is adjacent to the first). You can only travel by bus. You are interested in finding the minimum amount of time you need to get to each station, or state that it is impossible.

You can only travel in one bus at a time, but you can use multiple buses to reach your destination. There can be multiple buses at the the same station at the same time. Getting in and off a bus is instantaneous.

Input

The first line contains 2 integers N and M - the number of stations and the number of buses respectively.

Each of the next M lines contain an integer $t_i$ followed by $t_i$ integers $s_{i,1}, s_{i,2}, ... ,s_{i,t_i}$ - the itinerary of a bus.

Output

Print $N-1$ numbers - the i-th number is the minimum amount of time needed to reach the $(i+1)$-th station, or 1 if it is impossible.

Constraints

• $2 \leq N \leq 10^5$

• $1 \leq M \leq 10^5$

• $2 \leq t_i$

• $1 \leq s_{i,j} \leq N$

• $s_{i,j} \neq s_{i,j-1}$

• $s_{i,n} \neq s_{i,1}$

• The sum of all $t_i$ is not greater then $2*10^5$