Find all subsequences of given string

Question

I have a string (which does not contain a newline character) and I want to find all subsequences of another string that are in the first one.

For example, let's assume that the string that I am looking for is "hello world". If I search (using a Regex) for it in this string: "1h2e3l4l5o6 7w8o9r0l0d0", it should be able to find out that it does contain (once) the string "hello world". It should also be able to find multiple matches in the following string: "hheelloo wwoorrlldd".

I have the following code:

string stringToSearch = // could be anything (no newline)
int numOfSubSeq = 0;
Regex myRegex = new Regex("h.*e.*l.*l.*o.* .*w.*o.*r.*l.*d");
MatchCollection matches = myRegex.Matches(stringToSearch);
numOfSubSeq = matches.Count; // I only need the number of matches

This works. Sort of. If stringToSearch is "1h2e3l4l5o6 7w8o9r0l0d0", it works just fine. But, if stringToSearch is "hheelloo wwoorrlldd", then this Regex can find only one match, which is wrong.

Any ideas on how I can fix this?

Answer 1

You won't have any luck doing this with .NET regexes. Your best bet would be to write an algorithm for it. Regexes aren't the right tool for the job.

That said, you can do this with PCRE regexes, and I did just that for fun ;)

Disclaimer: I'm the author of the library I used in this post.

Fisrt, install PCRE.NET:

Install-Package PCRE.NET

Then, build a pattern such as this:

h.*?e.*?l.*?l.*?o.*?\ .*?w.*?o.*?r.*?l.*?d(?C1)

That (?C1) thing is called a callout in PCRE parlance. It instructs the regex engine to call a custom function of yours at this point of the matching. You can then say if that part should be considered as matching or not.

Count the number of times your callout function is invoked, and tell the engine the pattern should fail, which will force it to backtrack. Job done.

public static int GetMatchCount(string searchFor, string searchIn)
{
    if (string.IsNullOrEmpty(searchFor) || string.IsNullOrEmpty(searchIn))
        return 0;

    var patternBuilder = new StringBuilder();
    foreach (var searchChar in searchFor)
        patternBuilder.Append(Regex.Escape(searchChar.ToString())).Append(".*?");

    patternBuilder.Length -= 3;
    patternBuilder.Append("(?C1)");

    var pattern = new PcreRegex(patternBuilder.ToString());

    var count = 0;
    pattern.Match(searchIn, callout =>
    {
        ++count;
        return PcreCalloutResult.Fail;
    });

    return count;
}

Calling GetMatchCount("hello world", "hheelloo wwoorrlldd") returns 512.

---

Oh, by the way if you'd like to actually see where the characters are located in the input string, here's some code for that:

public static void PrintMatches(string searchFor, string searchIn)
{
    if (string.IsNullOrEmpty(searchFor) || string.IsNullOrEmpty(searchIn))
        return;

    var patternBuilder = new StringBuilder();
    foreach (var searchChar in searchFor)
        patternBuilder.Append("(").Append(Regex.Escape(searchChar.ToString())).Append(").*?");

    patternBuilder.Length -= 3;
    patternBuilder.Append("(?C1)");

    var pattern = new PcreRegex(patternBuilder.ToString());
    var outputBuilder = new StringBuilder();

    Console.WriteLine(searchIn);
    pattern.Match(searchIn, callout =>
    {
        outputBuilder.Clear();
        outputBuilder.Append(' ', searchIn.Length);

        foreach (var group in callout.Match.Groups.Skip(1))
            outputBuilder[group.Index] = '^';

        Console.WriteLine(outputBuilder);

        return PcreCalloutResult.Fail;
    });
}

And here's the result:

hheelloo  wwoorrlldd
^ ^ ^^^ ^ ^ ^ ^ ^ ^
^ ^ ^^^ ^ ^ ^ ^ ^  ^
^ ^ ^^^ ^ ^ ^ ^  ^^
^ ^ ^^^ ^ ^ ^ ^  ^ ^
^ ^ ^^^ ^ ^ ^  ^^ ^
^ ^ ^^^ ^ ^ ^  ^^  ^
^ ^ ^^^ ^ ^ ^  ^ ^^
^ ^ ^^^ ^ ^ ^  ^ ^ ^
^ ^ ^^^ ^ ^  ^^ ^ ^
^ ^ ^^^ ^ ^  ^^ ^  ^
^ ^ ^^^ ^ ^  ^^  ^^
^ ^ ^^^ ^ ^  ^^  ^ ^
^ ^ ^^^ ^ ^  ^ ^^ ^
^ ^ ^^^ ^ ^  ^ ^^  ^
^ ^ ^^^ ^ ^  ^ ^ ^^
^ ^ ^^^ ^ ^  ^ ^ ^ ^
^ ^ ^^^ ^  ^^ ^ ^ ^
^ ^ ^^^ ^  ^^ ^ ^  ^
^ ^ ^^^ ^  ^^ ^  ^^
^ ^ ^^^ ^  ^^ ^  ^ ^
^ ^ ^^^ ^  ^^  ^^ ^
^ ^ ^^^ ^  ^^  ^^  ^
^ ^ ^^^ ^  ^^  ^ ^^
^ ^ ^^^ ^  ^^  ^ ^ ^
^ ^ ^^^ ^  ^ ^^ ^ ^
^ ^ ^^^ ^  ^ ^^ ^  ^
^ ^ ^^^ ^  ^ ^^  ^^
^ ^ ^^^ ^  ^ ^^  ^ ^
^ ^ ^^^ ^  ^ ^ ^^ ^
^ ^ ^^^ ^  ^ ^ ^^  ^
^ ^ ^^^ ^  ^ ^ ^ ^^
^ ^ ^^^ ^  ^ ^ ^ ^ ^
^ ^ ^^^  ^^ ^ ^ ^ ^
^ ^ ^^^  ^^ ^ ^ ^  ^
^ ^ ^^^  ^^ ^ ^  ^^
^ ^ ^^^  ^^ ^ ^  ^ ^
^ ^ ^^^  ^^ ^  ^^ ^
^ ^ ^^^  ^^ ^  ^^  ^
^ ^ ^^^  ^^ ^  ^ ^^
^ ^ ^^^  ^^ ^  ^ ^ ^
^ ^ ^^^  ^^  ^^ ^ ^
^ ^ ^^^  ^^  ^^ ^  ^
^ ^ ^^^  ^^  ^^  ^^
^ ^ ^^^  ^^  ^^  ^ ^
^ ^ ^^^  ^^  ^ ^^ ^
^ ^ ^^^  ^^  ^ ^^  ^
^ ^ ^^^  ^^  ^ ^ ^^
^ ^ ^^^  ^^  ^ ^ ^ ^
^ ^ ^^^  ^ ^^ ^ ^ ^
^ ^ ^^^  ^ ^^ ^ ^  ^
^ ^ ^^^  ^ ^^ ^  ^^
^ ^ ^^^  ^ ^^ ^  ^ ^
^ ^ ^^^  ^ ^^  ^^ ^
^ ^ ^^^  ^ ^^  ^^  ^
^ ^ ^^^  ^ ^^  ^ ^^
^ ^ ^^^  ^ ^^  ^ ^ ^
^ ^ ^^^  ^ ^ ^^ ^ ^
^ ^ ^^^  ^ ^ ^^ ^  ^
^ ^ ^^^  ^ ^ ^^  ^^
^ ^ ^^^  ^ ^ ^^  ^ ^
^ ^ ^^^  ^ ^ ^ ^^ ^
^ ^ ^^^  ^ ^ ^ ^^  ^
^ ^ ^^^  ^ ^ ^ ^ ^^
^ ^ ^^^  ^ ^ ^ ^ ^ ^
^ ^ ^^ ^^ ^ ^ ^ ^ ^
^ ^ ^^ ^^ ^ ^ ^ ^  ^
^ ^ ^^ ^^ ^ ^ ^  ^^
^ ^ ^^ ^^ ^ ^ ^  ^ ^
^ ^ ^^ ^^ ^ ^  ^^ ^
^ ^ ^^ ^^ ^ ^  ^^  ^
^ ^ ^^ ^^ ^ ^  ^ ^^
^ ^ ^^ ^^ ^ ^  ^ ^ ^
^ ^ ^^ ^^ ^  ^^ ^ ^
^ ^ ^^ ^^ ^  ^^ ^  ^
^ ^ ^^ ^^ ^  ^^  ^^
^ ^ ^^ ^^ ^  ^^  ^ ^
^ ^ ^^ ^^ ^  ^ ^^ ^
^ ^ ^^ ^^ ^  ^ ^^  ^
^ ^ ^^ ^^ ^  ^ ^ ^^
^ ^ ^^ ^^ ^  ^ ^ ^ ^
^ ^ ^^ ^^  ^^ ^ ^ ^
^ ^ ^^ ^^  ^^ ^ ^  ^
^ ^ ^^ ^^  ^^ ^  ^^
^ ^ ^^ ^^  ^^ ^  ^ ^
^ ^ ^^ ^^  ^^  ^^ ^
^ ^ ^^ ^^  ^^  ^^  ^
^ ^ ^^ ^^  ^^  ^ ^^
^ ^ ^^ ^^  ^^  ^ ^ ^
^ ^ ^^ ^^  ^ ^^ ^ ^
^ ^ ^^ ^^  ^ ^^ ^  ^
^ ^ ^^ ^^  ^ ^^  ^^
^ ^ ^^ ^^  ^ ^^  ^ ^
^ ^ ^^ ^^  ^ ^ ^^ ^
^ ^ ^^ ^^  ^ ^ ^^  ^
^ ^ ^^ ^^  ^ ^ ^ ^^
^ ^ ^^ ^^  ^ ^ ^ ^ ^
^ ^ ^^ ^ ^^ ^ ^ ^ ^
^ ^ ^^ ^ ^^ ^ ^ ^  ^
^ ^ ^^ ^ ^^ ^ ^  ^^
^ ^ ^^ ^ ^^ ^ ^  ^ ^
^ ^ ^^ ^ ^^ ^  ^^ ^
^ ^ ^^ ^ ^^ ^  ^^  ^
^ ^ ^^ ^ ^^ ^  ^ ^^
^ ^ ^^ ^ ^^ ^  ^ ^ ^
^ ^ ^^ ^ ^^  ^^ ^ ^
^ ^ ^^ ^ ^^  ^^ ^  ^
^ ^ ^^ ^ ^^  ^^  ^^
^ ^ ^^ ^ ^^  ^^  ^ ^
^ ^ ^^ ^ ^^  ^ ^^ ^
^ ^ ^^ ^ ^^  ^ ^^  ^
^ ^ ^^ ^ ^^  ^ ^ ^^
^ ^ ^^ ^ ^^  ^ ^ ^ ^
^ ^ ^^ ^ ^ ^^ ^ ^ ^
^ ^ ^^ ^ ^ ^^ ^ ^  ^
^ ^ ^^ ^ ^ ^^ ^  ^^
^ ^ ^^ ^ ^ ^^ ^  ^ ^
^ ^ ^^ ^ ^ ^^  ^^ ^
^ ^ ^^ ^ ^ ^^  ^^  ^
^ ^ ^^ ^ ^ ^^  ^ ^^
^ ^ ^^ ^ ^ ^^  ^ ^ ^
^ ^ ^^ ^ ^ ^ ^^ ^ ^
^ ^ ^^ ^ ^ ^ ^^ ^  ^
^ ^ ^^ ^ ^ ^ ^^  ^^
^ ^ ^^ ^ ^ ^ ^^  ^ ^
^ ^ ^^ ^ ^ ^ ^ ^^ ^
^ ^ ^^ ^ ^ ^ ^ ^^  ^
^ ^ ^^ ^ ^ ^ ^ ^ ^^
^ ^ ^^ ^ ^ ^ ^ ^ ^ ^
^  ^^^^ ^ ^ ^ ^ ^ ^
^  ^^^^ ^ ^ ^ ^ ^  ^
^  ^^^^ ^ ^ ^ ^  ^^
^  ^^^^ ^ ^ ^ ^  ^ ^
^  ^^^^ ^ ^ ^  ^^ ^
^  ^^^^ ^ ^ ^  ^^  ^
^  ^^^^ ^ ^ ^  ^ ^^
^  ^^^^ ^ ^ ^  ^ ^ ^
^  ^^^^ ^ ^  ^^ ^ ^
^  ^^^^ ^ ^  ^^ ^  ^
^  ^^^^ ^ ^  ^^  ^^
^  ^^^^ ^ ^  ^^  ^ ^
^  ^^^^ ^ ^  ^ ^^ ^
^  ^^^^ ^ ^  ^ ^^  ^
^  ^^^^ ^ ^  ^ ^ ^^
^  ^^^^ ^ ^  ^ ^ ^ ^
^  ^^^^ ^  ^^ ^ ^ ^
^  ^^^^ ^  ^^ ^ ^  ^
^  ^^^^ ^  ^^ ^  ^^
^  ^^^^ ^  ^^ ^  ^ ^
^  ^^^^ ^  ^^  ^^ ^
^  ^^^^ ^  ^^  ^^  ^
^  ^^^^ ^  ^^  ^ ^^
^  ^^^^ ^  ^^  ^ ^ ^
^  ^^^^ ^  ^ ^^ ^ ^
^  ^^^^ ^  ^ ^^ ^  ^
^  ^^^^ ^  ^ ^^  ^^
^  ^^^^ ^  ^ ^^  ^ ^
^  ^^^^ ^  ^ ^ ^^ ^
^  ^^^^ ^  ^ ^ ^^  ^
^  ^^^^ ^  ^ ^ ^ ^^
^  ^^^^ ^  ^ ^ ^ ^ ^
^  ^^^^  ^^ ^ ^ ^ ^
^  ^^^^  ^^ ^ ^ ^  ^
^  ^^^^  ^^ ^ ^  ^^
^  ^^^^  ^^ ^ ^  ^ ^
^  ^^^^  ^^ ^  ^^ ^
^  ^^^^  ^^ ^  ^^  ^
^  ^^^^  ^^ ^  ^ ^^
^  ^^^^  ^^ ^  ^ ^ ^
^  ^^^^  ^^  ^^ ^ ^
^  ^^^^  ^^  ^^ ^  ^
^  ^^^^  ^^  ^^  ^^
^  ^^^^  ^^  ^^  ^ ^
^  ^^^^  ^^  ^ ^^ ^
^  ^^^^  ^^  ^ ^^  ^
^  ^^^^  ^^  ^ ^ ^^
^  ^^^^  ^^  ^ ^ ^ ^
^  ^^^^  ^ ^^ ^ ^ ^
^  ^^^^  ^ ^^ ^ ^  ^
^  ^^^^  ^ ^^ ^  ^^
^  ^^^^  ^ ^^ ^  ^ ^
^  ^^^^  ^ ^^  ^^ ^
^  ^^^^  ^ ^^  ^^  ^
^  ^^^^  ^ ^^  ^ ^^
^  ^^^^  ^ ^^  ^ ^ ^
^  ^^^^  ^ ^ ^^ ^ ^
^  ^^^^  ^ ^ ^^ ^  ^
^  ^^^^  ^ ^ ^^  ^^
^  ^^^^  ^ ^ ^^  ^ ^
^  ^^^^  ^ ^ ^ ^^ ^
^  ^^^^  ^ ^ ^ ^^  ^
^  ^^^^  ^ ^ ^ ^ ^^
^  ^^^^  ^ ^ ^ ^ ^ ^
^  ^^^ ^^ ^ ^ ^ ^ ^
^  ^^^ ^^ ^ ^ ^ ^  ^
^  ^^^ ^^ ^ ^ ^  ^^
^  ^^^ ^^ ^ ^ ^  ^ ^
^  ^^^ ^^ ^ ^  ^^ ^
^  ^^^ ^^ ^ ^  ^^  ^
^  ^^^ ^^ ^ ^  ^ ^^
^  ^^^ ^^ ^ ^  ^ ^ ^
^  ^^^ ^^ ^  ^^ ^ ^
^  ^^^ ^^ ^  ^^ ^  ^
^  ^^^ ^^ ^  ^^  ^^
^  ^^^ ^^ ^  ^^  ^ ^
^  ^^^ ^^ ^  ^ ^^ ^
^  ^^^ ^^ ^  ^ ^^  ^
^  ^^^ ^^ ^  ^ ^ ^^
^  ^^^ ^^ ^  ^ ^ ^ ^
^  ^^^ ^^  ^^ ^ ^ ^
^  ^^^ ^^  ^^ ^ ^  ^
^  ^^^ ^^  ^^ ^  ^^
^  ^^^ ^^  ^^ ^  ^ ^
^  ^^^ ^^  ^^  ^^ ^
^  ^^^ ^^  ^^  ^^  ^
^  ^^^ ^^  ^^  ^ ^^
^  ^^^ ^^  ^^  ^ ^ ^
^  ^^^ ^^  ^ ^^ ^ ^
^  ^^^ ^^  ^ ^^ ^  ^
^  ^^^ ^^  ^ ^^  ^^
^  ^^^ ^^  ^ ^^  ^ ^
^  ^^^ ^^  ^ ^ ^^ ^
^  ^^^ ^^  ^ ^ ^^  ^
^  ^^^ ^^  ^ ^ ^ ^^
^  ^^^ ^^  ^ ^ ^ ^ ^
^  ^^^ ^ ^^ ^ ^ ^ ^
^  ^^^ ^ ^^ ^ ^ ^  ^
^  ^^^ ^ ^^ ^ ^  ^^
^  ^^^ ^ ^^ ^ ^  ^ ^
^  ^^^ ^ ^^ ^  ^^ ^
^  ^^^ ^ ^^ ^  ^^  ^
^  ^^^ ^ ^^ ^  ^ ^^
^  ^^^ ^ ^^ ^  ^ ^ ^
^  ^^^ ^ ^^  ^^ ^ ^
^  ^^^ ^ ^^  ^^ ^  ^
^  ^^^ ^ ^^  ^^  ^^
^  ^^^ ^ ^^  ^^  ^ ^
^  ^^^ ^ ^^  ^ ^^ ^
^  ^^^ ^ ^^  ^ ^^  ^
^  ^^^ ^ ^^  ^ ^ ^^
^  ^^^ ^ ^^  ^ ^ ^ ^
^  ^^^ ^ ^ ^^ ^ ^ ^
^  ^^^ ^ ^ ^^ ^ ^  ^
^  ^^^ ^ ^ ^^ ^  ^^
^  ^^^ ^ ^ ^^ ^  ^ ^
^  ^^^ ^ ^ ^^  ^^ ^
^  ^^^ ^ ^ ^^  ^^  ^
^  ^^^ ^ ^ ^^  ^ ^^
^  ^^^ ^ ^ ^^  ^ ^ ^
^  ^^^ ^ ^ ^ ^^ ^ ^
^  ^^^ ^ ^ ^ ^^ ^  ^
^  ^^^ ^ ^ ^ ^^  ^^
^  ^^^ ^ ^ ^ ^^  ^ ^
^  ^^^ ^ ^ ^ ^ ^^ ^
^  ^^^ ^ ^ ^ ^ ^^  ^
^  ^^^ ^ ^ ^ ^ ^ ^^
^  ^^^ ^ ^ ^ ^ ^ ^ ^
 ^^ ^^^ ^ ^ ^ ^ ^ ^
 ^^ ^^^ ^ ^ ^ ^ ^  ^
 ^^ ^^^ ^ ^ ^ ^  ^^
 ^^ ^^^ ^ ^ ^ ^  ^ ^
 ^^ ^^^ ^ ^ ^  ^^ ^
 ^^ ^^^ ^ ^ ^  ^^  ^
 ^^ ^^^ ^ ^ ^  ^ ^^
 ^^ ^^^ ^ ^ ^  ^ ^ ^
 ^^ ^^^ ^ ^  ^^ ^ ^
 ^^ ^^^ ^ ^  ^^ ^  ^
 ^^ ^^^ ^ ^  ^^  ^^
 ^^ ^^^ ^ ^  ^^  ^ ^
 ^^ ^^^ ^ ^  ^ ^^ ^
 ^^ ^^^ ^ ^  ^ ^^  ^
 ^^ ^^^ ^ ^  ^ ^ ^^
 ^^ ^^^ ^ ^  ^ ^ ^ ^
 ^^ ^^^ ^  ^^ ^ ^ ^
 ^^ ^^^ ^  ^^ ^ ^  ^
 ^^ ^^^ ^  ^^ ^  ^^
 ^^ ^^^ ^  ^^ ^  ^ ^
 ^^ ^^^ ^  ^^  ^^ ^
 ^^ ^^^ ^  ^^  ^^  ^
 ^^ ^^^ ^  ^^  ^ ^^
 ^^ ^^^ ^  ^^  ^ ^ ^
 ^^ ^^^ ^  ^ ^^ ^ ^
 ^^ ^^^ ^  ^ ^^ ^  ^
 ^^ ^^^ ^  ^ ^^  ^^
 ^^ ^^^ ^  ^ ^^  ^ ^
 ^^ ^^^ ^  ^ ^ ^^ ^
 ^^ ^^^ ^  ^ ^ ^^  ^
 ^^ ^^^ ^  ^ ^ ^ ^^
 ^^ ^^^ ^  ^ ^ ^ ^ ^
 ^^ ^^^  ^^ ^ ^ ^ ^
 ^^ ^^^  ^^ ^ ^ ^  ^
 ^^ ^^^  ^^ ^ ^  ^^
 ^^ ^^^  ^^ ^ ^  ^ ^
 ^^ ^^^  ^^ ^  ^^ ^
 ^^ ^^^  ^^ ^  ^^  ^
 ^^ ^^^  ^^ ^  ^ ^^
 ^^ ^^^  ^^ ^  ^ ^ ^
 ^^ ^^^  ^^  ^^ ^ ^
 ^^ ^^^  ^^  ^^ ^  ^
 ^^ ^^^  ^^  ^^  ^^
 ^^ ^^^  ^^  ^^  ^ ^
 ^^ ^^^  ^^  ^ ^^ ^
 ^^ ^^^  ^^  ^ ^^  ^
 ^^ ^^^  ^^  ^ ^ ^^
 ^^ ^^^  ^^  ^ ^ ^ ^
 ^^ ^^^  ^ ^^ ^ ^ ^
 ^^ ^^^  ^ ^^ ^ ^  ^
 ^^ ^^^  ^ ^^ ^  ^^
 ^^ ^^^  ^ ^^ ^  ^ ^
 ^^ ^^^  ^ ^^  ^^ ^
 ^^ ^^^  ^ ^^  ^^  ^
 ^^ ^^^  ^ ^^  ^ ^^
 ^^ ^^^  ^ ^^  ^ ^ ^
 ^^ ^^^  ^ ^ ^^ ^ ^
 ^^ ^^^  ^ ^ ^^ ^  ^
 ^^ ^^^  ^ ^ ^^  ^^
 ^^ ^^^  ^ ^ ^^  ^ ^
 ^^ ^^^  ^ ^ ^ ^^ ^
 ^^ ^^^  ^ ^ ^ ^^  ^
 ^^ ^^^  ^ ^ ^ ^ ^^
 ^^ ^^^  ^ ^ ^ ^ ^ ^
 ^^ ^^ ^^ ^ ^ ^ ^ ^
 ^^ ^^ ^^ ^ ^ ^ ^  ^
 ^^ ^^ ^^ ^ ^ ^  ^^
 ^^ ^^ ^^ ^ ^ ^  ^ ^
 ^^ ^^ ^^ ^ ^  ^^ ^
 ^^ ^^ ^^ ^ ^  ^^  ^
 ^^ ^^ ^^ ^ ^  ^ ^^
 ^^ ^^ ^^ ^ ^  ^ ^ ^
 ^^ ^^ ^^ ^  ^^ ^ ^
 ^^ ^^ ^^ ^  ^^ ^  ^
 ^^ ^^ ^^ ^  ^^  ^^
 ^^ ^^ ^^ ^  ^^  ^ ^
 ^^ ^^ ^^ ^  ^ ^^ ^
 ^^ ^^ ^^ ^  ^ ^^  ^
 ^^ ^^ ^^ ^  ^ ^ ^^
 ^^ ^^ ^^ ^  ^ ^ ^ ^
 ^^ ^^ ^^  ^^ ^ ^ ^
 ^^ ^^ ^^  ^^ ^ ^  ^
 ^^ ^^ ^^  ^^ ^  ^^
 ^^ ^^ ^^  ^^ ^  ^ ^
 ^^ ^^ ^^  ^^  ^^ ^
 ^^ ^^ ^^  ^^  ^^  ^
 ^^ ^^ ^^  ^^  ^ ^^
 ^^ ^^ ^^  ^^  ^ ^ ^
 ^^ ^^ ^^  ^ ^^ ^ ^
 ^^ ^^ ^^  ^ ^^ ^  ^
 ^^ ^^ ^^  ^ ^^  ^^
 ^^ ^^ ^^  ^ ^^  ^ ^
 ^^ ^^ ^^  ^ ^ ^^ ^
 ^^ ^^ ^^  ^ ^ ^^  ^
 ^^ ^^ ^^  ^ ^ ^ ^^
 ^^ ^^ ^^  ^ ^ ^ ^ ^
 ^^ ^^ ^ ^^ ^ ^ ^ ^
 ^^ ^^ ^ ^^ ^ ^ ^  ^
 ^^ ^^ ^ ^^ ^ ^  ^^
 ^^ ^^ ^ ^^ ^ ^  ^ ^
 ^^ ^^ ^ ^^ ^  ^^ ^
 ^^ ^^ ^ ^^ ^  ^^  ^
 ^^ ^^ ^ ^^ ^  ^ ^^
 ^^ ^^ ^ ^^ ^  ^ ^ ^
 ^^ ^^ ^ ^^  ^^ ^ ^
 ^^ ^^ ^ ^^  ^^ ^  ^
 ^^ ^^ ^ ^^  ^^  ^^
 ^^ ^^ ^ ^^  ^^  ^ ^
 ^^ ^^ ^ ^^  ^ ^^ ^
 ^^ ^^ ^ ^^  ^ ^^  ^
 ^^ ^^ ^ ^^  ^ ^ ^^
 ^^ ^^ ^ ^^  ^ ^ ^ ^
 ^^ ^^ ^ ^ ^^ ^ ^ ^
 ^^ ^^ ^ ^ ^^ ^ ^  ^
 ^^ ^^ ^ ^ ^^ ^  ^^
 ^^ ^^ ^ ^ ^^ ^  ^ ^
 ^^ ^^ ^ ^ ^^  ^^ ^
 ^^ ^^ ^ ^ ^^  ^^  ^
 ^^ ^^ ^ ^ ^^  ^ ^^
 ^^ ^^ ^ ^ ^^  ^ ^ ^
 ^^ ^^ ^ ^ ^ ^^ ^ ^
 ^^ ^^ ^ ^ ^ ^^ ^  ^
 ^^ ^^ ^ ^ ^ ^^  ^^
 ^^ ^^ ^ ^ ^ ^^  ^ ^
 ^^ ^^ ^ ^ ^ ^ ^^ ^
 ^^ ^^ ^ ^ ^ ^ ^^  ^
 ^^ ^^ ^ ^ ^ ^ ^ ^^
 ^^ ^^ ^ ^ ^ ^ ^ ^ ^
 ^ ^^^^ ^ ^ ^ ^ ^ ^
 ^ ^^^^ ^ ^ ^ ^ ^  ^
 ^ ^^^^ ^ ^ ^ ^  ^^
 ^ ^^^^ ^ ^ ^ ^  ^ ^
 ^ ^^^^ ^ ^ ^  ^^ ^
 ^ ^^^^ ^ ^ ^  ^^  ^
 ^ ^^^^ ^ ^ ^  ^ ^^
 ^ ^^^^ ^ ^ ^  ^ ^ ^
 ^ ^^^^ ^ ^  ^^ ^ ^
 ^ ^^^^ ^ ^  ^^ ^  ^
 ^ ^^^^ ^ ^  ^^  ^^
 ^ ^^^^ ^ ^  ^^  ^ ^
 ^ ^^^^ ^ ^  ^ ^^ ^
 ^ ^^^^ ^ ^  ^ ^^  ^
 ^ ^^^^ ^ ^  ^ ^ ^^
 ^ ^^^^ ^ ^  ^ ^ ^ ^
 ^ ^^^^ ^  ^^ ^ ^ ^
 ^ ^^^^ ^  ^^ ^ ^  ^
 ^ ^^^^ ^  ^^ ^  ^^
 ^ ^^^^ ^  ^^ ^  ^ ^
 ^ ^^^^ ^  ^^  ^^ ^
 ^ ^^^^ ^  ^^  ^^  ^
 ^ ^^^^ ^  ^^  ^ ^^
 ^ ^^^^ ^  ^^  ^ ^ ^
 ^ ^^^^ ^  ^ ^^ ^ ^
 ^ ^^^^ ^  ^ ^^ ^  ^
 ^ ^^^^ ^  ^ ^^  ^^
 ^ ^^^^ ^  ^ ^^  ^ ^
 ^ ^^^^ ^  ^ ^ ^^ ^
 ^ ^^^^ ^  ^ ^ ^^  ^
 ^ ^^^^ ^  ^ ^ ^ ^^
 ^ ^^^^ ^  ^ ^ ^ ^ ^
 ^ ^^^^  ^^ ^ ^ ^ ^
 ^ ^^^^  ^^ ^ ^ ^  ^
 ^ ^^^^  ^^ ^ ^  ^^
 ^ ^^^^  ^^ ^ ^  ^ ^
 ^ ^^^^  ^^ ^  ^^ ^
 ^ ^^^^  ^^ ^  ^^  ^
 ^ ^^^^  ^^ ^  ^ ^^
 ^ ^^^^  ^^ ^  ^ ^ ^
 ^ ^^^^  ^^  ^^ ^ ^
 ^ ^^^^  ^^  ^^ ^  ^
 ^ ^^^^  ^^  ^^  ^^
 ^ ^^^^  ^^  ^^  ^ ^
 ^ ^^^^  ^^  ^ ^^ ^
 ^ ^^^^  ^^  ^ ^^  ^
 ^ ^^^^  ^^  ^ ^ ^^
 ^ ^^^^  ^^  ^ ^ ^ ^
 ^ ^^^^  ^ ^^ ^ ^ ^
 ^ ^^^^  ^ ^^ ^ ^  ^
 ^ ^^^^  ^ ^^ ^  ^^
 ^ ^^^^  ^ ^^ ^  ^ ^
 ^ ^^^^  ^ ^^  ^^ ^
 ^ ^^^^  ^ ^^  ^^  ^
 ^ ^^^^  ^ ^^  ^ ^^
 ^ ^^^^  ^ ^^  ^ ^ ^
 ^ ^^^^  ^ ^ ^^ ^ ^
 ^ ^^^^  ^ ^ ^^ ^  ^
 ^ ^^^^  ^ ^ ^^  ^^
 ^ ^^^^  ^ ^ ^^  ^ ^
 ^ ^^^^  ^ ^ ^ ^^ ^
 ^ ^^^^  ^ ^ ^ ^^  ^
 ^ ^^^^  ^ ^ ^ ^ ^^
 ^ ^^^^  ^ ^ ^ ^ ^ ^
 ^ ^^^ ^^ ^ ^ ^ ^ ^
 ^ ^^^ ^^ ^ ^ ^ ^  ^
 ^ ^^^ ^^ ^ ^ ^  ^^
 ^ ^^^ ^^ ^ ^ ^  ^ ^
 ^ ^^^ ^^ ^ ^  ^^ ^
 ^ ^^^ ^^ ^ ^  ^^  ^
 ^ ^^^ ^^ ^ ^  ^ ^^
 ^ ^^^ ^^ ^ ^  ^ ^ ^
 ^ ^^^ ^^ ^  ^^ ^ ^
 ^ ^^^ ^^ ^  ^^ ^  ^
 ^ ^^^ ^^ ^  ^^  ^^
 ^ ^^^ ^^ ^  ^^  ^ ^
 ^ ^^^ ^^ ^  ^ ^^ ^
 ^ ^^^ ^^ ^  ^ ^^  ^
 ^ ^^^ ^^ ^  ^ ^ ^^
 ^ ^^^ ^^ ^  ^ ^ ^ ^
 ^ ^^^ ^^  ^^ ^ ^ ^
 ^ ^^^ ^^  ^^ ^ ^  ^
 ^ ^^^ ^^  ^^ ^  ^^
 ^ ^^^ ^^  ^^ ^  ^ ^
 ^ ^^^ ^^  ^^  ^^ ^
 ^ ^^^ ^^  ^^  ^^  ^
 ^ ^^^ ^^  ^^  ^ ^^
 ^ ^^^ ^^  ^^  ^ ^ ^
 ^ ^^^ ^^  ^ ^^ ^ ^
 ^ ^^^ ^^  ^ ^^ ^  ^
 ^ ^^^ ^^  ^ ^^  ^^
 ^ ^^^ ^^  ^ ^^  ^ ^
 ^ ^^^ ^^  ^ ^ ^^ ^
 ^ ^^^ ^^  ^ ^ ^^  ^
 ^ ^^^ ^^  ^ ^ ^ ^^
 ^ ^^^ ^^  ^ ^ ^ ^ ^
 ^ ^^^ ^ ^^ ^ ^ ^ ^
 ^ ^^^ ^ ^^ ^ ^ ^  ^
 ^ ^^^ ^ ^^ ^ ^  ^^
 ^ ^^^ ^ ^^ ^ ^  ^ ^
 ^ ^^^ ^ ^^ ^  ^^ ^
 ^ ^^^ ^ ^^ ^  ^^  ^
 ^ ^^^ ^ ^^ ^  ^ ^^
 ^ ^^^ ^ ^^ ^  ^ ^ ^
 ^ ^^^ ^ ^^  ^^ ^ ^
 ^ ^^^ ^ ^^  ^^ ^  ^
 ^ ^^^ ^ ^^  ^^  ^^
 ^ ^^^ ^ ^^  ^^  ^ ^
 ^ ^^^ ^ ^^  ^ ^^ ^
 ^ ^^^ ^ ^^  ^ ^^  ^
 ^ ^^^ ^ ^^  ^ ^ ^^
 ^ ^^^ ^ ^^  ^ ^ ^ ^
 ^ ^^^ ^ ^ ^^ ^ ^ ^
 ^ ^^^ ^ ^ ^^ ^ ^  ^
 ^ ^^^ ^ ^ ^^ ^  ^^
 ^ ^^^ ^ ^ ^^ ^  ^ ^
 ^ ^^^ ^ ^ ^^  ^^ ^
 ^ ^^^ ^ ^ ^^  ^^  ^
 ^ ^^^ ^ ^ ^^  ^ ^^
 ^ ^^^ ^ ^ ^^  ^ ^ ^
 ^ ^^^ ^ ^ ^ ^^ ^ ^
 ^ ^^^ ^ ^ ^ ^^ ^  ^
 ^ ^^^ ^ ^ ^ ^^  ^^
 ^ ^^^ ^ ^ ^ ^^  ^ ^
 ^ ^^^ ^ ^ ^ ^ ^^ ^
 ^ ^^^ ^ ^ ^ ^ ^^  ^
 ^ ^^^ ^ ^ ^ ^ ^ ^^
 ^ ^^^ ^ ^ ^ ^ ^ ^ ^