Martian DNA

Russia is known for its success in the field of space exploration. Recently Russian scientists analysed the samples of Martian soil, and found some strange molecule, which they believe can be some kind of DNA. This molecule has only two base elements instead of the four bases in the normal DNA. So the whole molecule can be described as string of zeroes and ones.

The scientists computed the length of the molecule, it is n base elements. Now they want to determine its structure, i.e. find the string of ones and zeroes S, that encodes the elements of the DNA molecule. In order to do it, they can make tests in a special DNA analyser. In each test they set a sequence of elements, encoded by string P, and the analyser checks if this sequence appears in the molecule, i.e. if the string P is a substring of S.

The sample is very fragile, so the scientists will be able to make only t tests. Help them make correct tests to determine the structure of the DNA sequence.