Background

Description

Given a string, consider the prefix string made of the first N chars of the string. Does that prefix string appear somewhere else in the string? Assume that the string is not empty and that N is in the range 1..str.length().

Format

Input

Output

Samples

abXYabc" 

true

abXYabc" 

true

abXYabc" 

false

Limitation

1s, 1024KiB for each test case.