Description

3/31 Update: Add additional comments in partial judge code and partial judge header. No rejudge.

4/4 Update: Modify sample input and output to sync with the demo animation. Test case#1 is changed accordingly. Because test case#1 is simple, no rejudge will be performed.

4/6 Update: Add additional description in QUERY card for clarification. No rejudge will be performed.

4/8 Update: Add additional comments about the "first_row()" function in partial judge header and code. The original function name is misleading. Actually, you need to implement the card type of BOTTOM_ROW in this function. No rejudge will be performed because  rejudge all submissions does more harm than good.

This is a partial judge problem.

Hanako Honda (本田華子), Olivia (オリヴィア), and Kasumi Nomura (野村香純) are three cute junior high school students, a.k.a. JC. They are also the members of the Pastimers Club (遊び人研究会). One day during the club activity time, Hanako brought a board game she invented(i) to play with Kasumi and Olivia.

(Starting from left to right is Kasumi, Hanako, and Olivia)

 

This game is inspired by Tetris, although the rule and the goal are totally different. The rule of the game is described as follows. There are three important components in this game, the board B, the matching stack M, and a stack of drawing cards. At the beginning, there are totally L empty vertical slots on the board numbered from 0 to L-1(ii), denoted by l₀, l₁, ..., l_n-1. Also, the matching stack M will be empty. In each round of the game, the player needs to draw a card from the card deck and perform corresponding actions. Initially, the card deck contains a stack of D cards, denoted by c₁, c₂, ..., c_D, each containing a single action. There are five types of cards (actions) in total, described as follows.

 

INSERT: If you draw this card, you can insert an arbitrary string onto the board! Formally, you can insert a string s_i onto the board starting from slot l_p consisting of only lowercase characters. The j-th character of s_i will be inserted into slot l_p+j-1.
The insertion rule is similar to Tetris. You need to insert the s_i to the bottom of the board unless it meets the "obstacles" formed by the previous inserted block. After you insert s_i onto the board, the board will change in the following way. All empty spaces in each slot will be replaced by "at symbol"(@) if there is at least one lowercase character above it within the same slot. The "at symbol" means an empty obstacle.

BOTTOM_ROW: If you draw this card, you need to speak out the bottom row of the obstacle on the board. If the vertical slot contains no obstacle, you need to read out the tilde symbol (~).

QUERY: If you draw this card, you can query a single string s_q consisting of only lowercase characters, or at symbol, to see if s_q is a substring of s_b, where s_b is the string formed by the bottom row of the obstacle. If s_q is a substring of s_b, you can remove the corresponding obstacles from the bottom row of the board. After removal, all the obstacles within the same slots above would be moved one row down(iii). Also, you need to copy s_q onto a piece of empty card, and put it on top of the matching stack M. If there are multiple occurrence of s_q in s_b, you only need to remove the first occurence of it.
If the query string s_q is not a substring of s_b, you do not need to do anything.

FLUSH: If you draw this card, you need to clear out the matching stack M and speak out all the strings written on the card! Formally, assume there are |M| cards in the matching stack. You need to repeat the following process until there is no remaining card in M. For each time, you pick the card on top of the stack and speak out the string written on it. The card will then be discarded and the number of cards remaining in M will reduce by 1.

RESET: If you draw this card, all the obstacles on the board will be removed. Moreover, all the cards in the matching stack M will be discarded. You do not need to speak out the content on the board or the matching stack.

 

The players can draw an arbitrary number of cards in arbitrary order. If multiple cards are drawn, you need to perform them one by one. You can not sneak into other cards you draw when you are performing one of them.
The whole game will end after all C cards are drawn and performed.

 

To make the game more exciting, they decided to add an additional rule. If the BOTTOM_ROW or the FLUSH card is drawn, but the person drawing it can not speak out the content of the obstacle or the string, then she needs to smell Olivia's armpit for ten second(iv). Unfortunately, the game has been modified so that Olivia and Kasumi can only draw BOTTOM_ROW or FLUSH, whereas Hanako can only draw INSERT, QUERY, or FLUSH. Hanako cheats for the game so that she can insert blocks consisting of english characters and tease Olivia and Kasumi(v)!

 

Actually, Maeda, the butler in Hanako's family, has already told Olivia and Kasumi about Hanako's plot. They decide to pretend they know nothing and play the game with Hanako. However, they still need someone's help to pronounce the characters correctly. Can you write a program to help the two cute junior high school students?

 

Here is the demo animation of the sample input.

 

Notes:

(i) Actually, the game is invented by Maeda (前多), the butler in Hanako's family. But that is another long story.

(ii) You can think of Tetris as a board with 10 slots. However, in this game, the capacity constraint of each slot is much more bigger.

(iii) The removal process is similar to the "clear line" process in Tetris. One difference is that some vertical slots may remain the same after removal. Also, in each query string, at most one row of obstacles can be removed.

(iv) Olivia has strong body odor.

(v) Olivia and Kasumi are very bad at English.

Input

The first line contains an integer L, representing the number of vertical slots on the board.

The second line contains an integer C, representing the number of cards to be drawn.

The following C lines represent the order of the card deck and Hanako’s actions. Each line starts with a string c_i, representing the type of card. c_i will only be one of the following strings: INSERT, BOTTOM_ROW, QUERY, FLUSH, or RESET.

If c_i is INSERT, c_i is followed by an integer l_p and a string s_i, representing the starting slot and the string Hanako inserted onto the board.

If c_i is QUERY, c_i is followed by a string s_q, representing the query string Hanako asked for.

If c_i is BOTTOME_ROW, FLUSH, or RESET, there will be no more following input in the same line.

 

It is guaranteed that:

Test case #1: Sample Input

Test case #2 ~ #7: L ≤ 10, max_size(l_i) ≤ 10, D ≤ 10², len(s_q) ≤ 10, |M| ≤ 10

Test case #8 ~ #9: L ≤ 10, max_size(l_i) ≤ 10³, D ≤ 10⁵, len(s_q) ≤ 10, |M| ≤ 10³

Test case #10: L ≤ 10², max_size(l_i) ≤ 10⁶, Σ(size(l_i)) ≤ 10⁶, D ≤ 10⁶, len(s_q) ≤ 10², |M| ≤ 10⁴

• len(s_i) represents the length of the insert string; len(s_q) represents the length of the query string.
• max_size(l_i) represents the maximum capacity of a single slot; Σ(size(l_i)) represents the total number of characters (obstacles) existing on the board.
• l_p + len(s_i) < L for each test case.

Output

For each drawing card, you need to output the answer with the following format.

If the card is INSERT, QUERY, or RESET, you do not need to output anything.

If the card is BOTTOM_ROW, you need to print the string "BOTTOM_ROW" following a new line symbol.
In the next line, you need to print s_b, the string formed by the bottom row of the obstacle, followed by a new line symbol.

If the card is FLUSH, you need to print the string "FLUSH" following a new line symbol.
In the next |M| lines, you need to print a string in a line, representing the order of the string you need to speak out.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13144.cpp

Partial Judge Header

13144.h

Tags

Discuss