Linked Merchant Groups

A payments platform stores merchant profiles as flat dictionaries that have been serialized into rows of alternating keys and values:

[key1, value1, key2, value2, ...]

Every row contains exactly one merchant_id key, and its value is non-empty and unique across all rows. A row may also contain the identity fields email, phone and address, plus arbitrary additional fields such as country or mcc.

Two rows are directly linked when they share the same non-empty value under the same identity key. That is, rows A and B are directly linked if there is a key K in {email, phone, address} such that both rows contain K, both of their values for K are non-empty, and those two values are identical. An empty value never links anything, a value that matches under a different key never links anything, and additional fields (anything outside merchant_id, email, phone, address) never establish a link even when their values match.

A merchant group is a set of rows closed under the transitive closure of direct links: if A is linked to B and B is linked to C, then A, B and C belong to the same group. Every row belongs to exactly one group, and a row linked to nothing forms a group of its own.

Report every merchant group, identified by the merchant_id values it contains.

Function

linkedMerchantGroups(records: String[][]) -> List<List<String>>

Ordering

The answer is a list of groups, and it must be produced in exactly this order:

Inside each group, the merchant IDs are sorted lexicographically (ascending, by ASCII byte

value). 2. The groups themselves are sorted lexicographically by their complete sorted ID lists, comparing the lists element by element. When one list is a prefix of another, the shorter list comes first. Because merchant IDs are unique, no two groups compare equal.

Note that step 2 compares the ID lists, not the joined output lines.

Input Format

The first line contains a single integer n, the number of rows.

No key and no value contains the | character, and none of them begins or ends with a space.

Output Format

Print one line per merchant group, in the order defined above. Each line contains that group's merchant IDs, sorted lexicographically, joined by the | character.

Constraints

1 <= n <= 1000
Each row contains between 1 and 20 key-value pairs.
Keys and values consist of printable ASCII characters (codes 32 through 126) excluding |, with no leading or trailing space.
Each key has length between 1 and 30. Each value has length between 0 and 60.
Every row contains the key merchant_id exactly once, its value is non-empty, and no two rows share the same merchant_id value.
Within a row, each of merchant_id, email, phone and address appears at most once.
Every merchant_id value has length at most 20, and the total length of all merchant_id values is at most 12000.
The total number of characters across all keys and all values is at most 100000.

Examples

### Example 1

Input:

4
merchant_id|m1|email|a@x.com
merchant_id|m2|email|a@x.com|phone|222
merchant_id|m3|phone|222
merchant_id|m4|address|4 Main

Output:

m1|m2|m3
m4

m1 links to m2 by email, and m2 links to m3 by phone, so transitivity joins all three. m4 shares nothing and stands alone.

### Example 2

Input:

3
merchant_id|b|email|
merchant_id|a|email|
merchant_id|ab|country|IN

Output:

a
ab
b

All three email values are empty, so nothing links and every row is its own group. The group ["a"] precedes ["ab"] because "a" is a prefix of "ab", and ["ab"] precedes ["b"].

### Example 3

Input:

4
merchant_id|p1|email|dup|phone|dup
merchant_id|p2|phone|dup
merchant_id|p3|email|other|mcc|dup
merchant_id|p4|mcc|dup

Output:

p1|p2
p3
p4

p1 and p2 share the value dup under the same key phone, so they link. p3 also carries the value dup, but under mcc, which is not an identity field; p4 carries it under mcc too. A shared value only links rows when the key matches and the key is an identity field.