Two background services, A and B, each produce a log of events encoded as a string. A monitoring pipeline merges the two logs into a single combined log by interleaving their characters: every character of A and every character of B must appear exactly once in the merged log, and each source's own characters must keep their original relative order. Additionally, because of a fairness rule, the merged log may never contain more than k consecutive characters taken from the same source in a row.

Given k, the two source logs, and a candidate merged log, determine whether the candidate could actually have been produced this way.

Input format

Line 1: an integer k. Line 2: the log from service A (may be empty, producing a blank line). Line 3: the log from service B (may be empty, producing a blank line). Line 4: the candidate merged log (may be empty, producing a blank line).

All logs contain only lowercase English letters.

Output format

Print 1 if the candidate log can be produced by interleaving the two source logs (preserving each source's internal order) with no run of more than k consecutive characters from the same source, and 0 otherwise.

Constraints

• 1 <= k <= 5
• 0 <= |A|, |B| <= 12

2
ab
cd
acbd

1

1
aa
b
aab

0