ACPC11A - Arabic and English

Some computer programs have problems in displaying Arabic text, especially when mixed with English words in the same line, because Arabic is written from right to left and English is written from left to right. In this problem we will try to fix a text with some corrupted lines which consist of a mixture of Arabic and English words. For simplicity, all Arabic letters will be replaced with the symbol '#'.

Each line will contain at most one English word. For a line containing an English word, the program that will fix the text will swap the words before the English word with the words after the English word. The words before the English word will remain in the same order. The words after the English word will also remain in the same order. For example, if the line is "# #### ### abc ##", it will be fixed to become "## abc # #### ###".

Please note that a line that contains words only of the same language is not corrupt.

Input

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). Next 2T lines contain the test cases, each on a pair of lines. The first line of each case contains a single integer N, the number of words in the line to fix (1 ≤ N ≤ 100). The second line contains N words, separated by single spaces, with no leading or trailing spaces, and each word will be at least 1 character and at most 10 characters long.

Each word will be either Arabic or English. Arabic words will consist of one to ten '#' letters, and English words will consist of one to ten English lower case letters.

Each line contains at most one English word.

Output

For each test case, output, on a single line, the fixed line of input text.

Example

Input:
3
5
# #### ### abc ##
4
## ### ## #####
4
## ##### # xyz

Output:
## abc # #### ###
## ### ## #####
xyz ## ##### #

Added by:mohamedwahba
Date:2011-12-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Arab Collegiate Programming Contest

hide comments
2012-01-09 12:54:02 himanshu jain
WAhBA please verify that wt is the ans for:-
# ab ## cd ####
ans:
## ab #### cd #

Last edit: 2012-01-10 11:12:36
2011-12-31 09:43:34 Vikram Kamath
Note: Read the problem thoroughly, the test cases are slightly deceptive.
2011-12-24 19:33:08 Aditya Muttur
EASY!!!

Last edit: 2011-12-18 16:03:51
2011-12-24 19:33:08 BOND
@summa if str is character array then you must know last position stores '/0'
@gary its # ## ### abc
2011-12-24 19:33:08 Gary Thompson
what is output for
abc # ## ###
2011-12-24 19:33:08 Summa
I dont understand this. . The max num of letters in a word is 10. So if i give str[10] it gives WA but it works with str[11]. . How ??
2011-12-24 19:33:08 .:abacus:.
imp: no space at end of output line
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.