ExpertAlgorithms50 points

Find the customers who signed up twice

A CRM team in Mumbai wants to merge duplicate customer records. Two records are linked when they have the same email key OR the same name key. Links are transitive: if A matches B and B matches C, all three form one group.

  • Email key: trim and lower-case the address and split it at @ into local part and domain. Cut the local part at the first + (everything from the + on is dropped). If the domain is gmail.com or googlemail.com, remove all dots from the local part and use gmail.com as the domain. The key is local@domain.
  • Name key: keep only the letters of the name in lower case and sort those letters alphabetically. So Ali Khan and Khan, Ali share a key. The rule is deliberately strict and any anagram counts, even Amir Ali and Mira Ali.

Task: line 1 is N, then N lines of the form id,name,email (ids are unique words without commas, names contain no commas). Print one line for every group with two or more records: the ids separated by single spaces in input order. Print the groups ordered by the input position of their first record. If there are no groups print No duplicates.

Sample tests

Input

6
C1,Ali Khan,ali.khan@gmail.com
C2,Sara Lopez,sara@corp.mx
C3,Khan Ali,other@yahoo.com
C4,Ahmed Raza,a.hmed+news@googlemail.com
C5,Zoe Wu,ZOE@WU.cn
C6,Ahmad Raza,ahmed@gmail.com

Expected output

C1 C3
C4 C6

Input

2
A,John Smith,john@a.com
B,Maria Garcia,maria@b.com

Expected output

No duplicates

Your answer is also checked against 3 hidden tests.

Need a hint?

A union-find (or a graph search) over the records, linking records through their keys, is a clean way to get transitive groups.