Shortest text that covers the letters

Problem

Given a text s and required letters t (letters may repeat), find the shortest part of s that contains every letter of t with at least the same counts. If there are several, print the leftmost. If none exists, print NONE.

Input, output and limits

Input: Line 1: s. Line 2: t. Both use lower-case letters.
Output: The part of s, or NONE.
Constraints: 1 ≤ |s|, |t| ≤ 10^5

Examples

Example 1

Input

adobecodebanc
abc

Output

banc

banc is the shortest.

Example 2

Input

a
b

Output

NONE

Hints

Try the problem first. Open one hint at a time.

Hint 1

Count how many of each required letter are still missing.

Hint 2

Grow the right end until nothing is missing, then shrink the left end as far as possible and record the window.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Longest run after a few repairshard
Two lost codeshard
Ways to reach the top floorhard
Longest balanced stretchhard
All valid bracket codeshard

All Python problems

Problem

Input, output and limits

Examples

Hints

More Pattern Practice problems

Problem

Input, output and limits

Examples

Hints

More Pattern Practice problems