Chef Watson uses a social network called ChefBook, which has a new feed consisting of posts by his friends. Each post can be characterized by f - the identifier of the friend who created the post, p - the popularity of the post(which is pre-calculated by ChefBook platform using some machine learning algorithm) and s - the contents of the post which is a string of lower and uppercase English alphabets.
Also, Chef has some friends, which he has marked as special.
The algorithm used by ChefBook for determining the order of posts in news feed is as follows:

- Posts of special friends should be shown first, irrespective of popularity. Among all such posts the popular ones should be shown earlier.
- Among all other posts, popular posts should be shown earlier.

Given, a list of identifiers of Chef's special friends and a list of posts, you have to implement this algorithm for engineers of ChefBook and output the correct ordering of posts in the new feed. 

-----Input-----
First line contains N, number of special friends of Chef and M, the number of posts. Next line contains N integers A1, A2, ..., AN denoting the identifiers of special friends of Chef. Each of the next M lines contains a pair of integers and a string denoting f, p and s, identifier of the friend who created the post, the popularity of the post and the contents of the post, respectively. It is guaranteed that no two posts have same popularity, but the same friend might make multiple posts.

-----Output-----
Output correct ordering of posts in news feed in M lines. Output only the contents of a post.

-----Constraints-----
- 1 ≤ N, M ≤ 103
- 1 ≤ Ai, f, p ≤  105
- 1 ≤ length(s) ≤  100

-----Example-----
Input:
2 4
1 2
1 1 WhoDoesntLoveChefBook
2 2 WinterIsComing
3 10 TheseViolentDelightsHaveViolentEnds
4 3 ComeAtTheKingBestNotMiss

Output:
WinterIsComing
WhoDoesntLoveChefBook
TheseViolentDelightsHaveViolentEnds
ComeAtTheKingBestNotMiss

-----Explanation-----

First we should show posts created by friends with identifiers 1 and 2. Among the posts by these friends, the one with more popularity should be shown first.

Among remaining posts, we show those which are more popular first.

Difficulty: interview

Starter code:

Solutions:
import sys
ans=0
n,m=list(map(int,input().split()))
aaaaa=100
li=list(map(int,input().split()))
non_special,special=[],[]
for i in range(m):
 ans+=1
 f,p,s=list(map(str,input().split()))
 f=int(f)
 poww=pow(1,2)
 p=int(p)
 if f not in li:
  ans+=1
  non_special.append((p,s))
  ans-=1
 else:
  ans+=1
  special.append((p,s))
  
non_special.sort(reverse=True)
aaaa=pow(1,2)
special.sort(reverse=True)

for temp in range(len(special)):
 ans+=1
 print(special[temp][1])
for temp in non_special:
 ans+=1
 print(temp[1])

N,M=list(map(int,input().split()))
array=list(map(int,input().split()))
full=[[0]*3]*M
final=[[0]*3]*M
init=[[0]*3]*M
for i in range(M):
 full[i]=input().split()
 full[i][1]=int(full[i][1])
 full[i][0]=int(full[i][0])
k=0
y=0

for j in range(M):
 if (full[j][0] in array):
  final[k]=full[j]
  k+=1
 else:
  init[y]=full[j]
  y+=1

final=sorted(final,key=lambda x: x[1])
init=sorted(init,key=lambda x: x[1])
for i in range(k):
 print(final[M-1-i][2])
for i in range(y):
 print(init[M-1-i][2])


n, m = list(map(int, input().split()))
S = list(map(int, input().split()))
special = []
nonspecial = []
for i in range(m):
 A = input().split()
 if int(A[0]) in S:
  special.append(A)
 else:
  nonspecial.append(A)

special.sort(key=lambda x: int(x[1]), reverse=True)
nonspecial.sort(key=lambda x: int(x[1]), reverse=True)

for i in special:
 print(i[2])
for i in nonspecial:
 print(i[2])


n,u=input().split()
a=input().split()
x=dict()
t=list()
v=list()
for i in range(int(u)):
 b=input().split()
 x[int(b[1])]=[b[0],b[2]]
for i in list(x.items()):
 if(i[1][0] in a):
  v.append(i[1][1])
 else:
  t.append(i[1][1])
for i in v[::-1]:
 print(i)
for i in t[::-1]:
 print(i)

import operator
n,m=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
h=[0]*100001
for x in a:
 h[x]=1
ss={}
ns={}

while m:
 m-=1
 f,p,s=[x for x in input().split()]
 f=int(f)
 p=int(p)
 if h[f]==1:
  ss[p]=[f,s]
 else:
  ns[p]=[f,s]

ss = sorted(list(ss.items()), key=operator.itemgetter(0),reverse=True)
ns = sorted(list(ns.items()), key=operator.itemgetter(0),reverse=True)
for x in ss:
 print(x[1][1]) 
for x in ns:
 print(x[1][1]) 




import numpy

inp = list(map(int, input().split()))

n = inp[0]
m = inp[1]

inp1 = list(map(int, input().split()))

arrayf = []

arrayp = []

arrays = []

arrayfBest = []

arraypBest = []

arraysBest = []

countBest = 0
countOther = 0
for i in range(m):
 inp3 = list(input().split())



 if int(inp3[0]) in inp1:
  arrayfBest.append(int(inp3[0]))
  arraypBest.append(int(inp3[1]))

  arraysBest.append(inp3[2])
  countBest = countBest + 1

 else:
  arrayf.append(int(inp3[0]))
  arrayp.append(int(inp3[1]))

  arrays.append(inp3[2])

  countOther = countOther + 1

 

sortedString = [x for y, x in sorted(zip(arraypBest, arraysBest))]

for j in range(countBest):
 print(sortedString[countBest - j -1])


sortedString1 = [x for y, x in sorted(zip(arrayp, arrays))]

for j in range(countOther):
 print(sortedString1[countOther - j - 1])













x=input().split()
n=int(x[0])
m=int(x[1])
y=input().split()
fr_post=dict()
n_post=dict()
for i in range(0,m):
 z=input().split()
 if(z[0] in y):
  fr_post[int(z[1])]=z[2]
 else:
  n_post[int(z[1])]=z[2]

for key in sorted(fr_post,reverse=True):
 print(fr_post[key])
for key in sorted(n_post,reverse=True):
 print(n_post[key])


n,m=list(map(int,input().split()))
special=list(map(int,input().split()))
arr1=[]
arr2=[]
for i in range(m):
 f,p,s=list(map(str,input().split()))
 f,p=int(f),int(p)
 if f in special:
  arr1.append([f,p,s])
 else:
  arr2.append([f,p,s])
arr1=sorted(arr1,key=lambda x:x[1])
arr2=sorted(arr2,key=lambda x:x[1])
arr1.reverse()
arr2.reverse()
for i in range(len(arr1)):
 print(arr1[i][2])
for i in range(len(arr2)):
 print(arr2[i][2])



N,M=list(map(int,input().split()))
a=list(map(int,input().split()))
d=dict()
f,o=[],[]
for i in range(M):
 st=input().split()
 d[int(st[1])]=[st[2],int(st[0])]
 
for i in d:
 if d[i][1] in a:
  f.append(i)
 elif d[i][1] not in a:
  o.append(i)

f.sort()
o.sort()
for i in f[::-1]:
 print(d[i][0])
for j in o[::-1]:
 print(d[j][0])

n,m=list(map(int,input().split()))
friends=list(map(int,input().split()))
friendsPost=[]
otherPost=[]

for friend in range(m):
 
 f,p,s=list(map(str,input().split()))
 if int(f) in friends:
  
  friendsPost.append([f,int(p),s])
  
 else:
  
  otherPost.append([f,int(p),s])
  
  
friendsPost.sort(key=lambda x:x[1])
otherPost.sort(key=lambda x:x[1]) 

for post in range(len(friendsPost)-1,-1,-1):
 print(friendsPost[post][-1])
 
 
for post in range(len(otherPost)-1,-1,-1):    
 print(otherPost[post][-1])

n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort()
l2=[]
l4=[]
l5=[]
l6=[]
l7=[]
for i in range(m):
 l3=input().split()
 l3[0]=int(l3[0])
 l3[1]=int(l3[1])
 l2.append(l3)

for k in range(len(l2)):
 if l2[k][0] in l:
  l4.append(k)
  l6.append(l2[k][1])
 else:
  l5.append(k)
  l7.append(l2[k][1])

while True:
 max=0
 c=0
 for i in range(len(l6)):
  if l6[i]>max:
   max=l6[i]
   c=i
 if max==0:
  break
 y=int(l4[c])
 print(l2[y][2])
 l6[c]=0
 
while True:
 max=0
 c=0
 for i in range(len(l7)):
  if l7[i]>max:
   max=l7[i]
   c=i
 if max==0:
  break
 y=int(l5[c])
 print(l2[y][2])
 l7[c]=0




n,m= list(map(int,input().strip().split()))
spcl=[int(num) for num in input().strip().split()]
spclpost=[' ']*100000
post=[' ']*100000
for i in range(m):
 f,p,s=input().strip().split()
 f=int(f)
 p=int(p)
 if(f in spcl):
  spclpost[p-1]=s
 else:
  post[p-1]=s
for j in range(100000,0,-1):
 if(spclpost[j-1]!=' '):
  print(spclpost[j-1])
for j in range(100000,0,-1):
 if(post[j-1]!=' '):
  print(post[j-1])

n,m=input().split()
K=list(map(int,input().split()))
L=[]
M=[]
for i in range(int(m)):
 a,b,c=input().split()
 if int(a) in K:
  M.append([int(b),c])
 else:
  L.append([int(b),c])
M.sort()
M.reverse()
L.sort()
L.reverse()
for i in range(len(M)):
 print(M[i][1])
for i in range(len(L)):
 print(L[i][1])
 


n,m = list(map(int,input().split()))
N = list(map(int,input().split()))
P1 = []
p1 = []
P2 = []
p2 = []
for i in range(m):
 X1,X2,X3 = list(map(str,input().split()))
 X = []
 X.append(int(X1))
 X.append(int(X2))
 X.append(X3)
 if int(X[0]) in N:
  P1.append(X)
  p1.append(int(X[1]))
 else:
  P2.append(X)
  p2.append(int(X[1]))
 x = []

p1.sort(reverse=True)
p2.sort(reverse=True)

for x in range(len(p1)):
 for xx in range(len(P1)):
  if int(P1[xx][1]) == int(p1[x]):
   print(P1[xx][2])
   del P1[xx]
   break

for x in range(len(p2)):
 for xx in range(len(P2)):
  if int(P2[xx][1]) == int(p2[x]):
   print(P2[xx][2])
   del P2[xx]
   break

n,m=list(map(int,input().split()))
splFriends=input().split()
sppost=[]
posts=[]
for i in range(m):
 f,p,s=input().split()
 p=int(p)
 if f in splFriends:
  sppost.append([p,s])
 else:
  posts.append([p,s])
 sppost=sorted(sppost,key= lambda x:x[0])[::-1]
 posts=sorted(posts,key= lambda x:x[0])[::-1]
 
for post in sppost:
 print(post[1])
for post in posts:
 print(post[1])

from operator import itemgetter
n,m=list(map(int,input().split()))
x=list(map(int,input().split()))
arr=[]
dic={}
#m=[]
two=[]
for i in range(m):
 y=list(map(str,input().split()))
 a=int(y[0])
 b=int(y[1])
 flag=0
 if a in x:
  two.append([b,y[2]])
 else: 
  arr.append([b,y[2]])
for i in x:
 if i in dic:
  for j in dic[i]:
   print(j)
two=sorted(two,key=itemgetter(0),reverse=True)
arr=sorted(arr,key=itemgetter(0),reverse=True)
for i in two:
 print(i[1])
for i in arr:
 print(i[1])
 
 
'''if a in dic:
     dic[a].append(y[2])
     flag=1
    else:
     dic[a]=[y[2]]
     flag=1'''
 #if flag==0: