Under construction

Still being built. Things may change

Appointments

Interview

Time limit2sMemory limit1024 MB

Summary
Given a string, delete every occurrence of one character so that the remaining string is lexicographically smallest, and print it.
Level

Medium4 of 10

Topics
String, Greedy
Solved
No attempts yet

Problem

Dr. House hates waiting. He especially hates it when his patients have to wait in the queue for surgery. Usually this is not a problem, because the hospital administration always makes room for the best doctor. But now Foreman is at a conference, and House has to take desperate measures.

The hospital recently installed a new system for registering patients for surgery. House hired a hacker who broke into it. It turned out that each surgery appointment is stored in the database as a string made of lowercase Latin letters, digits, and underscores. The hacker is not very skilled, so he can change an appointment only by deleting all occurrences of one character from it. Also, from each string in the database, occurrences of only one character can be deleted, otherwise the string is marked invalid.

Dr. House has picked the record he wants to change, and he wants to know the lexicographically smallest string that can result from it.

Input

The first line contains the surgery appointment that House wants to fix, a string ss (1≤∣s∣≤1061 \le |s| \le 10^6) made of lowercase Latin letters, digits, and underscores.

Output

Print the lexicographically smallest string that Dr. House can obtain.

Examples2

  1. Example 1

    Input
    house_g_0101_first_january_angioplasty
    Expected output
    hose_g_0101_first_janary_angioplasty

  2. Example 2

    Input
    khoukse_k_1012_tenth_december_endoscopy
    Expected output
    house__1012_tenth_december_endoscopy