Nhân dịp \(20\) tháng \(10\), Tèo muốn có một món quà đặc biệt tặng cho bạn nữ duy nhất trong lớp học CP của mình. Tèo dự định sẽ làm một món quà handmade từ một xâu \(A\) gồm \(N\) ký tự. Tèo có thể tạo ra xâu \(B_i = A_iA_{i + 1}\ldots A_NA_1A_2\ldots A_{i - 1}\) bằng tài năng và nghệ thuật của mình.

Tèo thu thập được \(M\) món quà kém chất lượng không được sử dụng vào ngày \(20\) tháng \(10\), mỗi món quà là một xâu khác nhau. Độ xấu của một món quà được làm từ xâu \(A\) được định nghĩa là xâu con dài nhất mà cũng là xâu con của ít nhất một xâu trong \(M\) món quà Tèo thu thập được. Nhắc lại, xâu con là một xâu được tạo từ một đoạn con các ký tự liên tiếp từ xâu ban đầu.

Yêu cầu: Hãy giúp Tèo tạo ra món quà có độ xấu nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) \((N \leq 10 ^ 5\), \(M \leq 10 ^ 4)\) lần lượt là độ dài xâu \(A\) và số xâu thu thập được.
• Dòng thứ hai chứa xâu \(A\) ban đầu.
• Dòng thứ \(i\) trong số \(M\) dòng tiếp theo chứa xâu thứ \(i\) trong số \(M\) xâu thu thập được. Tổng độ dài của các xâu thu thập được là \(T\) \((T \le 10 ^ 5)\).

Biết rằng tất cả các xâu chỉ gồm \(26\) chữ cái Latin in thường.

Output

• In ra độ xấu nhỏ nhất của xâu \(B_i\) Tèo tặng các bạn nữ nhé!

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 10 ^ 2\), \(T \le 10 ^ 2\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 10 ^ 3\), \(T \le 10 ^ 3\).
• Subtask \(3\) (\(20\%\) số điểm): \(T \le 10 ^ 3\).
• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

8 9
wqzjuyip
j
i
u
y
p
q
i
uy
z

1

9 3
iuidkunog
uidg
id
iuin

2

10 1
eprwqfntti
ttiwqeprwq

3