시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 34 19 18 58.065%

문제

큐에 들어있는 아이템과 큐 연산이 주어진다. 연산을 모두 수행한 이후에 큐에 들어있는 아이템을 구하는 프로그램을 작성하시오.

큐 연산은 다음과 같은 형식이다.

시작 위치 to 이동할 위치

즉, 시작 위치에 있는 아이템을 이동할 위치로 옮기는 연산이다.

예를 들어, 큐에 들어있는 아이템이 다음과 같은 경우를 생각해보자.

Item1 Item2 Item3 Item4 Item5

Item1의 위치가 1번 위치, Item2의 위치가 2번 위치 이다.

5 to 2 연산을 수행한 후의 큐는 다음과 같다.

Item1 Item5 Item2 Item3 Item4

큐 연산 여러 개를 동시에 수행할 수도 있다. 예를 들어, 큐의 내용이 다음과 같을 때

Item1 Item2 Item3 Item4 Item5 Item6 Item7 Item8

다음과 같연 연산을 수행하면

2 to 6; 6 to 3; 4 to 5; 5 to 2; 7 to 4; 8 to 1

큐는 다음과 같이 된다.

Item8 Item5 Item6 Item7 Item4 Item2 Item1 Item3

큐 연산에 포함되지 않는 아이템은 모두 순서를 유지하고, 빈 위치로 이동하게 된다. 이동 연산의 시작 위치가 갖거나, 이동할 위치가 갖는 연산은 주어지지 않는다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 아이템의 수 m과 큐 연산의 수 n이 주어진다. (1 ≤ m, n ≤ 20) 둘째 줄에는 큐에 들어있는 아이템의 이름이 주어진다. 이름은 알파벳과 숫자로 이루어져 있으며, 길이는 최대 8이다. 두 아이템의 이름이 같은 경우는 없다. 다음 n개 줄에는 큐 연산이 한 줄에 하나씩 주어진다.

출력

각 테스트 케이스마다, 입력으로 주어진 연산을 모두 수행한 뒤에 큐에 들어있는 원소를 출력한다.

예제 입력 1

3
5 1
alpha beta gamma delta epsilon
5 2
8 6
a b c d e f g h
2 6
6 3
4 5
5 2
7 4
8 1
3 2
foo bar baz
3 1
1 3

예제 출력 1

alpha epsilon beta gamma delta
h e f g d b a c
baz bar foo

힌트

W3sicHJvYmxlbV9pZCI6IjQ1NDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJRIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwNTBcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1YWNmYyBcdWQwNTAgXHVjNWYwXHVjMGIwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWMyMThcdWQ1ODlcdWQ1NWMgXHVjNzc0XHVkNmM0XHVjNWQwIFx1ZDA1MFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWQwNTAgXHVjNWYwXHVjMGIwXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4IHRvIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWM3MDRcdWNlNTg8XC9wPlxyXG5cclxuPHA+XHVjOTg5LCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NDQgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzcwNFx1Y2U1OFx1Yjg1YyBcdWM2MmVcdWFlMzBcdWIyOTQgXHVjNWYwXHVjMGIwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQwNTBcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPkl0ZW0xIEl0ZW0yIEl0ZW0zIEl0ZW00IEl0ZW01PFwvcD5cclxuXHJcbjxwPkl0ZW0xXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCAxXHViYzg4IFx1YzcwNFx1Y2U1OCwgSXRlbTJcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIDJcdWJjODggXHVjNzA0XHVjZTU4IFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+NSB0byAyIFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NWMgXHVkNmM0XHVjNzU4IFx1ZDA1MFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5JdGVtMSBJdGVtNSBJdGVtMiBJdGVtMyBJdGVtNDxcL3A+XHJcblxyXG48cD5cdWQwNTAgXHVjNWYwXHVjMGIwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWI5N2MgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQwNTBcdWM3NTggXHViMGI0XHVjNmE5XHVjNzc0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDQgXHViNTRjPFwvcD5cclxuXHJcbjxwPkl0ZW0xIEl0ZW0yIEl0ZW0zIEl0ZW00IEl0ZW01IEl0ZW02IEl0ZW03IEl0ZW04PFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM1ZjAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YmE3NDxcL3A+XHJcblxyXG48cD4yIHRvIDY7IDYgdG8gMzsgNCB0byA1OyA1IHRvIDI7IDcgdG8gNDsgOCB0byAxPFwvcD5cclxuXHJcbjxwPlx1ZDA1MFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+SXRlbTggSXRlbTUgSXRlbTYgSXRlbTcgSXRlbTQgSXRlbTIgSXRlbTEgSXRlbTM8XC9wPlxyXG5cclxuPHA+XHVkMDUwIFx1YzVmMFx1YzBiMFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc0MCBcdWJhYThcdWI0NTAgXHVjMjFjXHVjMTFjXHViOTdjIFx1YzcyMFx1YzljMFx1ZDU1OFx1YWNlMCwgXHViZTQ4IFx1YzcwNFx1Y2U1OFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM3NzRcdWIzZDkgXHVjNWYwXHVjMGIwXHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNThcdWFjMDAgXHVhYzE2XHVhYzcwXHViMDk4LCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YWMxNlx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc1OCBcdWMyMTggbVx1YWNmYyBcdWQwNTAgXHVjNWYwXHVjMGIwXHVjNzU4IFx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBtLCBuICZsZTsgMjApIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMDUwXHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NTggXHVjNzc0XHViOTg0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViOTg0XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1YWNmYyBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZTM4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCA4XHVjNzc0XHViMmU0LiBcdWI0NTAgXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDA1MCBcdWM1ZjBcdWMwYjBcdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0LCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjMjE4XHVkNTg5XHVkNTVjIFx1YjRhNFx1YzVkMCBcdWQwNTBcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDU0MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlEiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSYjMzk7dmUgZ290IGEgcXVldWUuIEFuZCB5b3UganVzdCBnb3QgdG8gbWVzcyB3aXRoIGl0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHF1ZXVlIG9mIGl0ZW1zIGFuZCBhIHNlcmllcyBvZiBxdWV1ZSBvcGVyYXRpb25zLCByZXR1cm4gdGhlIHJlc3VsdGluZyBxdWV1ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+UXVldWUgb3BlcmF0aW9ucyBhcmUgZGVmaW5lZCBhcyBmb2xsb3dzOiZuYnNwOzxcL3A+XHJcblxyXG48cD5zdGFydGluZy1wb3NpdGlvbiB0byByZXF1ZXN0ZWQtcG9zaXRpb248XC9wPlxyXG5cclxuPHA+bWVhbmluZyBvbmUgd2FudHMgdGhlIGl0ZW0gYXQgdGhlIHN0YXJ0aW5nIHBvc2l0aW9uIHRvIGJlIG1vdmVkIHRvIHRoZSByZXF1ZXN0ZWQgcG9zaXRpb24uIFNvIGlmIHRoZSBxdWV1ZSBvZiBpdGVtcyB3ZXJlOiZuYnNwOzxcL3A+XHJcblxyXG48cD5JdGVtMSBJdGVtMiBJdGVtMyBJdGVtNCBJdGVtNTxcL3A+XHJcblxyXG48cD4oSXRlbTEgYmVpbmcgaW4gcG9zaXRpb24gMSwgSXRlbTIgaW4gcG9zaXRpb24gMiwgZXRjLikmbmJzcDs8XC9wPlxyXG5cclxuPHA+YWZ0ZXIgYXBwbHlpbmcgdGhlIHF1ZXVlIG9wZXJhdGlvbjombmJzcDs8XC9wPlxyXG5cclxuPHA+NSB0byAyJm5ic3A7PFwvcD5cclxuXHJcbjxwPnRoZSByZXN1bHRpbmcgcXVldWUgd291bGQgYmU6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkl0ZW0xIEl0ZW01IEl0ZW0yIEl0ZW0zIEl0ZW00PFwvcD5cclxuXHJcbjxwPmFzIEl0ZW01ICh0aGUgaXRlbSBpbiBwb3NpdGlvbiA1KSB3YXMgbW92ZWQgdG8gcG9zaXRpb24gMi4gTXVsdGlwbGUgcXVldWUgb3BlcmF0aW9ucyBhcmUgYXBwbGllZCBhdCB0aGUgc2FtZSB0aW1lLCBob3dldmVyOyBlLmcuLCBnaXZlbiB0aGUgcXVldWUgb2YgaXRlbXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkl0ZW0xIEl0ZW0yIEl0ZW0zIEl0ZW00IEl0ZW01IEl0ZW02IEl0ZW03IEl0ZW04PFwvcD5cclxuXHJcbjxwPklmIHRoZSBmb2xsb3dpbmcgcXVldWUgb3BlcmF0aW9ucyB3ZXJlIGFwcGxpZWQ6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjIgdG8gNjsgNiB0byAzOyA0IHRvIDU7IDUgdG8gMjsgNyB0byA0OyA4IHRvIDE8XC9wPlxyXG5cclxuPHA+dGhlbiB0aGUgcmVzdWx0aW5nIHF1ZXVlIHdvdWxkIGJlOiZuYnNwOzxcL3A+XHJcblxyXG48cD5JdGVtOCBJdGVtNSBJdGVtNiBJdGVtNyBJdGVtNCBJdGVtMiBJdGVtMSBJdGVtMzxcL3A+XHJcblxyXG48cD5BcyB5b3UgY2FuIHNlZSwgdGhlIHF1ZXVlIG9wZXJhdGlvbnMgYXJlIHN0cmljdGx5IGVuZm9yY2VkLCB3aXRoIG90aGVyIGl0ZW1zIChub3QgaW52b2x2ZWQgaW4gcXVldWUgb3BlcmF0aW9ucykgbWFpbnRhaW5pbmcgdGhlaXIgb3JkZXIgYW5kIG1vdmluZyB0byB2YWNhbnQgcG9zaXRpb25zIGluIHRoZSBxdWV1ZS4gTm90ZSB0aGF0IG5vIHR3byBxdWV1ZSBvcGVyYXRpb25zIHdpbGwgaGF2ZSB0aGUgc2FtZSBzdGFydGluZy1wb3NpdGlvbiBvciBzYW1lIHJlcXVlc3RlZC1wb3NpdGlvbiBkZWZpbmVkLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgdG8gdGhpcyBwcm9ibGVtIHdpbGwgYmVnaW4gd2l0aCBhIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyIHggaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIGRhdGFzZXRzLiBFYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIHRocmVlIGNvbXBvbmVudHM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+U3RhcnQgbGluZSAmbmRhc2g7IEEgc2luZ2xlIGxpbmUsICZxdW90O20gbiZxdW90OyAoMSAmbHQ7PSBtLCBuICZsdDs9IDIwKSB3aGVyZSBtIGluZGljYXRlcyB0aGUgbnVtYmVyIG9mIGl0ZW1zIGluIHRoZSBxdWV1ZSBhbmQgbiBpbmRpY2F0ZXMgdGhlIG51bWJlciBvZiBxdWV1ZSBvcGVyYXRpb25zLjxcL2xpPlxyXG5cdDxsaT5RdWV1ZSBpdGVtcyAmbmRhc2g7IEEgbGluZSBvZiBzaG9ydCAoYmV0d2VlbiAxIGFuZCA4IGNoYXJhY3RlcnMpIGFscGhhbnVtZXJpYyBuYW1lcyBmb3IgdGhlIGl0ZW1zIGluIHRoZSBxdWV1ZS4gTmFtZXMgYXJlIHVuaXF1ZSBmb3IgYSBnaXZlbiBkYXRhIHNldCBhbmQgY29udGFpbiBubyB3aGl0ZXNwYWNlLjxcL2xpPlxyXG5cdDxsaT5RdWV1ZSBvcGVyYXRpb25zICZuZGFzaDsgbiBsaW5lcyBvZiBxdWV1ZSBvcGVyYXRpb25zIGluIHRoZSBmb3JtYXQgJnF1b3Q7c3RhcnRpbmctcG9zaXRpb24gcmVxdWVzdGVkLXBvc2l0aW9uJnF1b3Q7LjxcL2xpPlxyXG48XC9vbD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YXNldCwgb3V0cHV0IHRoZSBxdWV1ZSBhZnRlciB0aGUgcXVldWUgb3BlcmF0aW9ucyBoYXZlIGJlZW4gYXBwbGllZC4gUHJpbnQgdGhlIGVsZW1lbnRzIG9mIHRoZSBxdWV1ZSBvbiBhIHNpbmdsZSBsaW5lLCBzdGFydGluZyBmcm9tIHRoZSBmaXJzdCBhbmQgZW5kaW5nIHdpdGggdGhlIGxhc3QsIHdpdGggYSBzaW5nbGUgc3BhY2Ugc2VwYXJhdGluZyBlYWNoIGl0ZW0uJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d