Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

Once upon a time in the magical land of Whitechapel which is located in Great Britain, there lived a curious character named Mr. Heart. Mr. Heart had a special talent—he could manipulate strings in the most fascinating ways. One day, he decided to challenge the inhabitants of Whitechapel with a problem that would test their string manipulation skills.

Mr. Heart gathered the best coders from around the land and presented them with a challenge. He gave them a special string, S, which had to undergo a series of transformations based on his instructions. Along with the string are two types of Q queries.

• 1 - You have to reverse the String: Mr. Heart might ask you to flip the string backward, turning it into its mirror image. For example, if the string is "abc," it would become "cba."
• 2 D C - You have to append the character value C in the String S: if D = 1 then append to the beginning or if D = 2 then append to the ending.

Mr. Heart would then ask the coders to process each of the Q queries in sequence. After completing all query, the coders were required to show him the final state of the string. Only those who could keep up with Mr. Heart’s whims and correctly manipulate the string each time would pass the challenge.

The coders knew that they had to be vigilant. A simple mistake, like appending a character in the wrong position or forgetting to reverse the string, could mean failing Mr. Heart's challenge.

You have the opportunity to participate in this challenge as well. Would you want to do?

Input

First Line T (1 ≤ T ≤ 5), the number of test cases.
Second Line contains a String value S (1 ≤ S ≤ \(10^5\)), which contains small english letter.
Third line Q (1 ≤ Q ≤ \(2 * 10^5\)), the number of query.
Each query takes two types of input in the following format

• 1
• 2 D C

D(1 ≤ D ≤ 2), an integers value and C, a lowercase english letter.

sum of Q over all testcase will not exceed \(2 * 10^5\)

Output

Print the final string S after each query processing.

Sample

1
abc
3
2 1 d
1
2 2 e

cbade