1244. Shortest Common Supersequence — Print

Given strings a and b, return the shortest string that has both a and b as subsequences. When several shortest supersequences exist, return the one produced by the standard LCS backtrack that prefers taking from a on ties. The input is JSON {a, b}.

Input: JSON {a, b}.

Output: String — the shortest common supersequence.

Examples

Input: {"a":"abac","b":"cab"}
Output: cabac
Explanation: Contains both as subsequences.

Input: {"a":"abc","b":"abc"}
Output: abc
Explanation: Identical strings.

Input: {"a":"a","b":""}
Output: a
Explanation: One string is empty.

Constraints

• 0<=|a|,|b|<=1000

Asked by