Рабочее место участника

Advanced Caption Machines (ACM) produces electronic captions that are used as labels, signs, and tags in various brick-and-mortar stores. They range from small tags that are used on the shelves of the stores to the large signs for the rows. Electronic captions use flip disks, electronic ink and other similar technologies to display one line of text so that this text can be electronically changed as needed. The common to all these display technologies that are used by ACM is that they represent a text with `m\ times\ n` grid of pixels that can be individually electronically turned on or off and indefinitely retain their state. For example, if turned off pixels are represented with '.' and turned on pixels are represented with '*', then one of the ways to display the text "ACM ICPC" on a `5\ times\ 53` grid of pixels is:

.....*....****.*...*.........*....****.****...****...
....*.*..*.....**.**.........*...*.....*...*.*.......
...*...*.*.....*.*.*.........*...*.....****..*.......
...*****.*.....*...*.........*...*.....*.....*.......
...*...*..****.*...*.........*....****.*......****...

The advantage of an electronic caption is that energy is consumed only to flip the state of individual pixels. The total energy required to change displayed text to some other text is proportional to the number of pixels flipped.

ACM is mindful about nature conservation. The whole concept and marketing model of ACM's business is built around preservation of natural resources. Without ACM's captions stores had to print out new labels, signs, and tags whenever they had to change the layout of goods in the store, thus throwing old labels, signs, and tags away. ACM had decided to go even further and had figured out that each change of text on their electronic captions requires some electrical energy which should be conserved, too, because electrical energy is still mostly produced from non-renewable fossil fuels with their harmful emissions.

Fortunately, when one text is changed to the other text on an electronic caption, there is always a leeway in how the text can be laid out on `m\ times\ n` grid of pixels. The text is always written in a fixed-width font where each letter is represented by a `m\ times\ k` grid of pixels. However, the spacing between the letters in a caption can vary from `s_{min}` pixels to `s_{max}` pixels. The left-right position of the text in a caption can also vary. Together, that gives enough freedom to optimize the text update procedure, so that the number of pixels that need to change is minimized, thus minimizing the energy expenditure.

For example, the optimal way to change the text on the caption above to "NEERC" while maintaining spacing between the letters from 1 to 2 pixels is shown below. Only 61 pixels will have to be flipped (34 pixels will be turned off and 27 pixels will be turned on).

...................*...*..*****..*****.****...****...
...................**..*..*......*.....*...*.*.......
...................*.*.*..***....***...****..*.......
...................*..**..*......*.....*.*...*.......
...................*...*..*****..*****.*..*...****...

Your team is assigned with a task to write a procedure that finds the optimal caption layout for the new caption text given the text that it currently contains, so that the number of pixels to update is minimized.

The first line of the input file contains 5 integer numbers `m`, `n`, `k`, `s_{min}`, and `s_{max}`, where `m` (`5\ ≤\ m\ ≤\ 30`) is the number of rows on the caption, `n` (`5\ ≤\ n\ ≤\ 2000`) is the number of columns on the caption, `k` (`5\ ≤\ k\ ≤\ 30`) is the width of each letter in the font, `s_{min}` and `s_{max}` (`0\ ≤\ s_{min}\ ≤\ s_{max}\ ≤\ 30`) are the minimal and the maximal allowed spacing between letters in pixels correspondingly.

The following `m` lines of the input file contain description of the font. Each line of the font description contains `t(k+3)\ -\ 1` characters, where `t` (`1\ ≤\ t\ ≤\ 26`) is the number of Latin letters that are defined in this font. The grid with `m` rows and `t(k+3)\ -\ 1` columns on those `m` lines is composed of `m\ times\ k` grids of characters '.' and '*' defining the font for uppercase Latin letters from A to Z. The letters that are defined appear on the first line before the corresponding grids. Everything is arranged in the same way as in the sample input below. The first of those `m` lines uses a total of `2t\ -\ 1` spaces as delimiters, subsequent lines use `3t\ -\ 1` spaces each. Letters do not necessary appear in alphabetic order, but each letter is defined at most once.

The space character is assumed to be implicitly defined in any font as `m\ times\ k` grid of '.'. The spacing between spaces and other letters is bound by the same `s_{min}` and `s_{max}` constraints, the space is treated just as a letter.

The next line contains the text that is currently displayed on the electronic caption. This string has `c_{"cur"}` characters (`1\ ≤\ c_{"cur"}\ ≤\ 30`) –- uppercase Latin letters from A to Z and spaces. There are no leading or trailing spaces.

The line after that contains `c_{"cur"}` non-negative integer numbers. Each number defines the spacing (in pixels) before the corresponding letter or space of the currently displayed string. The first number is the spacing from the left side of the caption to the first letter, the second number is the spacing from the first letter to the second letter or space, etc. The whole string fits on the caption. The spacing for the currently displayed string does not have to obey `s_{min}` and `s_{max}` limits.

The next line contains the new text that should be displayed on the electronic caption. This string has `c_{"new"}` characters (`1\ ≤\ c_{"new"}\ ≤\ 30`) –- uppercase Latin letters from A to Z and spaces. There are no leading or trailing spaces.

All Latin letters that are used for the current and the new text are defined in the font description.

Write to the output file a single line with `c_{"new"}` integer numbers, denoting the optimal spacing for the new text. The first number is the spacing from the left side of the caption to the first letter and should be non-negative, the second number is the spacing from the first letter to the second letter or space, etc. The spacing between the letters and space characters should be between `s_{min}` and `s_{max}` pixels inclusive. The text shall fit on the electronic caption. There is always at least one way to fit the text on the electronic caption satisfying the above constraints. If there are multiple optimal answers, write any of them.

5 53 5 1 2
A ..*.. C .**** E ***** I ..*.. M *...* N *...* P ****. R ****.
  .*.*.   *....   *....   ..*..   **.**   **..*   *...*   *...*
  *...*   *....   ***..   ..*..   *.*.*   *.*.*   ****.   ****.
  *****   *....   *....   ..*..   *...*   *..**   *....   *.*..
  *...*   .****   *****   ..*..   *...*   *...*   *....   *..*.
ACM ICPC
3 1 1 1 1 1 1 1
NEERC

19 2 2 1 1