시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 37 22 21 61.765%

문제

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

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

  • 시작 위치 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+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNTggdG8gXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzcwNFx1Y2U1ODxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzk4OSwgXHVjMmRjXHVjNzkxIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzQ0IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWM3MDRcdWNlNThcdWI4NWMgXHVjNjJlXHVhZTMwXHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVkMDUwXHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5JdGVtMSBJdGVtMiBJdGVtMyBJdGVtNCBJdGVtNTxcL3A+XHJcblxyXG48cD5JdGVtMVx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgMVx1YmM4OCBcdWM3MDRcdWNlNTgsIEl0ZW0yXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCAyXHViYzg4IFx1YzcwNFx1Y2U1OCBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjUgdG8gMiBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTVjIFx1ZDZjNFx1Yzc1OCBcdWQwNTBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+SXRlbTEgSXRlbTUgSXRlbTIgSXRlbTMgSXRlbTQ8XC9wPlxyXG5cclxuPHA+XHVkMDUwIFx1YzVmMFx1YzBiMCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHViOTdjIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVkMDUwXHVjNzU4IFx1YjBiNFx1YzZhOVx1Yzc3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQ0IFx1YjU0YzxcL3A+XHJcblxyXG48cD5JdGVtMSBJdGVtMiBJdGVtMyBJdGVtNCBJdGVtNSBJdGVtNiBJdGVtNyBJdGVtODxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNWYwIFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NThcdWJhNzQ8XC9wPlxyXG5cclxuPHA+MiB0byA2OyA2IHRvIDM7IDQgdG8gNTsgNSB0byAyOyA3IHRvIDQ7IDggdG8gMTxcL3A+XHJcblxyXG48cD5cdWQwNTBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkl0ZW04IEl0ZW01IEl0ZW02IEl0ZW03IEl0ZW00IEl0ZW0yIEl0ZW0xIEl0ZW0zPFwvcD5cclxuXHJcbjxwPlx1ZDA1MCBcdWM1ZjBcdWMwYjBcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NDAgXHViYWE4XHViNDUwIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWM3MjBcdWM5YzBcdWQ1NThcdWFjZTAsIFx1YmU0OCBcdWM3MDRcdWNlNThcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1ZDA1MCBcdWM1ZjBcdWMwYjBcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNThcdWFjMDAgXHVhYzE5XHVhYzcwXHViMDk4LCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzU4IFx1YzIxOCBtXHVhY2ZjIFx1ZDA1MCBcdWM1ZjBcdWMwYjBcdWM3NTggXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG0sIG4gJmxlOyAyMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQwNTBcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI5ODRcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzXHVhY2ZjIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIDhcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NTggXHVjNzc0XHViOTg0XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMDUwIFx1YzVmMFx1YzBiMFx1Yzc3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWMyMThcdWQ1ODlcdWQ1NWMgXHViNGE0XHVjNWQwIFx1ZDA1MFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjNmQwXHVjMThjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0NTQwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUSIsImRlc2NyaXB0aW9uIjoiPHA+WW91JiMzOTt2ZSBnb3QgYSBxdWV1ZS4gQW5kIHlvdSBqdXN0IGdvdCB0byBtZXNzIHdpdGggaXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgcXVldWUgb2YgaXRlbXMgYW5kIGEgc2VyaWVzIG9mIHF1ZXVlIG9wZXJhdGlvbnMsIHJldHVybiB0aGUgcmVzdWx0aW5nIHF1ZXVlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5RdWV1ZSBvcGVyYXRpb25zIGFyZSBkZWZpbmVkIGFzIGZvbGxvd3M6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPnN0YXJ0aW5nLXBvc2l0aW9uIHRvIHJlcXVlc3RlZC1wb3NpdGlvbjxcL3A+XHJcblxyXG48cD5tZWFuaW5nIG9uZSB3YW50cyB0aGUgaXRlbSBhdCB0aGUgc3RhcnRpbmcgcG9zaXRpb24gdG8gYmUgbW92ZWQgdG8gdGhlIHJlcXVlc3RlZCBwb3NpdGlvbi4gU28gaWYgdGhlIHF1ZXVlIG9mIGl0ZW1zIHdlcmU6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkl0ZW0xIEl0ZW0yIEl0ZW0zIEl0ZW00IEl0ZW01PFwvcD5cclxuXHJcbjxwPihJdGVtMSBiZWluZyBpbiBwb3NpdGlvbiAxLCBJdGVtMiBpbiBwb3NpdGlvbiAyLCBldGMuKSZuYnNwOzxcL3A+XHJcblxyXG48cD5hZnRlciBhcHBseWluZyB0aGUgcXVldWUgb3BlcmF0aW9uOiZuYnNwOzxcL3A+XHJcblxyXG48cD41IHRvIDImbmJzcDs8XC9wPlxyXG5cclxuPHA+dGhlIHJlc3VsdGluZyBxdWV1ZSB3b3VsZCBiZTombmJzcDs8XC9wPlxyXG5cclxuPHA+SXRlbTEgSXRlbTUgSXRlbTIgSXRlbTMgSXRlbTQ8XC9wPlxyXG5cclxuPHA+YXMgSXRlbTUgKHRoZSBpdGVtIGluIHBvc2l0aW9uIDUpIHdhcyBtb3ZlZCB0byBwb3NpdGlvbiAyLiBNdWx0aXBsZSBxdWV1ZSBvcGVyYXRpb25zIGFyZSBhcHBsaWVkIGF0IHRoZSBzYW1lIHRpbWUsIGhvd2V2ZXI7IGUuZy4sIGdpdmVuIHRoZSBxdWV1ZSBvZiBpdGVtczombmJzcDs8XC9wPlxyXG5cclxuPHA+SXRlbTEgSXRlbTIgSXRlbTMgSXRlbTQgSXRlbTUgSXRlbTYgSXRlbTcgSXRlbTg8XC9wPlxyXG5cclxuPHA+SWYgdGhlIGZvbGxvd2luZyBxdWV1ZSBvcGVyYXRpb25zIHdlcmUgYXBwbGllZDombmJzcDs8XC9wPlxyXG5cclxuPHA+MiB0byA2OyA2IHRvIDM7IDQgdG8gNTsgNSB0byAyOyA3IHRvIDQ7IDggdG8gMTxcL3A+XHJcblxyXG48cD50aGVuIHRoZSByZXN1bHRpbmcgcXVldWUgd291bGQgYmU6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkl0ZW04IEl0ZW01IEl0ZW02IEl0ZW03IEl0ZW00IEl0ZW0yIEl0ZW0xIEl0ZW0zPFwvcD5cclxuXHJcbjxwPkFzIHlvdSBjYW4gc2VlLCB0aGUgcXVldWUgb3BlcmF0aW9ucyBhcmUgc3RyaWN0bHkgZW5mb3JjZWQsIHdpdGggb3RoZXIgaXRlbXMgKG5vdCBpbnZvbHZlZCBpbiBxdWV1ZSBvcGVyYXRpb25zKSBtYWludGFpbmluZyB0aGVpciBvcmRlciBhbmQgbW92aW5nIHRvIHZhY2FudCBwb3NpdGlvbnMgaW4gdGhlIHF1ZXVlLiBOb3RlIHRoYXQgbm8gdHdvIHF1ZXVlIG9wZXJhdGlvbnMgd2lsbCBoYXZlIHRoZSBzYW1lIHN0YXJ0aW5nLXBvc2l0aW9uIG9yIHNhbWUgcmVxdWVzdGVkLXBvc2l0aW9uIGRlZmluZWQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB0byB0aGlzIHByb2JsZW0gd2lsbCBiZWdpbiB3aXRoIGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgeCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgZGF0YXNldHMuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgdGhyZWUgY29tcG9uZW50czo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5TdGFydCBsaW5lICZuZGFzaDsgQSBzaW5nbGUgbGluZSwgJnF1b3Q7bSBuJnF1b3Q7ICgxICZsdDs9IG0sIG4gJmx0Oz0gMjApIHdoZXJlIG0gaW5kaWNhdGVzIHRoZSBudW1iZXIgb2YgaXRlbXMgaW4gdGhlIHF1ZXVlIGFuZCBuIGluZGljYXRlcyB0aGUgbnVtYmVyIG9mIHF1ZXVlIG9wZXJhdGlvbnMuPFwvbGk+XHJcblx0PGxpPlF1ZXVlIGl0ZW1zICZuZGFzaDsgQSBsaW5lIG9mIHNob3J0IChiZXR3ZWVuIDEgYW5kIDggY2hhcmFjdGVycykgYWxwaGFudW1lcmljIG5hbWVzIGZvciB0aGUgaXRlbXMgaW4gdGhlIHF1ZXVlLiBOYW1lcyBhcmUgdW5pcXVlIGZvciBhIGdpdmVuIGRhdGEgc2V0IGFuZCBjb250YWluIG5vIHdoaXRlc3BhY2UuPFwvbGk+XHJcblx0PGxpPlF1ZXVlIG9wZXJhdGlvbnMgJm5kYXNoOyBuIGxpbmVzIG9mIHF1ZXVlIG9wZXJhdGlvbnMgaW4gdGhlIGZvcm1hdCAmcXVvdDtzdGFydGluZy1wb3NpdGlvbiByZXF1ZXN0ZWQtcG9zaXRpb24mcXVvdDsuPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCBvdXRwdXQgdGhlIHF1ZXVlIGFmdGVyIHRoZSBxdWV1ZSBvcGVyYXRpb25zIGhhdmUgYmVlbiBhcHBsaWVkLiBQcmludCB0aGUgZWxlbWVudHMgb2YgdGhlIHF1ZXVlIG9uIGEgc2luZ2xlIGxpbmUsIHN0YXJ0aW5nIGZyb20gdGhlIGZpcnN0IGFuZCBlbmRpbmcgd2l0aCB0aGUgbGFzdCwgd2l0aCBhIHNpbmdsZSBzcGFjZSBzZXBhcmF0aW5nIGVhY2ggaXRlbS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=