정화

방 안(문자열 $P$)에 흩어져 있는 잡동사니들(금지어 목록 $N_i$)을 모두 치워야 한다.

문자열 $P$에서 문자열 $N_i$의 모든 등장을 제거하는 프로그램을 작성하라. 더 정확히 말하면, $P$가 어떤 $N_i$를 부분 문자열로 포함하는 동안 다음을 반복한다. 어떤 $N_i$를 포함하는 $P$의 접두사 중 가장 짧은 것을 고른 뒤, 그 접두사가 포함하는 $N_i$ 중 가장 짧은 것을 삭제한다.

첫째 줄에 문자열 $P$가 주어진다. $P$는 숫자와 영어 대소문자로만 이루어지며, 길이는 최대 $10^5$이다. 이후 각 줄에는 정확히 하나의 문자열 $N_i$가 주어진다. $N_i$ 역시 숫자와 영어 대소문자로만 이루어지며, 모든 $N_i$의 길이의 합도 최대 $10^5$이다.

모든 $N_i$를 제거한 뒤 남은 $P$를 한 줄에 출력한다. 남은 $P$의 길이는 항상 1 이상임이 보장된다.