Longest Unique Substring Without Repeating Characters

You are given a string s consisting of lowercase or uppercase letters and/or digits. Your task is to determine the longest substring of s which does not contain any repeating characters. In other words, if you denote the substring as s[i...j] then for every pair of indices p and q in this range (i ≤ p, q ≤ j), it must hold that if p ≠ q then s[p] ≠ s[q].

If there exists more than one substring with the same maximum length, output the one that appears first in s. The problem can be formulated mathematically as finding indices i and j such that:

$$\text{maximize } (j - i + 1) \quad \text{subject to} \quad \forall p, q \in [i,j],\, p \neq q \Rightarrow s[p] \neq s[q]. $$

The input is provided as a single string through standard input, and your result should be printed to standard output.

inputFormat

The input consists of a single line containing the string s. The string can include letters, digits, and other standard characters. It is guaranteed that the length of s is at most 10⁵.

outputFormat

Output the longest substring of the given string that does not contain any repeating characters. If multiple answers exist, output the first occurring one. The output should be printed to standard output.

## sample

abcabcbb

abc