Chuỗi từ có độ dài ~n~ là một dãy các từ ~w_1,w_2,...,w_n~ sao cho với mọi ~1 \le i < n~, từ ~w_i~ là tiền tố của từ ~w_{i+1}~.

Nhắc lại từ ~u~ có độ dài ~k~ là tiền tố của từ ~v~ có độ dài ~l~ nếu ~l > k~ và các kí tự đầu tiên của ~v~ trùng với ~u~.

Cho tập hợp các từ ~S = \{s_1,s_2,...,s_m\}~. Tìm chuỗi từ dài nhất có thể xây dựng được bằng cách dùng các từ trong tập ~S~ (có thể không sử dụng hết các từ).

Input

• Dòng đầu gồm số nguyên dương ~m~ .
• ~m~ dòng sau, mỗi dòng gồm một từ ~s_i~.

Constraints

• ~1 \le m \le 2 \times 10^5~
• Độ dài tất cả các xâu không quá ~10^6~.

Output

• In ra một số duy nhất là độ dài của chuỗi từ dài nhất xây dựng được từ các từ trong tập đã cho.

Sample Input 1

3
a
ab
abc

Sample Output 1

3

Sample Input 2

5
a
ab
bc
bcd
add

Sample Output 2

2

Bờm viết một chương trình hỗ trợ học ngoại ngữ. Module quản lí từ vựng với phép tìm kiếm từ được Bờm xây dựng theo quy trình: giả sử danh sách từ chương trình đang có là ~w_1, w_2, . . . , w_N~ , mỗi khi nhận được mẫu tìm ~P~, chương trình sẽ lần lượt so sánh ~P~ với ~w_1, w_2, . . .~ cho đến khi gặp từ trùng với ~P~ hoặc đã hết danh sách từ. Khi so sánh ~P~ với các từ, chương trình sẽ lần lượt so sánh các kí tự từ trái qua phải cho đến khi gặp kí tự sai khác hay một trong hai từ kết thúc (khi đó nếu cả hai từ cùng kết thúc là tìm kiếm thành công).

Để khảo sát hiệu năng của module tìm kiếm, Bờm xây dựng một danh sách N từ và thực hiện tìm kiếm ~Q~ mẫu, với mỗi mẫu Bờm cần xác định số thao tác cơ sở mà chương trình thực hiện, thao tác cơ sở là một lần so sánh kí tự hoặc một lần xử lí khi gặp kết thúc từ. Số thao tác cơ sở thực hiện với mỗi mẫu tìm kiếm sẽ bằng tổng của: số lượng từ được so sánh với mẫu, độ dài của tiền tố chung dài nhất của mỗi từ với mẫu.

Hãy giúp Bờm thực hiện việc khảo sát trên mà không cần thực hiện chương trình của Bờm.

Input

• Dòng ~1~ gồm hai số nguyên ~N,Q~ ~(1 \le N,Q \le 3\times10^4)~
• ~N~ dòng sau, dòng thứ ~i~ ghi từ ~w_i~.
• ~Q~ dòng sau, mỗi dòng là một từ mẫu tì kiếm.

Tất cả các từ trong input đều có độ dài không quá ~30~ và chỉ chứa các chữ cái latin in thường.

Output

• Gồm ~Q~ dòng: dòng ~i~ ghi số nguyên là số thao tác cơ sở mà chương trình của Bờm sẽ thực hiện khi tìm kiếm từ mẫu thứ ~i~.

Sample Input 1

4 2
c
cvp
cvy
cvn
cv
cvy

Sample Output 1

11
9

Cho một tập ~S~ ban đầu rỗng, bạn cần thực hiện ~q~ truy vấn có dạng như sau:

• ~1~ ~x~: Thêm số nguyên ~x~ vào tập ~S~. ~(0 \le x \le 10^9)~

• ~2~ ~x~: Xóa số nguyên ~x~ ra khỏi tập ~S~, nếu số ~x~ xuất hiện nhiều lần, ta chỉ xóa nó một lần, nếu số đó không xuất hiện trong tập ~S~, ta bỏ qua truy vấn này.

• ~3~ ~L~ ~R~: In ra tổng các phần tử trong tập ~S~ có giá trị trong đoạn ~[L,R]~. ~(0 \le L \le R \le 10^9)~

• ~4~ ~k~: In ra phần tử bé thứ ~k~ trong tập ~S~. ~(1 \le K \le |S|)~

• ~5~ ~a~: In ra ~max (a \oplus x) \, \forall \, x \in S~, ở đây ~\oplus~ là phép ~xor~.

Input

Dòng đầu tiên gồm số nguyên ~q~ ~(1 \le q \le 2*10^5)~ mô tả số truy vấn.

~q~ dòng sau, mỗi dòng miêu tả một truy vấn.

Output

Mỗi dòng in ra kết quả theo thứ tự nhập vào của các truy vấn loại ~3,4,5~.

Sample Input 1

10
1 3
1 4
3 1 3
4 2
1 2
2 2
4 1
2 5
3 1 6
5 8

Sample Output 1

3
4
3
7
12

Một lớp học nọ có ~n~ học sinh, tên của học sinh thứ ~i~ được biểu diễn bằng một string ~s_i~.

Có ~n~ biệt danh cũng được biểu diễn bằng các string ~p_i~.

Ta kí hiệu ~lcp(a,b)~ là độ dài tiền tố chung dài nhất giữa hai xâu ~a~ và ~b~.

Bạn có thể chọn ~c~ là dãy hoán vị từ ~1~ tới ~n~, tương đương với việc gán cho bạn thứ ~i~ biệt danh là ~p_{c_i}~. Cách chọn này có độ "hoàn hảo" là ~\sum lcp(s_i,p_{c_i}) \forall i \in[1,n]~.

Hãy tìm dãy hoán vị ~c~ có độ hoàn hảo lớn nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~.
• ~n~ dòng sau, dòng thứ ~i~ là xâu ~s_i~ miêu tả tên của bạn thứ ~i~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ là xâu ~p_i~ miêu tả biệt danh thứ ~i~.
• Lưu ý rằng có thể có các tên hoặc biệt danh trùng với nhau.

Constraints

• ~1 \le n \le 10^5~
• Tổng kí tự của tất cả các xâu không quá ~10^6~.

Output

• In ra độ hoàn hảo lớn nhất tìm được.

Sample Input 1

3
chau
huy
hoang
homhinh
hoanhi
chumchim

Sample Output 1

7

Explanation 1

• chau sẽ ghép với chumchim và có ~lcp~ là ~2~.
• huy sẽ ghép với homhinh và có ~lcp~ là ~1~.
• hoang sẽ ghép với hoanhi và có ~lcp~ là ~4~.

Cho ~n~ xâu ~s_1,s_2,...,s_n~ và số nguyên ~k~.

Đếm số xâu palindrome độ dài ~k~ mà xâu đó có ít nhất một xâu ~s_i \; (1 \le i \le n)~ là xâu con liên tiếp của nó.

Subtask

• Subtask 1: (20% số điểm): ~|s_1| = |s_2| = ... = |s_n| = 1~
• Subtask 2: (30% số điểm): ~n = 1~
• Subtask 3: (30% số điểm): ~\left| s_i \right| \leq 20 \; \forall \, i \in [1, n]~
• Subtask 4: (20% số điểm): ~1 \le n, k \le 10^3~. Độ dài tất cả các xâu không quá ~10^3~.

Input

• Dòng đầu gồm 2 số nguyên dương ~n~ và ~k~ .
• ~n~ dòng sau, mỗi dòng gồm một xâu ~s_i~.

Output

• In ra một số duy nhất là kết quả của bài toán khi chia cho ~10^9 + 7~.

Sample Input 1

2 3
a
aa

Sample Output 1

51

Explanation 1

Một số xâu thỏa mãn là: aaa, ara, sas,...