#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// hàm tìm vị trí của số x đầu tiên (vì có thể có nhiều hơn 1 số x trong mảng này) trong một mảng được sắp xếp từ bé đến lớn
int binarySearch(int tmp[], int l, int r, int x){
if(r>=l){
int mid =l+(r-l)/2;
// vd tìm vị trí của số 2 trong mảng là 1 1 2 2 3 5 6 8 8;
// thì mid = 4, tmp[mid] = 2 nhung mid chưa phải là vị trí cần tìm, mà vị trí cần tìm phỉa là mid-1
// do đó đk để return mid thì a[mid-1] < x;
if((mid == 0 || tmp[mid-1] < x) && tmp[mid] == x) return mid;
if(x < tmp[mid]) return binarySearch(tmp, l, mid-1, x);
return binarySearch(tmp, mid+1, r, x);
}
return -1;
}
void sortAccording(int A[], int B[], int n, int m){
int temp[n], visited[n];
// mảng temp là mảng chứa những phần tử của mảng A nhưng đã được sắp xếp
// mảng visited để đánh dấu phần tử đã được thăm
for(int i = 0; i< n; i++){
temp[i] = A[i];
visited[i] = 0;
}
sort(temp, temp + n);
int index = 0;
for(int i = 0; i < m; i++){
int f = binarySearch(temp, 0, n-1, B[i]); // tìm vị trí đâu tiến của B[i] trong mảng temp
if(f == -1) continue; // nếu ko tìm thấy thì tiếp tục
for(int j = f; (j<n && temp[j] == B[i]); j++){
A[index++] = temp[j];
visited[j] = 1; // đánh dấu đã thăm
}
}
// điền nốt những phần tử ko có trong mảng B
for(int i = 0; i< n; i++){
if(visited[i] == 0){
A[index++] = temp[i];
}
}
}
void print(int A[], int n){
for(int i = 0; i< n; i++){
cout << A[i] <<" ";
}
cout << endl;
}
int main(){
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
int A[n], B[m];
for(int i = 0; i < n; i++){
cin >> A[i];
}
for(int i = 0; i < m; i++){
cin >> B[i];
}
sortAccording(A, B, n, m);
print(A,n);
}
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCi8vIGjDoG0gdMOsbSAgduG7iyB0csOtIGPhu6dhIHPhu5EgeCDEkeG6p3UgdGnDqm4gKHbDrCBjw7MgdGjhu4MgY8OzIG5oaeG7gXUgaMahbiAxIHPhu5EgeCB0cm9uZyBt4bqjbmcgbsOgeSkgdHJvbmcgbeG7mXQgbeG6o25nIMSRxrDhu6NjIHPhuq9wIHjhur9wIHThu6sgYsOpIMSR4bq/biBs4bubbgppbnQgYmluYXJ5U2VhcmNoKGludCB0bXBbXSwgaW50IGwsIGludCByLCBpbnQgeCl7CiAgICBpZihyPj1sKXsKICAgICAgICBpbnQgbWlkID1sKyhyLWwpLzI7CiAgICAgICAgLy8gdmQgdMOsbSB24buLIHRyw60gY+G7p2Egc+G7kSAyIHRyb25nIG3huqNuZyBsw6AgMSAxIDIgMiAzIDUgNiA4IDg7IAogICAgICAgIC8vIHRow6wgbWlkID0gNCwgdG1wW21pZF0gPSAyIG5odW5nIG1pZCBjaMawYSBwaOG6o2kgbMOgIHbhu4sgdHLDrSBj4bqnbiB0w6xtLCBtw6AgduG7iyB0csOtIGPhuqduIHTDrG0gcGjhu4lhIGzDoCBtaWQtMQogICAgICAgIC8vIGRvIMSRw7MgxJFrIMSR4buDIHJldHVybiBtaWQgdGjDrCBhW21pZC0xXSA8IHg7CiAgICAgICAgaWYoKG1pZCA9PSAwIHx8IHRtcFttaWQtMV0gPCB4KSAmJiB0bXBbbWlkXSA9PSB4KSByZXR1cm4gbWlkOwogICAgICAgIGlmKHggPCB0bXBbbWlkXSkgcmV0dXJuIGJpbmFyeVNlYXJjaCh0bXAsIGwsIG1pZC0xLCB4KTsKICAgICAgICByZXR1cm4gYmluYXJ5U2VhcmNoKHRtcCwgbWlkKzEsIHIsIHgpOwogICAgfQogICAgcmV0dXJuIC0xOwp9Cgp2b2lkIHNvcnRBY2NvcmRpbmcoaW50IEFbXSwgaW50IEJbXSwgaW50IG4sIGludCBtKXsKICAgIGludCB0ZW1wW25dLCB2aXNpdGVkW25dOwoKICAgIC8vIG3huqNuZyB0ZW1wIGzDoCBt4bqjbmcgY2jhu6lhIG5o4buvbmcgcGjhuqduIHThu60gY+G7p2EgbeG6o25nIEEgbmjGsG5nIMSRw6MgxJHGsOG7o2Mgc+G6r3AgeOG6v3AKICAgIC8vIG3huqNuZyB2aXNpdGVkIMSR4buDIMSRw6FuaCBk4bqldSBwaOG6p24gdOG7rSDEkcOjIMSRxrDhu6NjIHRoxINtCiAgICBmb3IoaW50IGkgPSAwOyBpPCBuOyBpKyspewogICAgICAgIHRlbXBbaV0gPSBBW2ldOwogICAgICAgIHZpc2l0ZWRbaV0gPSAwOwogICAgfQogICAgc29ydCh0ZW1wLCB0ZW1wICsgbik7CgogICAgaW50IGluZGV4ID0gMDsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBtOyBpKyspewogICAgICAgIGludCBmID0gYmluYXJ5U2VhcmNoKHRlbXAsIDAsIG4tMSwgQltpXSk7IC8vIHTDrG0gduG7iyB0csOtIMSRw6J1IHRp4bq/biBj4bunYSBCW2ldIHRyb25nIG3huqNuZyB0ZW1wCiAgICAgICAgaWYoZiA9PSAtMSkgY29udGludWU7IC8vIG7hur91IGtvIHTDrG0gdGjhuqV5IHRow6wgdGnhur9wIHThu6VjCiAgICAgICAgCiAgICAgICAgZm9yKGludCBqID0gZjsgKGo8biAmJiB0ZW1wW2pdID09IEJbaV0pOyBqKyspeyAKICAgICAgICAgICAgQVtpbmRleCsrXSA9IHRlbXBbal07CiAgICAgICAgICAgIHZpc2l0ZWRbal0gPSAxOyAvLyDEkcOhbmggZOG6pXUgxJHDoyB0aMSDbQogICAgICAgIH0KICAgIH0KCiAgICAvLyDEkWnhu4FuIG7hu5F0IG5o4buvbmcgcGjhuqduIHThu60ga28gY8OzIHRyb25nIG3huqNuZyBCIAogICAgZm9yKGludCBpID0gMDsgaTwgbjsgaSsrKXsKICAgICAgICBpZih2aXNpdGVkW2ldID09IDApewogICAgICAgICAgICBBW2luZGV4KytdID0gdGVtcFtpXTsKICAgICAgICB9CiAgICB9Cn0KCnZvaWQgcHJpbnQoaW50IEFbXSwgaW50IG4pewogICAgZm9yKGludCBpID0gMDsgaTwgbjsgaSsrKXsKICAgICAgICBjb3V0IDw8IEFbaV0gPDwiICI7CiAgICB9CiAgICBjb3V0IDw8IGVuZGw7Cn0KCmludCBtYWluKCl7CiAgICBpbnQgdDsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUodC0tKXsKICAgICAgICBpbnQgbiwgbTsKICAgICAgICBjaW4gPj4gbiA+PiBtOwogICAgICAgIGludCBBW25dLCBCW21dOwoKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKXsKICAgICAgICAgICAgY2luID4+IEFbaV07CiAgICAgICAgfQogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBtOyBpKyspewogICAgICAgICAgICBjaW4gPj4gQltpXTsKICAgICAgICB9CiAgICAgICAgc29ydEFjY29yZGluZyhBLCBCLCBuLCBtKTsKICAgICAgICBwcmludChBLG4pOwogICAgfQogICAgcmV0dXJuIDA7Cn0=