Module: Prefix function, Z function


Problem

10 /10


Cipher

Theory Click to read/hide

 
Both Z and the function prefix can be used to implement the KMP(Knuth-Morris-Pratt) algorithm for finding a substring in a string in O(|S|). The essence of this algorithm is as follows: we attribute to the string we want to find the string in which we are searching. It is highly desirable to put a separator character between these lines, i.e. a character that does not occur in any line (usually #).

Problem

Corwin was able to intercept n messages about Eric's troop movements. True, they turned out to be encrypted, but it does not matter! Will you help him decipher these messages? This shouldn't be difficult, as Corwin knows at least one substring in every original message.

For encryption, Eric is known to use a Caesar cipher, that is, a cipher in which the letter with the number i is replaced by the letter with the number i + k , where k is some number.

Since modern compilers do not support the Amber alphabet, we will replace characters with their serial number - a number from 1 to q, where q - the number of characters in the alphabet.

Each message is x long, and each known substring of its decryption is y.

Your goal is to restore all original messages.

THE SUPPLIER WITH STD::STRING WILL GO TO THE YARDS OF CHAOS!!!
 
Input
First line reads numbers n (\(1 <= n <= 100\)) and q (\(1 <= k <= 100\))
The following 3 * n lines contain numbers xi, yi (\(1 <= b_i <= a_i <= 100\)) and 2 arrays of numbers representing the message and its decryption substring.

Imprint
In the line number i print the decoded version of the message with the number i.
There must be MUST NOT at the end of this line


Examples
# Input Output
1 1 11
10 4
11 7 1 1 2 6 7 1 1 8
2 7 7 8 		6 2 7 7 8 1 2 7 7 3

time 250 ms
memory 16 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!