Algorithms on strings

Plus

Problem description Progress

ID 33308. Stitches

The boy Kirill once wrote a line on a sheet of paper, consisting of large and small Latin letters, and after that he went to play football. When he returned, he found that his friend Dima had written another line of the same length under his line. Dima claims that he got his line by cyclically shifting Kirill's line a few steps to the right (cyclically shifting the line abcde by 2 positions to the right will give the line deabc).
However, Dima is known for the fact that he can accidentally make mistakes in a large number of calculations, so Kirill is at a loss – whether to believe Dima? Help him! Based on the given lines, print the minimum possible shift size or -1 if Dima made a mistake.

Input

The first two lines of the input contain the lines of Kirill and Dima, respectively. The lengths of the strings are the same, do not exceed 10000 and are not equal to 0.

Output

Print a single number – answer to the question of the problem.

Examples

#	Input	Output
1	zabcd abcdz	4

ID 33294. Cyclic string

Темы: Algorithms on strings

The string S was written many times in a row, after which a substring was taken from the resulting string and given to you. Your task is to determine the minimum possible length of the source string S.

Input

The input of the program is a string that contains only Latin letters, the length of the string does not exceed 50000 characters.

Output

Required to output a single number – answer to the question of the problem.

Examples

#	Input	Output
1	z	1
2	abcdef	6

ID 23406. Unpacking a line

Темы: Algorithms on strings

We will consider only lines consisting of capital Latin letters. For example, consider the string AAAABCCCCCDDDD. The length of this string is 14. Since the string consists of only Latin letters, the repeated characters can be removed and replaced by numbers specifying the number of repetitions. Thus, this string can be represented as 4AB5C4D. The length of such a string is 7. We will call the described method packing a string.

Write a program that takes a packed string and restores the original string from it.

Output data

The input file contains one packed line. A string can only contain constructions of the form nA, where n is the number of repetitions of a character (an integer from 2 to 99), and A is a capital Latin letter, or constructions of the form A, that is, a character without a number that defines ;number of repetitions. The maximum length of a string does not exceed 80.

Output

Output the restored string to the output file. In this case, the string must be broken into lines of exactly 40 characters (except for the last one, which may contain less than 40 characters).

Examples

Input	Output
3A4B7D	AAABBBBDDDDDDD
22D7AC18FGD	DDDDDDDDDDDDDDDDDDDDDDAAAAAAACFFFFFFFFFF FFFFFFFFGD
95AB	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAB
40AB39A	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

ID 38365. Inventive Petya

Темы: Algorithms on strings

Petya found an old telegraph machine in the attic and attached to it an ingenious device that can print a certain word on the telegraph tape (let's denote it as X). Petino's device can print this word on the tape any number of times. Petya can force the device to print any other message on the tape, but for this he needs to disassemble his ingenious device, and after that he will no longer be able to print message X. And most importantly, printing even one character of another message will require more effort from Petya, than printing the word X on tape using a contraption.

Petya wants to make it seem to everyone that he received a message Z by telegraph. To do this, he can (strictly in this sequence):

print message X as many times as you want
take apart the contraption and type something else character-by-character (let's call it Y)
tear off and discard the beginning of the tape so that the remaining tape prints exactly the message Z

Since typing individual characters of message Y is quite difficult, Petya wants message Y to contain as few characters as possible.

For a better understanding of the task, see examples and explanations for them.

Input
The first line contains the word X, which Petya can type as many times as he likes with the ingenious device. The second line contains the message Z that Petya wants to receive. Each message consists only of small Latin letters and has a maximum length of 100 characters.

Imprint
Print the shortest message Y that Petya will have to type manually.

Examples

#	Input	Output	Explanation
1	mama amamam	m	First, Petya will type the word mama twice, then he will print the letter m to it, and then he will cut off and discard the three initial characters (mam). The answer is the letter m, printed separately.
2	ura mura	mura	It would seem that Petya should first type the letter m, and then the word ura, which he can type. However, in order to type m, he would have to disassemble his device, and he would also have to type ura character-by-character.
3	computer comp	comp	It would seem that Petya can type the word computer, and then cut off and throw away the end — however, he cannot do this, because he can only cut and discard the beginning of the tape.
4	ejudge judge		It is enough for Petya to type the word ejudge once, and then cut off and discard the letter e. It doesn't have to print anything character-by-character, so the answer is an empty string.
5	m hmm		It is enough to print the original word three times and the desired result will be obtained. Nothing needs to be added, so the – empty string.

ID 38848. Number

Темы: Using sort Algorithms on strings

Vasya wrote a large number on a long strip of paper and decided to show off this achievement to his older brother Petya. But as soon as he left the room to call his brother, his sister Katya ran into the room and cut a strip of paper into several pieces. As a result, one or more consecutive numbers appeared on each part.

Now Vasya cannot remember exactly what number he wrote. Just remember that it was very big. To console his younger brother, Petya decided to find out what the maximum number could be written on a strip of paper before cutting. Help him!

Input
The input consists of one or more lines, each containing a sequence of digits. The number of lines does not exceed 100, each line contains from 1 to 100 digits. It is guaranteed that the first digit in at least one line is different from zero.
The last line of the input stream contains the number -1 - a sign of the end of the data.

Imprint
Output a single line – the maximum number that could be written on the strip before cutting.

Examples

#	Input	Output
1	2 20 004 66 -1	66220004
2	3 -1	3