AlgoUniversity
  • Go Back
Alex's Love for Letters :

Author

Ayush Kumar Shaw

Difficulty Level : Medium

Submissions : 118

Asked In : Capgemini

Marks :10

: 1 | : 0

Alex had written all the $$$26$$$ letters from $$$a$$$ to $$$z$$$ on a board initially. Later, he rearranged those letters forming a new sequence. Alex gives you this new sequence of $$$26$$$ letters, another string $$$s$$$ of length $$$n$$$ and a number $$$k$$$.

Your task is to find and return the lexicographically smallest subsequence of length $$$k$$$ formed from string $$$s$$$, in accordance with the new sequence of letters provided to you.

Note: A subsequence of a string is formed by deleting a few (possibly $$$0$$$) characters from string. Given two strings, a string will be lexicographically smaller than other string, if it comes first in the dictionary.

Input

The first line contais $$$2$$$ integers $$$n,k(1 \leq k \leq n \leq 10^5)$$$.

The next line contains a string $$$sp$$$ of length $$$26$$$ - the new lexicographical order of alphabets. The next line contains a string $$$s$$$ of length $$$n$$$.

Output

Output a single string - the lexicographically smallest subsequence of length $$$k$$$.

Example

Input
4 2
abcdefghijklmnopqrstuvwxyz
rfov
Output
fo

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

You need to Log In
We're glad that you want to attempt this problem!

But to Run or Submit the Problem, you need to Log In.

Continue to Log In
Challenge Submitted!

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Challenge
Facing issue while trying to solve the problem! Don't worry, we got you covered!

Do let us know your issue.

Looks good!
Please enter your issue / feedback.

How do we get in touch with you?
Looks good!
Please enter your phone no.
Looks good!
Please enter your email address.