Problem: The new camp by widely-known over the country Spring Programming Camp is going to start soon. Hence, all the team of friendly curators and teachers started composing the camp's schedule. After some continuous discussion, they came up with a schedule s, which can be represented as a binary string, in which the i-th symbol is '1' if students will write the contest in the i-th day and '0' if they will have a day off.

At the last moment Gleb said that the camp will be the most productive if it runs with the schedule t (which can be described in the same format as schedule s). Since the number of days in the current may be different from number of days in schedule t, Gleb required that the camp's schedule must be altered so that the number of occurrences of t in it as a substring is maximum possible. At the same time, the number of contest days and days off shouldn't change, only their order may change.

Could you rearrange the schedule in the best possible way?

Input

The first line contains string s (1 ⩽ |s| ⩽ 500 000), denoting the current project of the camp's schedule.

The second line contains string t (1 ⩽ |t| ⩽ 500 000), denoting the optimal schedule according to Gleb.

Strings s and t contain characters '0' and '1' only.

Output

In the only line print the schedule having the largest number of substrings equal to t. Printed schedule should consist of characters '0' and '1' only and the number of zeros should be equal to the number of zeros in s and the number of ones should be equal to the number of ones in s.

In case there multiple optimal schedules, print any of them.

Examples

Input


101101
110


Output


110110

Input


10010110
100011


Output


01100011


Input


10
11100


Output


01

Note

In the first example there are two occurrences, one starting from first position and one starting from fourth position.

In the second example there is only one occurrence, which starts from third position. Note, that the answer is not unique. For example, if we move the first day (which is a day off) to the last position, the number of occurrences of t wouldn't change.

In the third example it's impossible to make even a single occurrence.

Solution (in JAVA):

Solution:
// Author : AMIT KUMAR BARMAN (gearman_0712)
import java.io.*;
import java.util.*;

public class Camp{
    static final long modp =1000000007;
    static long x_ec=1,y_ec=0,d_ec =1;
    static long maxi=0;
    static boolean v1 =false ,v2 = false;
    static InputReader in = new InputReader(System.in);
    static OutputStream outputStream = System.out;
    static OutputWriter out = new OutputWriter(outputStream);

    static int[] computeLPSArray(String patt)
    {   int m=  patt.length();
        int Lps[]= new int[m];
        int i=1 ,len=0;
        Lps[0]=0;
        while( i<m)
        { if(patt.charAt(i)==patt.charAt(len))
          { len++;
              Lps[i]=len;
             i++;
          }
          else 
          {  if(len!=0)
              {len =Lps[len-1];
  
              }
              else //len=0
               Lps[i++]=len;
  
  
          }
  
  
  
        }
  
      return Lps;
  
    }
  
    public static void main (String args[]) throws IOException {
       String s1 = in.readString();
       String s2 = in.readString();
      

       int bi1[]= new int[2];
       int bi2[]= new int[2];
       for( int i=0;i<s1.length();i++)
       { int r= (int)s1.charAt(i) -48;
         bi1[r]++;
       }
       for( int i=0;i<s2.length();i++)
       { int r= (int)s2.charAt(i)-48;
         bi2[r]++;
       } 
       int rep=0;
       StringBuffer fg = new StringBuffer("");
         
         if(bi1[0]>=bi2[0] && bi1[1]>=bi2[1])
         { fg.append(s2);
            bi1[0] -= bi2[0];
            bi1[1] -= bi2[1];
            int Lps[] = computeLPSArray(s2);
            int h= Lps[s2.length()-1];
            int bi3[]= new int[2];
            for( int i=0;i<h;i++)
            { int r= (int)s2.charAt(i)-48;
                bi3[r]++;
              } 
            int flag=0;
              while(flag==0)
              {    for( int i=h;i<s2.length();i++)
                       {   int g = s2.charAt(i) - '0';
                              
                            if(bi1[g]>0)
                            { bi1[g]--;
                                fg.append(s2.charAt(i));

                            }
                            else
                            { flag=1;
                                break;
                              
                            }
                           
                       

                       }

              }
          for( int i=0;i<bi1[0];i++)
         fg.append('0');
        
         for(int i= 0;i<bi1[1] ;i++)
          fg.append('1');
         
          
         }
         else 
         {  out.println(s1);

         }
        
       
         
         out.println(fg);
        
    out.close();
}
    /*
    static Node lca(Node root,int x,int y)
    {if(root==null)
        return null;
        if(root.value>x &&root.value>y )
        return lca(root.left, x, y);
         if(root.value<x &&root.value<y )
        return lca(root.right, x, y);
    
        return root;
    }
    
    
    
    
    static Node common(Node root,int x,int y)
    {  if(root==null)
        return null;
        Node temp=null;
        if(root.value ==x)
        { v1= true;
            temp =new Node(x);
    
        }
        else if(root.value ==y)
        { v2= true;
            temp =new Node(y);
    
        }
      Node  lef =common(root.left, x, y);
     Node rig =common(root.right, x, y);
       if(temp!=null)
       return temp;
       if(lef ==null)
       return rig;
       if(rig==null)
       return lef;
       return root;
    }
    
    // static class Node {
    //     int value;
    //     Node left;
    //     Node right;
        
    //     Node(int value){
    //         this.value =value;
    //         right =null;
    //         left =null;
    //     }
    // }
    static Node insert(Node root,int v)
      { if(root==null)
        return new Node(v);
          if( v<=root.value)
          root.left =insert(root.left, v);
          else
          root.right =insert(root.right,v);
    
          return root;
    
        }
      
      static int minvalue(Node root)
        {
            while(root.left!=null)
              root =root.left;
              return root.value;
    
            
    
        }
 static int[] computeLPSArray(String patt)
  {   int m=  patt.length();
      int Lps[]= new int[m];
      int i=1 ,len=0;
      Lps[0]=0;
      while( i<m)
      { if(patt.charAt(i)==patt.charAt(len))
        { len++;
            Lps[i]=len;
           i++;
        }
        else 
        {  if(len!=0)
            {len =Lps[len-1];

            }
            else //len=0
             Lps[i++]=len;


        }



      }

    return Lps;

  }
        static Node delete(Node root ,int val)
     { if(root ==null)
        return root;
        if(val<root.value)
        root.left=delete(root.left, val);
       else if(val>root.value)
       root.right =delete(root.right,val);
       else {
       if(root.left==null)
         return root.right;
         else if(root.right==null)
         return root.left;
         root.value= minvalue(root.right);
         root.right =delete(root.right, root.value);
       
    
       }
       return root;
    
    
     }
     */
    /*
     static void inorder(Node root,OutputWriter out)
     { if(root!=null)
       {inorder(root.left ,out);
          out.print(root.value+" ");
          inorder(root.right, out);
    
       }
     }
     static void preorder(Node root ,OutputWriter out)
     { if(root!=null)
       { out.println(root.value+" ");
          preorder(root.left, out);
          preorder(root.right,out);
    
       }
    
     }
     static void postorder(Node root,OutputWriter out)
     { if(root!=null)
       { postorder(root.left, out);
           postorder(root.right ,out);
           out.print(root.value+" ");
       }
    
     }
     */
    // Input: Indices Range [0..size]
    // Invariant: A[l] <= key and A[r] > key 
    static long modExponential(long x,long n)
        {long result =1l;
            while(n>0l)
            { if(n%2==1)
                result =(x*result)%modp;
                x= (x*x)%modp;
             n=n/2;
            }
            return result;
        }
      /*
    static int GetRightPosition(int A[], int l, int r, int key) 
    { 
        int m; 
    
        while( r - l > 1 ) 
        { 
            m = l + (r - l)/2; 
    
            if( A[m] <= key ) 
                l = m; 
            else
                r = m; 
        } 
    
        return l; 
    } 
    
    // Input: Indices Range -1 to size-1
    // Invariant: A[r] >= key and A[l] > key 
    static int GetLeftPosition(int A[], int l, int r, int key) 
    { 
        int m; 
    
        while( r - l > 1 ) 
        { 
            m = l + (r - l)/2; 
    
            if( A[m] >= key ) 
                r = m; 
            else
                l = m; 
        } 
    
        return r; 
    } 
    
    */
    
    public static long gcd(long a,long b)
    {
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
    public static int gcd(int a,int b)
    {
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
    public static int abs(int a,int b)
    {
        return (int)Math.abs(a-b);
    }
    public static long abs(long a,long b)
    {
        return (long)Math.abs(a-b);
    }
    public static int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
    public static int min(int a,int b)
    {
        if(a>b)
            return b;
        else 
            return a;
    }
    public static long max(long a,long b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
    public static long min(long a,long b)
    {
        if(a>b)
            return b;
        else 
            return a;
    }
     
    /*
    void countsort(int arr[],int n,int place)
    {
            int i,freq[range]={0};         //range for integers is 10 as digits range from 0-9
            int output[n];
            for(i=0;i<n;i++)
                    freq[(arr[i]/place)%range]++;
            for(i=1;i<range;i++)
                    freq[i]+=freq[i-1];
            for(i=n-1;i>=0;i--)
            {
                    output[freq[(arr[i]/place)%range]-1]=arr[i];
                    freq[(arr[i]/place)%range]--;
            }
            for(i=0;i<n;i++)
                    arr[i]=output[i];
    }
    void radixsort(ll arr[],int n,int maxx)            //maxx is the maximum element in the array
    {
            int mul=1;
            while(maxx)
            {
                    countsort(arr,n,mul);
                    mul*=10;
                    maxx/=10;
            }
    }*/
    
    /* BufferedReader bf =new BufferedReader (new InputStreamReader(System.in));
            int t= Integer.parseInt(bf.readLine());
            StringBuffer gh =new StringBuffer("");
            StringTokenizer  tk=new StringTokenizer(bf.readLine());
            long a= Long.parseLong(tk.nextToken());
    */
    
    
    static class Pair implements Comparable<Pair>
    {
        int a,b;
        Pair (int a,int b)
        {
            this.a=a;
            this.b=b;
        }
     
        public int compareTo(Pair o) {
            
            if(this.a!=o.a)
            return -Integer.compare(this.a,o.a);
            else
                return Integer.compare(this.b, o.b);
            //return 0;
        }
        public boolean equals(Object o) {
            if (o instanceof Pair) {
                Pair p = (Pair)o;
                return p.a == a && p.b == b;
            }
            return false;
        }
    
    
        public int hashCode(Object o) {
            Pair p = (Pair)o;
            return p.a* 31 +p.b;
        }
    
    } 
    
    static class Pair1 implements Comparable<Pair1>
    {
       char a;
       int b;
        Pair1 (char a,int b)
        {
            this.a=a;
            this.b=b;
        }
     
        public int compareTo(Pair1 o) {
            
            if(this.a!=o.a)
            return Integer.compare(this.a,o.a);
            else
                return Integer.compare(this.b, o.b);
            //return 0;
        }
        public boolean equals(Object o) {
            if (o instanceof Pair1) {
                Pair1 p = (Pair1)o;
                return p.a == a && p.b == b;
            }
            return false;
        }
    
    
        public int hashCode(Object o) {
            Pair1 p = (Pair1)o;
            return (int)p.a* 31 +(int)p.b;
        }
    
    } 
    /*
    //public void solve(int testNumber, InputReader in, OutputWriter out) 
    
    // in case u want to print And take input inside and static method
    static void extendedEuclid( long A,  long B) {
        if(B==0)
        {d_ec=A;
          x_ec =1;
          y_ec=0;
      
        }
        else{
            extendedEuclid(B, A%B);
             long temp =x_ec;
            x_ec = y_ec;
            y_ec =temp -(A/B)*y_ec;
        }
          
      }
      static long modInverse( long A,  long M) //A and M are coprime i.e. Ax+My=1. In the extended Euclidean algorithm, x is the modular multiplicative inverse of A under modulo M.
      {
          extendedEuclid(A,M);
          return (x_ec%M+M)%M;    //x may be negative
      }
      
      static boolean checkprime(int N) {
          int count = 0;
          for( int i = 1;i * i <=N;++i ) {
               if( N % i == 0) {
                   if( i * i == N )
                           count++;
                   else       // i < sqrt(N) and (N / i) > sqrt(N)
                           count += 2;
                }
          }
          if(count == 2)
               return true;
          else
            return false;
      }
      static void factorize (long a,HashMap<Long,Long> map)
        {
          long i=2;
          for( i=2;i*i<=a;i++)
          {
            if(a%i==0){
                long f=0;  
            while((a>0)&&(a%i==0))
            { 
                a= a/i;
                f++;
            }
            map.put(i, f);
          
            }
          }
          if(a>1l)
            map.put(a, 1l);
    
        }*/
    
    /*static class DSU
    {
    int parent[];
    int rank[];
    int state[];
    DSU(int n)
    {parent=new int[n];
    rank=new int[n];
    state=new int[n+1];
        
    }
    void makeset(int n)
    {
    for(int i=0;i<n;i++)
    {
    parent[i]=i;
    rank[i]=1;
    state[i]=0;// for jamboard question
    }
    }
    void decP(int x)// for jamboard question
    {
    if(state[x]>0)
    state[x]--;
    }
    void incP(int x)// for jamboard question
    {
    state[x]++;
    }
    boolean getP(int x)// for jamboard question
    {
    return (state[x]!=0);
    }
    int find(int x)
    {
    if(x==parent[x])
    return x;
    parent[x]=find(parent[x]);
    return parent[x];
    }
    void union(int x,int y)
    {
    int xRoot=find(x);
    int yRoot=find(y);
    if(xRoot==yRoot)
    return;
    if(rank[xRoot]>rank[yRoot])
    {
    parent[yRoot]=xRoot;
    state[xRoot]+=state[yRoot];// for jamboard question
    }
    else if(rank[xRoot]<rank[yRoot])
    {
    parent[xRoot]=yRoot;
    state[yRoot]+=state[xRoot];// for jamboard question
    }
    else
    {
    parent[xRoot]=yRoot;
    rank[yRoot]++;
    state[yRoot]+=state[xRoot];// for jamboard question
    }
    }
    }
    */    

}/*
class DSU
{
int parent[];
int rank[];
int diff[];
DSU(int sd){
parent=new int[sd];
rank=new int[sd];
diff=new int[sd];
}
void makeset(int n)
{

for(int i=0;i<n;i++)
{
parent[i]=i;
rank[i]=1;
diff[i]=0;
}
}

int find (int x) {
    if (x == parent [x]) return x;
    int t = parent [x];
    parent [x] = find (parent [x]);
    diff [x] ^= diff [t];
    return parent [x];
}
boolean union(int x,int y,int w)
{
int xRoot=find(x); 
int yRoot=find(y);
if(xRoot==yRoot)
{ if(w != (diff[x]^diff[y]))
         return false;
}

else if(rank[xRoot]>rank[yRoot])
{
parent[yRoot]=xRoot;
diff[yRoot]= diff[x]^diff[y]^w;
}
else if(rank[xRoot]<rank[yRoot])
{
parent[xRoot]=yRoot;
diff[xRoot]= diff[x]^diff[y]^w;

}
else
{
parent[xRoot]=yRoot;
rank[yRoot]++;
diff[xRoot]= diff[x]^diff[y]^w;
}
return true;
}
}*/
class Gnode{
    int value;
    List<Gnode> neighbours;
    Gnode(int x)
   {value=x;
    neighbours =new ArrayList<>();
   }
   
   }
 class Node{
       int value;
       Node left;
       Node right;
       Node(int qw){
           this.value = qw;
           this.left = null;
           this.right = null;
       }
   }
   
   class SegTree{
       long[] seg;
       int[] map;
       long[] arr;
       SegTree(int n,long[] a){
           seg=new long[4*n];
           arr=a;
           map=new int[n+1];
       }
       void build(int low,int high, int pos) {
           if(low==high) {
               map[low]=pos;
               seg[pos]=arr[low];
           }
           else {
               int middle=(low+high)/2;
               build(low,middle,2*pos+1);
               build(middle+1,high,2*pos+2);
               seg[pos]=Math.max(seg[2*pos+1], seg[2*pos+2]);
           }
       }
       void update(int low,int high, int pos,int elpos, long value) {
           if(low==high) {
               seg[pos]=value;
           }
           else {
               int middle=(low+high)/2;
               if(elpos<=middle) {
                   update(low,middle,2*pos+1,elpos,value);
               }
               else update(middle+1,high,2*pos+2,elpos,value);
               seg[pos]=Math.max(seg[2*pos+1], seg[2*pos+2]);
           }
       }
   }

class MinHeap {
   int size;
   int maxsize;
   int heap[];
   MinHeap(int maxsize,int size)           //size = capacity
   {this.size=size;
    this.maxsize= maxsize;
    heap = new int[maxsize];

   }
   boolean isEmpty()
   {return size==0;
}
   int peek()
   {if(isEmpty())
     return -99999;
     return heap[0];

   }
   int remove()
   {if(isEmpty())
    return -99999;
    int minItem = heap[1];
    heap[1]= heap[size];
    size --;
    heapifyDown(1);
    return minItem;
   }
    void print()
    {
      System.out.println(Arrays.toString(heap)); 
    }
   boolean add( int item)
   {  if(size>= maxsize)
          return false;
          heap[size+1]= item;
          size++;
          heapifyUp(size);
          return true;

   }
    void heapifyDown( int i)
    { int left = 2*i;
        int right = 2*i +1;
        int smallest =i;
        if(left<= size  && heap[left]<heap[smallest])
          smallest =left;
          if(right<= size  && heap[right]<heap[smallest])
          smallest =right;
          if(smallest!=i)
          {  int temp =heap[i];
             heap[i]= heap[smallest];
             heap[smallest]=temp;
             heapifyDown(smallest);

          }

    }
    void heapifyUp( int i)
    {
        int parent = i/2;
        if( parent>0 && heap[parent]>heap[i])
        { int temp =heap[parent];
            heap[parent]= heap[i];
            heap[i]=temp;
            heapifyUp(parent);

        }
    }}
    class MaxHeap {
        int size;
        int maxsize;
        int heap[];
        MaxHeap(int maxsize,int size)           //size = capacity
        {this.size=size;
         this.maxsize= maxsize;
         heap = new int[maxsize];
     
        }
        void buildHeap(int arr[])
        {size = arr.length+1;
         for(int i=0;i<arr.length;i++)
        heap[i+1]= arr[i];
        for( int i=size/2;i>=1;i--)
        {heapifyDown(i);
            
        }

         
        }
        boolean isEmpty()
        {return size==0;
     }
        int peek()
        {if(isEmpty())
          return -99999;
          return heap[0];
     
        }
        int remove()
        {if(isEmpty())
         return -99999;
         int minItem = heap[1];
         heap[1]= heap[size];
         size --;
         heapifyDown(1);
         return minItem;
        }
         void print()
         {
           System.out.println(Arrays.toString(heap)); 
         }
        boolean add( int item)
        {  if(size>= maxsize)
               return false;
               heap[size+1]= item;
               size++;
               heapifyUp(size);
               return true;
     
        }
         void heapifyDown( int i)
         { int left = 2*i;
             int right = 2*i +1;
             int largest =i;
             if(left<= size  && heap[left]>heap[largest])
               largest =left;
               if(right<= size  && heap[right]>heap[largest])
               largest =right;
               if(largest!=i)
               {  int temp =heap[i];
                  heap[i]= heap[largest];
                  heap[largest]=temp;
                  heapifyDown(largest);
     
               }
     
         }
         void heapifyUp( int i)
         {
             int parent = i/2;
             if( parent>0 && heap[parent]<heap[i])
             { int temp =heap[parent];
                 heap[parent]= heap[i];
                 heap[i]=temp;
                 heapifyUp(parent);
     
             }
         }







}
 class InputReader
{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;
 
    public InputReader(InputStream stream)
    {
        this.stream = stream;
    }
 
    public int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars)
        {
            curChar = 0;
            try
            {
                numChars = stream.read(buf);
            } catch (IOException e)
            {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }
 
    public int readInt ()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-')
        {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do
        {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
 
    public String readString ()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do
        {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }
    public String readLine() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isEndOfLine(c));
        return res.toString();
    }
    
 
    public double readDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, readInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }
    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
    public boolean isSpaceChar(int c)
    {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
 
    public String next()
    {
        return readString();
    }
 
    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
    public boolean isEndOfLine(int c) {
        return c == '\n' || c == '\r' || c == -1;
    }
}
class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0) {
                writer.print(' ');
            }
            writer.print(objects[i]);
        }
    }

    public void println(Object... objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

}