Mascot Naming

시간 제한2초메모리 제한2048 MB

요약
모든 s_i를 부분열로 포함하면서 t는 부분열로 포함하지 않는 문자열이 존재하는지 판정하고, 존재하면 하나를 출력한다.
난이도

보통10점 중 7점

유형
그리디, 문자열, 동적 계획법, 완전 탐색
정답자
아직 제출이 없습니다

문제

When organizing a big event, organizers often handle side tasks outside their expertise. For example, the chief judge of EUC 2025 must find a name for the event’s official mascot while satisfying certain constraints:

  • The name must include specific words as subsequences* , such as the event name and location. You are given the list s_1,s_2,…,s_ns\_1, s\_2, \dots , s\_n of the nn required words.
  • The name must not contain as a subsequence* the name t of last year’s mascot.

Please help the chief judge find a valid mascot name or determine that none exists.

*A string xx is a subsequence of a string yy if xx can be obtained from yy by erasing some characters (at any positions) while keeping the remaining characters in the same order. For example, abc is a subsequence of axbycz but not of acbxyz.

입력

The first line contains an integer nn (1≤n≤200,0001 ≤ n ≤ 200\\, 000) — the number of words that shall appear as subsequences.

The ii-th of the following nn lines contains the string s_is\_i (1≤∣s_i∣≤200,0001 ≤ |s\_i | ≤ 200\\, 000, s_is\_i consists of lowercase English letters) — the ii-th word in the list of words that shall appear as subsequences. The total length of these nn words is at most 200,000200\\, 000, i.e., ∣s_1∣+∣s_2∣+⋯+∣s_n∣≤200,000|s\_1| + |s\_2| + \cdots + |s\_n| ≤ 200\\, 000.

The last line contains the string tt (1≤∣t∣≤200,0001 ≤ |t| ≤ 200\\, 000, tt consists of lowercase English letters) — the name of last year’s mascot.

출력

Print YES if there is a valid name for the mascot. Otherwise, print NO.

If there is a valid name, on the next line print a valid name. The string you print must have length at most 1,000,0001\\, 000\\, 000 and must consist of lowercase English letters. One can prove that if a valid name for the mascot exists, then there is one satisfying these additional constraints.

If there are multiple solutions, print any of them.

예제4

  1. 예제 1

    입력
    2
    porto
    euc
    prague
    
    예상 출력
    YES
    poretuco
    
  2. 예제 2

    입력
    6
    credit
    debit
    money
    rich
    bank
    capitalism
    trap
    
    예상 출력
    YES
    moncrdebditeychankpitalism
    
  3. 예제 3

    입력
    2
    axiom
    choice
    io
    
    예상 출력
    NO
    
  4. 예제 4

    입력
    4
    aaa
    aab
    abb
    bbb
    ba
    
    예상 출력
    YES
    aaabbb