SHMOOGLE - Shmoogle Wave

no tags 

Shmoogle company developed new protocol <<Wave>> for the multi-user online editing of the text data. Using it, any client can send commands to the server for editing the text and the server would broadcast it to all other connected clients. Each command consists of a sequence of operations of the following type:

OperationDescription
R kMoves the cursor k positions right. The cursor is positioned at before the first character of the text at the start of performing the command.
C k sInserts the string s of length k at the cursor position. After this operation the cursor is positioned to the right of the inserted string.
D kDeletes k characters right of the cursor.

When the new client connects the server needs to send it all the command this client missed. In order to save traffic the server merges all the commands in one equivalent command. Help Shmoogle company implement merging of commands effectively.

The resulting command should consist of the least possible number of operations. The delete operations should precede the insert operations if possible.

Input

The first line contains T (1 <= T <= 10) — the number of test cases. The description of T tests follow. The first line of each test case contains the amount of commands n (1 <= n <= 10000). The description of each command follows. The first line of each command contains the amount of operations m (1 <= m <= 10). The next m lines contain the description of each operation in the format given above. 1 <= k <= 100000 for R and D operations, and 1 <= k <= 10 for C operations. The strings in C operations consist of latin letters and digits only.

Output

For each test case your program should print the result of merging the commands. The format of the command should be the same as in the input file, except for the limitations on m and k. The result should consist of the least possible number of operations. The delete operations should precede the insert operations if possible. If the result of merging consist of no operations print 0.

Example

Input:
1
2
4
R 4
C 3 abc
R 2
C 3 xyz
3
R 7
C 3 def
D 3

Output:
3
R 4
D 2
C 8 abcdefyz


hide comments
[Rampage] Blue.Mary: 2011-08-23 13:08:43

Mmm... A tough problem. I used some data structures to avoid TLE. (Even though the program without data structures is somewhat difficult and tricky.)

:D: 2011-08-23 13:08:43

SPOJ doesn't have such strict rules. There are no time limits on solving the problem and you can use internet and other media. You don't have to be an author to get a solution from some source. IMO author should be allowed to post it's own solution and it's not cheating, unless he uses some information on data that's not specified in the description. Other than that, he knows the solution to the problem and wrote the program on his own, so why not?

Last edit: 2011-03-21 23:24:04
Seshadri R: 2011-08-23 13:08:43

Alexey Shchepin is the author of this problem. He is also one of the three successful submitters. Is that OK? Under normal circumstances, a contest is open for only those who are not connected with contest formulator(s)


Added by:Spooky
Date:2010-03-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6
Resource:Advancement Spring 2010, http://sevolymp.uuuq.com/, author: Alexey Shchepin