You are given an array of strings entries.

Call a substring unique to an entry if, comparing case-insensitively, it occurs as a substring of that entry and of no other entry in the array. Occurring several times inside its own entry is fine.

For each entry, find its shortest unique substring. If several unique substrings share the shortest length, use the one that starts earliest in the entry. Wrap that occurrence in <u> and </u>.

Return the array with every entry marked this way, in the original order and with the original casing preserved.

It is guaranteed that every entry has at least one unique substring.

Examples

Example 1

Input: entries = ["Bird", "Cat", "Cow", "Dog", "Wallaby"]
Output: ["B<u>i</u>rd", "Ca<u>t</u>", "<u>Co</u>w", "Do<u>g</u>", "Wa<u>l</u>laby"]
Explanation:
"Bird": "b" also occurs in "Wallaby", so the first unique 1-letter substring is "i".
"Cow": every single letter occurs elsewhere ("c" in "Cat", "o" in "Dog", "w" in
"Wallaby"), so the answer has length 2; "Co" starts earlier than "ow".
"Wallaby": "l" is unique; its first occurrence is marked.