Indian National Olympiad in Informatics

Online Programming Contest, 4-5 December 2004

IARCS home > OLYMPIAD

Basic Division

Problem 1: The Faulty Transmitter, (K Narayan Kumar, CMI)

The Siruseri Intelligence Agency (SIA) uses a rather simple scheme to send instructions (like StealMap, RunForCover, return and so on) to its agents. To send an instruction, the agency transmits a long message with the instruction appearing as a subword. For example the instruction StealMap could be sent as XbedkStealMapdKLmN. On getting a message, the agent determines whether any instruction appears in the message (he/she has a book of all instructions). At most one instruction is issued in each message. However, it is possible that there is no instruction encoded in a message. This is done to confuse the enemy.

Unfortunately the transmitter used to send these messages has developed a problem. Instead of transmitting a given character once it transmits once, twice or thrice. So the above message could end up being sent as: XXbeeeddkSSteeeaalMMaaappdKLLmmN. That makes the task of finding the instruction a little harder for the agents. Thankfully, none of the instructions have the same letter occuring at adjacent positions (so, for instance, Attack is not a instruction) and that makes it a little easier.

Your task is the following: given two instructions and a message determine which of these instructions, if any, is encoded in the given message.

Input format

The input contains four lines. The first line of the input consists of three integers M1, M2 and N. M1 and M2 are the number of characters in the two instructions and N is the number of characters in the message. The second line contains the first instruction, the third line contains the second instruction and finally the fourth line contains the message.

You may assume that all characters that appear in the message and the instruction are taken from the set {a,b,c,...,z,A,B,C,...,Z,0,1,...,9}. Further, in each instruction, every pair of adjacent characers is different.

Output format

Two lines. The first line should say YES if the the first instruction is coded in the message and it should say NO otherwise. The second line should say YES if the second instruction is coded in the message and so NO otherwise.

Test data

You may assume that 3 ≤ N ≤ 5000 and 2 ≤ M1, M2 ≤ 50.

Example

We now illustrate the input and output formats using the example described above.

Sample input 1:

8 11 31
StealMap
RunForCover
XXbeeeddkSSteeeaalMMaaappdKLLmm

Sample output 1:

YES
NO

Sample input 2:

8 11 13
StealMap
RunForCover
Stkkkllmmddpq

Sample output 2:

NO
NO



Copyright (c) IARCS 2003-2024;   Last Updated: 27 Dec 2004