Vim

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65535/65535 K (Java/Others)

Description

Vim is a text editor which developed from vi. Due to its powerful function in code complete, compile, and error jump, it’s widely used by programmers. The same as Emacs, it’s the most popular text editor among users of UNIX. As such an excellent text editor, Vim has various of orders. Now, we’re asking you to write a program that simulates Vim’s replace order.

The format of Vim’s replace order is ([] means optional, {} means necessary) :

:[range]s/{pattern}/{string}/[flag]

In the order above,

‘:’ means the start of a replace order,

[range] indicates the range of the order, that is, the order works in which lines.

‘s’ is short for substitute.

{pattern} and {string} represent the string to match and replace to, respectively.

‘/’ is used to mark the beginning and ending of {pattern} and {string}.

{flag} is used to open or close some options.

{range} is often two integers separated by a comma, indicating the start line and end line’s line number.

For example, “4,8” means from line 4 to line 8 (including line 4, line 8). Line number starts from 1. You can also use a ‘%’ to represent all lines.

(Additional, Vim provides many more flexible formats. Such as, bypassing a number means the line cursor stays, ‘$’ means the last line of the text. So, “,$” means from the line cursor stays to the last line. )

{pattern} and {string} both support regular expression (if you haven’t ever heard of it, go to Google for help). If {pattern} is empty, the {pattern} of the last replace order will be used.

Obviously, ‘/’ can’t be included in {pattern} and {string}. So, an additional escape character ‘\’ is used. For example, if you want to replace “<br>” to “<br/>”, you cannot write:

:%s/<br>/<br />/g

Instead, you should write:

:%s/<br>/<br \/>/g

If there’re too many ‘/’s in the expression, (for instance, "file:///usr/share/man/man1/vim.1.gz"), it will become troublesome. So, people think of a solution, that is, use another character as the separator (the first character after ‘s’ is always treated as the separator). For example, when using ‘+’ as the separator, the order above can be written this way:

:%s+<br>+<br />+g

There’re many kinds of [flag]. ‘g’ means replace every time it matches. Without a ‘g’, it will only replace the first matching string. For example:

#include <stdio.h>

Execute the order bellow:

:%s/i//g

Result is:

#nclude <stdo.h>

While executing this order bellow:

:%s/i//

Result is:

#nclude <stdio.h>

Other flags including: ‘c’ indicates a confirm is required before every replacement, ‘i’ indicates case insensitive.

Here comes a problem, what if you want to replace “a” to “aa”? Somebody may doubt that it will go to an endless loop, but in fact, it won’t. Because there is a rule that, in a replacement, the replaced characters can’t be replaced again. So, if you want to replace “a” to “aa”, it’s in fact that every successive “a” string is doubled in length.

To simplify the problem, we make some appointments:

1. [range] must appear, in the form of “%” or “a,b” (a, b are both integers, and a<=b)

2. {pattern} and {string} are both consist of characters, numbers, spaces and “_” (not including any separator below, so an escape character is not needed)

3. You can choose one of these characters as the separator: /~!@#$%^&*()-+=

4. [flag] is always a “g”

A big example:

Original text:

If the Tao is greet, then the operating system is greet.

If the operating system is greeter, then the compiler is greet.

If the compiler is greeter, then the applications is greet.

The user is pleased and there is harmony in the world.

Replace order:

:[1,4]s/greet/great/g

Or:

:%s+greet+great+g

Either will replace the original text to:

If the Tao is great, then the operating system is great.

If the operating system is greater, then the compiler is great.

If the compiler is greater, then the applications is great.

The user is pleased and there is harmony in the world.

Please write a program to simulate this simplified vim replace order.

Input

The input will consist of one case.

The first line will be a positive integer L (L <= 100), specifying the number of lines to be processed. Then L lines of text are given. Each line has no more than 100 characters.

After that, several pieces (<= 50) of replace orders are given (one per line). It is ensured that any line of text will never have more than 100 characters during the replacement.

Output

After the execution of every replace order, output the line number and content of the lines that have been replaced, order by line number from small to big. In each line, first output the line number, which has a width of 4 characters, right-aligned, then 2 spaces, then the text after replacement.

If any order replaced nothing, output "Pattern not found".

Output a blank line between any two replace order’s result.

Sample Input

4 If the Tao is greet, then the operating system is greet. If the operating system is greeter, then the compiler is greet. If the compiler is greeter, then the applications is greet. The user is pleased and there is harmony in the world. :1,3s/greet/great/g :%s//great/g

Sample Output

1 If the Tao is great, then the operating system is great. 2 If the operating system is greater, then the compiler is great. 3 If the compiler is greater, then the applications is great. Pattern not found

Hint

gaojie

Source

2009 Multi-University Training Contest 15 -

提交代码