Problem Statement

This problem is a harder version of Problem C, with $N$ reels instead of three and a greater upper limit for $M$.

There is a slot machine with $N$ reels. The arrangement of symbols on the $i$-th reel is represented by the string $S_i$. Here, $S_i$ is a string of length $M$ consisting of digits.

Each reel has a corresponding button. For each non-negative integer $t$, Takahashi can either choose and press one button or do nothing exactly $t$ seconds after the reels start spinning. If he presses the button corresponding to the $i$-th reel exactly $t$ seconds after the reels start spinning, the $i$-th reel will stop and display the $((t \bmod M)+1)$-th character of $S_i$. Here, $t \bmod M$ denotes the remainder when $t$ is divided by $M$.

Takahashi wants to stop all the reels so that all the displayed characters are the same. Find the minimum possible number of seconds from the start of the spin until all the reels are stopped so that his goal is achieved. If this is impossible, report that fact.

Constraints

• $1 \leq N \leq 100$
• $1 \leq M \leq 10^5$
• $N$ and $M$ are integers.
• $S_i$ is a string of length $M$ consisting of digits.

Input

The input is given from Standard Input in the following format:

N M
S_1
\vdots
S_N

Output

If it is impossible to stop all the reels so that all the displayed characters are the same, print -1. Otherwise, print the minimum possible number of seconds from the start of the spin until such a state is achieved.