Give a string s of length l, and a set S of n sample string(s). We do reduce the string s using the set S by this way:

• Wherever S_i appears as a consecutive substring of the string s, you can delete (or not) it.
• After each deletion, you will get a new string s by joining the part to the left and to the right of the deleted substring.

Request

By that way, try to reduce the given string s to get a new string of minimum length. You can do delete for unlimited times.

Input

The Chef is planning on serving cupcakes for dessert. However, time is running out and the Chef has only enough time to bake one batch. Thankfully, the cupcake baking tin the Chef plans on using has barely enough spaces to ensure each guest receives one cupcake.

One unavoidable problem with running a restaurant is that occasionally a menu item cannot be prepared. This can be caused by a variety of reasons such as missing ingredients or malfunctioning equipment.

One unavoidable problem with running a restaurant is that occasionally a menu item cannot be prepared. This can be caused by a variety of reasons such as missing ingredients or malfunctioning equipment.