MALD Contest 1 P1 - Scratch Cat and DDoS

View as PDF

Submit solution


Points: 3
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
wHy iS sCrAtCh.MiT.EdU bLoCkEd?!

One day, the Scratch Cat decided to use his hacker skills to shut down all websites in Yuboland. There are N websites available for him to hack. However, the Scratch Cat isn't intelligent enough to decide whether a website is hosted by Yuboland.

Therefore, he came up with a rule to determine that. The Scratch Cat believes that a website is hosted by Yuboland if

  1. yubo (all lowercase) is a substring of the website's URL,
  2. The website is directly before or after a website that satisfies the first rule.

Please determine the websites that the Scratch Cat will hack in alphabetical order.

Constraints

1 \le N \le 10^4

1 \le |s_i| \le 100

Input Specification

The first line will contain an integer N, the number of websites available for the Scratch Cat to hack.

The next N lines will each contain a string s_i, the URL for the i^\text{th} website.

Output Specification

Output the URLs of the websites that the Scratch Cat will hack in alphabetical order. Do not output duplicate URLs.

Sample Input

5
dmoj.ca
scratch.mit.edu
yubosucks.scratch
scratch.mit.edu
canada.ca

Sample Output

scratch.mit.edu
yubosucks.scratch

Explanation

The second URL, scratch.mit.edu, is directly before a URL containing yubo as a substring. The third URL directly contains yubo. The fourth URL is identical to the second and is directly after a URL containing yubo. The sorted list of URLs is then \{scratch.mit.edu, yubosucks.scratch\}. Notice two scratch.mit.edu URLs that satisfy the conditions, but only one is output because they are the same website.


Comments

There are no comments at the moment.