# Prison Break

This challenge describes the following algorithm:

Start with a list of 10^7 zeros and for every line containing a,b,c separated by a space in the given file, add c modulo 10 to every number in your list between indices a and b (a included only).
Indices start at 1 in the list. At the end, compute the product modulo 999999937 of the nonzero digits in your list and you will obtain the password

In addition, we get a file called “Given_file.txt” that cointains 10^7 lines as described in the algorithm description.
If we try to solve this just by following the algorithm description, we will end up with a complexity of O(n^2) where n is the number of lines, which is 10^7. This yields a very long running time, so we better think about some other way.

In order to solve this problem in linear complexity we can do the following:

1. Generate an array X of 10^7 tuples – (0,0).
2. Traverse the input file and update X as follows: x[a] = (x[a] + c)%10
x[b] = (x[b] – c)%10
3. Compute the result by traversing X as follows:
   result = 1
cur = 0
for i in range(1, len(x)):
cur = (cur + x[i] + x[i]) % 10
if cur != 0:
result = (result * cur) % 999999937