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