Minimum Window Substring

Hard

Given strings s and t, print the shortest substring of s that contains every character of t with multiplicity. Input format: - First line: s - Second line: t If multiple windows have the same length, print the earliest one. Print `EMPTY` if no valid window exists.

Constraints

1 <= s.length, t.length <= 2 * 10^5

Sample tests

Sample 1

Input

ADOBECODEBANC
ABC

Output

BANC

Sample 2

Input

a
aa

Output

EMPTY