Problem B. Blanks

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Young programmer Vasya works for a local government.

His first job is to automate filling of paper forms. A form is represented by a single string consisting of Latin letters, spaces and underscores ('_', ASCII 95). Substrings of underscores (known as fields) represent blank spaces left for an applicant to fill. Under each field the paper form has a small caption explaining to the applicant what data he should put over those underscores. For example:

My name is ________
             name
In computerized form, captions are represented by a single string of spaces and Latin letters. Every caption is a single word. Number of captions is guaranteed to be equal to the number of fields. However, number of spaces between captions may be arbitrary, so captions are not necessarily located directly under corresponding fields.

You program must, given the representation of a form and a value for each field caption, put corresponding value into every form field.

When filling a field with a value, additional rules must be observed:

  1. First and last character of the field must remain underscores.
  2. Total field length must not change. If a value is longer than a field, it must be truncated on the right. If a value is shorter than a field, it must be aligned to the left.

Input file format

First line of input file contains a string representing the form. Second line contains field captions. Third line contains an integer N — number of different captions. Following 2 × N lines contain N pairs of captions and corresponding values. Captions consist of Latin letters only. Values consist of Latin letters and spaces. All captions are different. Note that several fields may have the same caption.

Output file format

Output file must contain a single line — a form with all fields filled in. It is guaranteed that values for all captions are present in the input. Note that spaces in the form are significant and must be preserved.

Constraints

All strings have length from 1 to 1000 characters. All fields consist of at least 3 underscores. 0 ≤ N ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
Hello _________ welcome to our ___
         name               location
2
name
Vasya
location
Eastowner city
Hello _Vasya___ welcome to our _E_
2
___  ____
a a
1
a
bb
_b_  _bb_

0.112s 0.017s 13