D. The New CEO of CloseAI
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Fahim had only been at CloseAI for two weeks, but he already knew two things with absolute certainty:

  1. The company's tokenization system was held together with duct tape, prayers, and legacy Bash scripts.
  2. He did not like the CEO, Saltman, who walked around the office wearing sunglasses indoors and calling everyone "chat-bros".

One morning, Saltman burst into the engineering floor holding a pile of printed stack traces like a kindergarten art project gone wrong.

"Tokenization is broken again!" he shouted. "If we don't fix this, our shareholders will replace me with a bag of potatoes!"

Fahim stared at him. A thought crossed his mind: If I fix this, maybe they'll replace him with me.

The challenge? Every model at CloseAI was panicking because they had forgotten how to tokenize words. They needed a clean implementation of tokenization, or as Saltman called it, "that spicy token cruncher thing".

So Fahim sat down, cracked his knuckles, and dove into the problem:

You're given $$$n$$$ lowercase English words, and you must apply tokenization to them, like a hero saving a collapsing startup. Each unique character from 'a' to 'z' starts as its own token — basic, simple, unlike Saltman's understanding of machine learning.

Then comes the tokenization loop:

Fahim has to count all adjacent token pairs across all words. He must find the most frequent adjacent token— the one that appears more than anything else. If there's a tie, he chooses the lexicographically smallest adjacent token. Then he merges that pair into a new token, like smashing two puzzle pieces together with pure engineering rage. Fahim also has to handle overlapping cases properly. For example, in a word like 'aaa', the pair 'aa' appears twice but overlaps — he only merges the leftmost occurrence first, so 'aaa' becomes ['aa', 'a'] in one merge step.

He repeats this: count, pick, merge, replace everywhere. He keeps going until there are no adjacent pairs of tokens. That's when the algorithm ends, and all the final tokens must be printed.

As he coded, something incredible happened: the errors stopped. The server logs went silent. The models started tokenizing again without screaming across the datacenter. Before anyone realized, the entire company was running smoothly.

Saltman strutted over and said, "Nice work, chat-bro. You've saved CloseAI."

Fahim smiled. One step closer to taking your job, Saltman.

Input

A single line containing a string $$$s$$$ — one or more words separated by single spaces.

Each word is a valid lowercase English dictionary word consisting only of characters from a to z.

It is guaranteed that each word has length at most $$$10$$$ and the total number of words does not exceed $$$10^5$$$.

Output

Print each unique token on a separate line in lexicographically sorted order.

Example
Input
cat bat rat
Output
a
at
b
bat
c
cat
r
rat
t
Note

In the first example:

Initial state:

Each character is a token: c, a, t, b, r.

Words: cat $$$\to$$$ [c, a, t], bat $$$\to$$$ [b, a, t], rat $$$\to$$$ [r, a, t]

Step 1: Count adjacent pairs

  • 1st: [c, a, t]: (c, a) $$$\to$$$ "ca", (a, t) $$$\to$$$ "at"
  • 2nd: [b, a, t]: (b, a) $$$\to$$$ "ba", (a, t) $$$\to$$$ "at"
  • 3rd: [r, a, t]: (r, a) $$$\to$$$ "ra", (a, t) $$$\to$$$ "at"

Frequencies: "at" appears 3 times, "ca", "ba", "ra" each appear 1 time.

Most frequent pair: "at" $$$\to$$$ merge (a, t) into token at.

After merge:

cat $$$\to$$$ [c, at], bat $$$\to$$$ [b, at], rat $$$\to$$$ [r, at]

Step 2: Count adjacent pairs

  • 1st: [c, at]: (c, at) $$$\to$$$ "cat"
  • 2nd: [b, at]: (b, at) $$$\to$$$ "bat"
  • 3rd: [r, at]: (r, at) $$$\to$$$ "rat"

Frequencies: "cat", "bat", "rat" each appear 1 time (tie).

Lexicographically smallest: "bat" $$$ \lt $$$ "cat" $$$ \lt $$$ "rat" $$$\to$$$ merge (b, at) into token bat.

After merge:

cat $$$\to$$$ [c, at], bat $$$\to$$$ [bat], rat $$$\to$$$ [r, at]

Step 3: Count adjacent pairs

  • 1st: [c, at]: (c, at) $$$\to$$$ "cat"
  • 3rd: [r, at]: (r, at) $$$\to$$$ "rat"

Frequencies: "cat", "rat" each appear 1 time (tie).

Lexicographically smallest: "cat" $$$ \lt $$$ "rat" $$$\to$$$ merge (c, at) into token cat.

After merge:

cat $$$\to$$$ [cat], bat $$$\to$$$ [bat], rat $$$\to$$$ [r, at]

Step 4: Count adjacent pairs

  • 3rd: [r, at]: (r, at) $$$\to$$$ "rat"

Only one pair: "rat" $$$\to$$$ merge (r, at) into token rat.

Final state:

cat $$$\to$$$ [cat], bat $$$\to$$$ [bat], rat $$$\to$$$ [rat]

All unique tokens: a, at, b, bat, c, cat, r, rat, t

Output in lexicographically sorted order.