Unknown Language Round 3 |
---|

Finished |

The following languages are only available languages for the problems from the contest

Unknown Language Round 3:

- Pike 7.8

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

*special problem

strings

*1500

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. World of Mouth

time limit per test

5 secondsmemory limit per test

256 megabytesinput

stdinoutput

stdoutThere are a lot of rumors in the media these days. One day Aida decided to find out how rumors are made.

She asked *n* of her friends to help her. They all formed a circle and Aida told the person to her right a piece of news which was just a simple string. Then each person told the string to the person on his/her right. But they didn't tell the string exactly as they'd heard it. Each person made at most one of these two types of changes:

- Removing one character from the end of the heard string.
- Adding a character to the end of the heard string.

Finally when the rumor passed exactly *n* moves (a complete cycle), Aida heard something quite different from what she expected from the person on her left. She thinks someone has cheated and made some changes other than those explained above. Now she wants you to write a Pike piece of code which gets the initial and final strings and tells Aida whether it's possible to get to the final string from the initial one, by the rules described above.

Input

The first line contains a single integer *n* (2 ≤ *n* ≤ 8 × 10^{6}), the number of Aida's friends. The following two lines contain a non-empty string each — initial and final strings. The lengths of strings are at most 10^{7} and they only contain English alphabet letters.

Output

Write a single YES or NO. Write YES only if it's possible to get to the final string from the initial string.

Examples

Input

100

Codeforces

MMIODPC

Output

Yes

Input

5

MMIOD

CF

Output

No

Note

The input is case-sensitive, while the output is not.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/09/2024 03:07:03 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|