Giải bài trực tuyến

Bờm có một mật khẩu rất rất là dài, và nó được ghi trong một tờ giấy.

Thật là lộ liệu và nguy hiểm nếu tờ giấy đó lọt vào tay người khác. Để giấu xâu mật khẩu A của mình, Bờm đã ghi thêm N xâu khác – gọi đó là các xâu B[1], B[2], … B[N]. Và ghi nhớ một xâu con E (gồm các kí tự liên tiếp) của A mà không là xâu con (gồm các kí tự liên tiếp) của bất cứ xâu B nào. Để khi nhìn lại tờ giấy, Bờm còn biết được đâu mới là mật khẩu của mình.

Tất nhiên là Bờm sẽ tìm xâu E có độ dài nhỏ nhất vì tính dễ quên của mình.

Input

• Dòng đầu tiên là số lượng xâu ghi thêm - N;
• N dòng tiếp theo, dòng thứ i ghi xâu B[i] khác rỗng;
• Dòng cuối cùng là xâu A - mật khẩu của Bờm;

Output

• Một dòng duy nhất là xâu E cần tìm - nếu có nhiều xâu thỏa, hãy in ra xâu có thứ tự từ điển nhỏ nhất.

Example

Input:
1
abacad
abbcaaa

Output:
aa

Giới hạn

• LA = Length(A) <= 1000000 (Length(A) là độ dài xâu A);
• S = Length(B[1]) + Length(B[2]) + ... + Length(B[n]) <= 1000000;
• Các xâu chỉ gồm chữ cái la tin 'a'..'z';
• Có 50% số test LA, S <= 100;