## Task

You are given three non negative integers `a`, `b` and `n`, and making an infinite sequence just like fibonacci sequence, use the following rules:

- step 1: use `ab` as the initial sequence.
- step 2: calculate the sum of the last two digits of the sequence, and append it to the end of sequence.
- repeat step 2 until you have enough digits

Your task is to complete the function which returns the `n`th digit (0-based) of the sequence.

### Notes:

- `0 <= a, b <= 9`, `0 <= n <= 10^10`
- `16` fixed testcases
- `100` random testcases, testing for correctness of solution
- `100` random testcases, testing for performance of code
- All inputs are valid.
- Pay attention to code performance.


## Examples

For `a = 7, b = 8 and n = 9` the output should be `5`, because the sequence is:
```
78 -> 7815 -> 78156 -> 7815611 -> 78156112 -> 781561123 -> 7815611235 -> ...
``` 

and the 9th digit of the sequence is `5`.

---

For `a = 0, b = 0 and n = 100000000` the output should be `0`, because all the digits in this sequence are `0`.

Difficulty: introductory

Starter code:

def find(a, b, n):
	

Solutions:
def find(a,b,n):
    strng = str(a) + str(b)
    #there are 10 and 4 long loops
    if (n > 20): n = n%20+20
    while len(strng) <= n:
        next_ch = int(strng[-1]) + int(strng[-2])
        strng = strng + str(next_ch)
    return int(strng[n])

L = [
("", "0"),
("0", "1123581347"),
("0224610", "1123581347"),
("03369156", "1123581347"),
("0448", "1235813471"),
("05510", "1123581347"),
("066", "1235813471"),
("077", "1459"),
("088167", "1347112358"),
("099189178156", "1123581347"),
("10", "1123581347"),
("", "1123581347"),
("", "1235813471"),
("", "1347112358"),
("", "1459"),
("156", "1123581347"),
("167", "1347112358"),
("178156", "1123581347"),
("189178156", "1123581347"),
("1910", "1123581347"),
("20224610", "1123581347"),
("2", "1347112358"),
("224610", "1123581347"),
("", "2358134711"),
("24610", "1123581347"),
("257", "1235813471"),
("268", "1459"),
("279167", "1347112358"),
("2810", "1123581347"),
("29", "1123581347"),
("303369156", "1123581347"),
("3", "1459"),
("3257", "1235813471"),
("3369156", "1123581347"),
("", "3471123581"),
("", "3581347112"),
("369156", "1123581347"),
("3710", "1123581347"),
("38", "1123581347"),
("39", "1235813471"),
("40448", "1235813471"),
("4156", "1123581347"),
("4268", "1459"),
("43710", "1123581347"),
("448", "1235813471"),
("", "4591"),
("4610", "1123581347"),
("", "4711235813"),
("48", "1235813471"),
("49", "1347112358"),
("505510", "1123581347"),
("5167", "1347112358"),
("5279167", "1347112358"),
("538", "1123581347"),
("549", "1347112358"),
("5510", "1123581347"),
("56", "1123581347"),
("57", "1235813471"),
("", "5813471123"),
("", "5914"),
("6066", "1235813471"),
("6178156", "1123581347"),
("62810", "1123581347"),
("639", "1235813471"),
("6410", "1123581347"),
("65", "1123581347"),
("66", "1235813471"),
("67", "1347112358"),
("68", "1459"),
("69156", "1123581347"),
("7077", "1459"),
("7189178156", "1123581347"),
("729", "1123581347"),
("7310", "1123581347"),
("74", "1123581347"),
("75", "1235813471"),
("76", "1347112358"),
("77", "1459"),
("78156", "1123581347"),
("79167", "1347112358"),
("8088167", "1347112358"),
("81910", "1123581347"),
("8210", "1123581347"),
("83", "1123581347"),
("84", "1235813471"),
("85", "1347112358"),
("86", "1459"),
("87156", "1123581347"),
("88167", "1347112358"),
("89178156", "1123581347"),
("9099189178156", "1123581347"),
("9110", "1123581347"),
("92", "1123581347"),
("93", "1235813471"),
("94", "1347112358"),
("95", "1459"),
("96156", "1123581347"),
("97167", "1347112358"),
("98178156", "1123581347"),
("99189178156", "1123581347")
]

# I couldn't get my hand on a working pattern so fuck it
# At least it's fast
def find(a, b, n):
    start, loop = L[10*a+b]
    if n < len(start): return int(start[n])
    return int(loop[(n-len(start))%len(loop)])

# Precompute all 2 digit suffixes into an associated prefix and repeating loop
# E.g. build until we get two repeating values:
#   98 -> [17, 8, 15, 6, 11, 2, 3, 5, 8, 13, 4, 7, 11, 2] (Note: [11, 2] is repeated)
#   -> Prefix '17815611', Loop: '2358134711'
#
# Now any number ending with 98 has a predefined prefix and cycle, e.g.:
#   123 + 598 -> 123598 -> 98 -> Prefix '17815611', Loop: '2358134711'
# Hence 123 + 598 starts with '12359817815611' and then repeats '2358134711' indefinitely

# Dict[str, Tuple[str, str]]
lookup = {}
for i in range(10):
    for j in range(10):
        start = f'{i}{j}'
        n = int(start)
        s = [0, n]
        seen = {}
        while True:
            x = s[-1]
            if x < 10:
                x = x + s[-2] % 10
            else:
                x = (x // 10) + (x % 10)
            
            pair = (s[-1], x)
            if pair not in seen:
                s.append(x)
                seen[pair] = len(s)
            else:
                # idx is the point where prefix finishes and loop starts
                idx = seen[pair] - 1
                prefix = s[2:idx]  # Skip the leading zero and the starting value
                loop = s[idx:]
                lookup[start] = (''.join(map(str, prefix)), ''.join(map(str, loop)))
                break

def find(a, b, n):
    start = f'{a}{b}'[-2:].rjust(2, '0')
    prefix, loop = lookup[start]
    s = str(a) + str(b) + prefix + loop
    
    if n < len(s):
        # Digit in initial supplied digits, the sum of their last two digits or the prefix
        return int(s[n])

    # Digit is in the loop
    m = (n - len(s)) % len(loop)
    return int(loop[m])


def find(a, b, n):
    s = str(a) + str(b)
    
    while s[-3:] not in {"000", "112", "145"}:
        s += str(int(s[-2]) + int(s[-1]))
    
    base = len(s) - 3
    loop = {"000": "000",
            "112": "1123581347",
            "145": "1459"}[s[-3:]]
    
    return int(s[n]) if n < base else int(loop[(n-base) % len(loop)])

def find(a, b, n):
    bag, seq = {}, [a, b]
    while True:
        if (a, b) in bag: break
        bag[a, b] = len(seq)
        a, b = b, a+b
        if b > 9:
            a, b = divmod(b, 10)
            seq.append(a)
        seq.append(b)
    return seq[n] if n < len(seq) else \
        seq[bag[a, b] + (n - bag[a, b]) % (len(seq) - bag[a, b])]


from itertools import islice


def find_repeat(a, b):
    x = f'{a}{b}'
    seen = {x: 0}
    while True:
        x += str(int(x[-2]) + int(x[-1]))
        last = x[-2:]
        if last in seen:
            i = seen[last]
            return x[:i], x[i:-2]
        seen[last] = len(x) - 2
    
def find(a,b,n):
    prefix, repeat = [list(map(int, x)) for x in find_repeat(a, b)]
    if n < len(prefix):
        return prefix[n]
    return repeat[(n - len(prefix)) % len(repeat)]

repetitive = {"00": "0", "11": "2358134711", "14": "5914"}

def find(a, b, n):
    sequence = f"{a}{b}"
    while not sequence[-2:] in repetitive:
        sequence = f"{sequence}{sum(int(n) for n in sequence[-2:])}"
    length = len(sequence)
    if n >= length:
        sequence = repetitive[sequence[-2:]]
        n = (n - length) % len(sequence)
    return int(sequence[n])


def find(a,b,n):
    r = [a, b]
    if n > 300:
        n = n % 300
    while len(r) <= n:
        x = r[-2] + r[-1]
        if x > 9:
            r.extend([x // 10, x % 10])
        else:
            r.append(x)
    return r[n]

def find(a,b,n):
    str_ = str(a) + str(b)
    for i in range(11 + 20):
        str_ += str(int(str_[-2]) + int(str_[-1]))
        
    return int(str_[n])  if n < 33 else int(str_[(n - 13) % 20 + 13])

def find(a,b,n):
    if a==0 and b==0:
        return 0
    res=f"{a}{b}"
    while len(res)<=n:
        if "1123581347" in res or "1459" in res:
            break
        total=int(res[-2])+int(res[-1])
        res+=str(total)
    if not ("1123581347" in res or "1459" in res):
        return int(res[n])
    if "1123581347" in res:
        return int("1123581347"[(n-res.index("1123581347"))%10])
    return int("1459"[(n-res.index("1459"))%4])