fast-sort-1

From the childhood we are taught that a comes before b then b comes before c and so on.So whenever we try to sort any given string we sort it in that manner only placing a before b and so on.But what happens if we initially change the pattern of sorting .This question arrived in Arav's  young mind. He thought what would the final string be like if z comes before a and a comes after c and so on. He got really puzzled in finding out the final sorted string.So he asks you for help.

He gives you two strings.One the pattern string P which decides the order of alphabets and the second that is the final string F which needs to be sorted. Help him by telling him the final sorted string.

Input:

The first line contains T denoting the number of test cases.Each test case consists of two lines.The first line contains the pattern string P indicating the relative ordering of alphabets and the second line contains the final string F to be sorted.

Output:

Print T lines where each line contains the sorted string.

Constraints:

1 ≤  T ≤ 10    

|P| = 26

1 ≤ |F| ≤ 10^5

Both the string consists only of  characters 'a'-'z'.

SAMPLE INPUT
2
wcyuogmlrdfphitxjakqvzbnes
jcdokai
miruqopsxthzdcnvkfbglwayje
wgfsyvno

SAMPLE OUTPUT
codijak
osnvfgwy

Difficulty: EASY
Tags: Greedy algorithms

Fundamentals

Sorting

Complete search
Skill types: Greedy algorithms

Sorting

Complete search

Starter code:

Solutions:
def mysort(alphabet):
	return ''.join(sorted(input(), key=lambda word: [alphabet.index(c) for c in word[0]]))

if __name__ == "__main__":
	for tc in range(int(input())):
		print(mysort(input()))


a=int(input())
for k in range(a):
	a=input()
	b=input()
	s=""
	for i in a:
		for j in b:
			if(j==i):
				s=s+i
	print(s)


for _ in range(eval(input())):
	mdict = {}
	sortlist = [char for char in input()]
	inlist = [char for char in input()]
	count = 0
	for val in sortlist:
		mdict[val] = count
		count += 1
	newlist = []
	for char in inlist:
		newlist.append(mdict[char])
	newlist.sort()
	finalstr = ''
	for val in newlist:
		finalstr += sortlist[val]
	print(finalstr)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

t=eval(input())
while t>0:
	x = input()
	d = dict()
	j=0
	for i in x:
		d[i]=j
		j=j+1
	y = input()
	d1 = dict()
	for i in y:
		if d[i] in list(d1.keys()):
			k = d1[d[i]] + str(i)
		else:
			k = str(i)
		d1[d[i]]= k
	s=""
	for i in d1:
		s=s+str(d1[i])
	print(s)
	t=t-1


n=input()
for i in range(int(n)):
	p=input()
	s=input()
	lst=[]
	for j in p:
		for k in s:
			if j==k:
				lst.append(k)
	print("".join(lst))			


n=eval(input())
for i in range(n):
	pat=input()
	li=list(pat)
	st=input()
	stt=list(st)
	for i in range(len(stt)):
		temp=stt[i]
		stt[i]=li.index(temp)
	stt.sort()
	for j in range(len(stt)):
		temp=int(stt[j])
		stt[j]=li[temp]
	print(''.join(stt))
	


noOfTestCases = int(input())
import collections

def customSort(string, orderString):

	#ordDic = collections.OrderedDict()
	#for c in orderString:
	#	ordDic[c] = 0
	#for c in string:
	#	ordDic[c] += 1
	#output = ""
	#for k in ordDic.keys():
	#	output += ordDic[k] * k
	#print output
	
	arr = []
	for i in range(1, 27):
		arr.append(0)
	for c in string:
		indexInPattern = orderString.index(c)
		arr[indexInPattern] += 1
	output = ""
	for i in range(0,26):
		output += arr[i] * orderString[i]
	print(output)	

for caseNo in range(1, noOfTestCases + 1):
	orderString = input()
	string = input()
	customSort(string, orderString)


times = int(eval(input()))
d = []
for x in range(times):
	d.append([input(), input()])
	
for a in d:
	news = ''
	for p in a[0]:
		for q in range(a[1].count(p)):
			if a[1].find(p) > -1:
				news = news + a[1][a[1].find(p)]
				a[1].replace(p, "", 1)
	print(news)
		


times = int(eval(input()))
d = []
for x in range(times):
	d.append([input(), input()])
	
for a in d:
	news = ""
	for p in a[0]:
		for q in range(a[1].count(p)):
			if a[1].find(p) > -1:
				news = news + a[1][a[1].find(p)]
				a[1].replace(p, "", 1)
	print(news)
		


import sys
for t in range(eval(input())):
	s1=input()
	s2=input()
	l1=len(s1)
	l2=len(s2)
	for i in range(l1):
		ch=s1[i]
		for j in range(l2):
			if ch==s2[j]:
				sys.stdout.write(ch)
	print() 



from collections import defaultdict
t=eval(input())
for k in range(t):
	d=defaultdict(int)
	s1=input()
	s2=input()
	for j in s2:
		d[j]+=1
	for i in s1:
		if i in d:
			print(i*d[i],end="")
	print()


noOfTestCases = int(input())
import collections

def customSort(string, orderString):
	ordDic = collections.OrderedDict()
	for c in orderString:
		ordDic[c] = 0
	for c in string:
		ordDic[c] += 1
	output = ""
	for k in list(ordDic.keys()):
		output += ordDic[k] * k
	print(output)	
			

for caseNo in range(1, noOfTestCases + 1):
	orderString = input()
	string = input()
	customSort(string, orderString)