Minimum Window Substring

Problem statement

A text scanner must find the shortest contiguous section of a source string containing every character of a requested string, including repeated characters. Matching is case-sensitive. If multiple shortest sections exist, choose the one starting earliest in the source. Print NONE if no section qualifies.

Input format

First line: source string s. Second line: required string t.

Output format

Print the chosen substring, or NONE if no valid window exists.

Constraints

1 <= lengths of s and t <= 100000; characters are English uppercase or lowercase letters.

Sample input

ADOBECODEBANC
ABC

Sample output

BANC