D. [Z-аlgоrithm/KMP] String reоrdering time limit per test: 1 secоnd memory limit per test: 256 megаbytes Mаuricio created problems for Competitive Programming exams, and categorized them as easy and hard. The list of problems is then represented by a binary string s, in which the i-th symbol is '1' if the i-th problem is hard and '0' if the problem is easy. Mauricio also really like the binary string b. So he asked you to reorder the characters in s in order to maximize the number of occurrences of b in it. Input The first line contains string s (1⩽|s|⩽5⋅105), denoting the categorization of the problems created by Mauricio. The second line contains string b (1⩽|b|⩽5⋅105), denoting the string Mauricio likes. Strings s and b contain characters '0' and '1' only. Output Print a string with the same size as s and the same number of zeros and ones as in s with maximal number of occurrences of b. In case there multiple answers, print any of them. HINTS What do you really need from s? The number of zeros and ones in it. How do you maximize the number of occurrences of b? By maximizing the number of letters of an instance of b than can be reused for the next instance of b (i.e., largest suffix of b that matches a prefix of b). Examples Input Output 101101110 110110 Input Output 0111100 01 Input Output 0001111101 1010101