Q

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

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

• 시작 위치 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개 줄에는 큐 연산이 한 줄에 하나씩 주어진다.

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