1 00:00:25,439 --> 00:00:28,390 hi folks welcome back um so we will continue our discussion uh that we had um that we've been doing for the past few lectures um we first talked about time complexity and then we shifted gears to talk about space complexity um and we saw we had a couple of lectures on pspace uh kind of culminating in proving that there were languages which are piece based complete namely this tqbf language which is where we started and then we also proved that there are problems around involving games such as the generalized geography game where determining which side has a winning strategy is this case piece based complete at the end of the lecture uh last time we moved to a different regime of space namely from polynomial space down to log space and we introduced the classes l and nl and so i'm going to begin today's lecture by reviewing some of the material on lnl which i think came a little too quickly last time and then we have two important theorems we're going to cover today one is about proving that there are complete languages for nl um that has a bearing on the l versus nl question you know log space deterministic log space versus non-deterministic log space that's yet another unsolved problem in our field and so there's a notion of a complete problem from for nl and um then we're going to prove a theorem that was in its day very surprising to people i remember when it came out um in the 1980s um that nl in fact is closed under complementation that the nl class and cohen l class uh class uh both uh collapse uh to one that they're equal which is not the way we believe the situation to be for np but until someone has a proof that they're different uh strange things can happen okay um so with that i will um move myself to uh into the corner and uh let's do our review um so we are um in order to talk about space complexity classes that are smaller than n we had to introduce a new model which was the two tape model where there was a read-only tape that had the input on it um which you normally would think of something very large the whole internet or uh uh um you know something so big that you can't read it into your kind of your local memory um and uh then you have a worktop which is your your local memory and the way we're going to think about it in this uh in the context of log space is that that work tape is logarithmic in the size of the input and that is enough to have small counters or pointers into the input um because the reference location of the input is just needs you only need login bits to do that so we gave a couple of examples of the l and n of l and nl languages so this language of ww reverse as you may remember so here is an input um in ww reverse it's a string follow you know it's a palindromic string which is of even length and so you can make a machine in log space here that can test whether it's input is of that form and the work tape is only all it needs is a pointer into um or a couple of pointers that refer to the corresponding places of the input that you're looking at at the moment so you maybe look start out looking at the two outside a's and then the and then the this b symbols that are next to that and you can write down on your tape where you're looking currently and so that's going to be enough for you to you may have to zigzag of course back and forth a lot in order to do that test but that's completely fine um using the the model we're not going to be measuring time we're only going to be focusing on how much space we're using another example that we gave is the path language where you're given a graph and a start node and a target node and you want to know is there a path is there a path um this directed graph that goes from s to t and that's a language that's also that language is an nl in fact not known to be an l so the way that would look shifting to an input of uh in the path language you would have a graph represented say by a sequence of edges and a start and a target and the work tape would keep track of the current node um so the nondeterministic machine would guess a path that takes you from s to t node by node and the work tape would keep track of the current node okay so i hope you have this develop a little bit of an intuition for these classes l and n l we're going to be spending the the entire lecture today talking about that um okay um so as i mentioned the l and n l um problem is an unsolved problem and it's very much uh analogous to the p versus np problem except as i mentioned as we'll show that uh nl and its complement are end up being the same which is not something that seems to be the case for np that we don't know um uh can we think of this as a multi-head turing machine i'm getting a question about that which is i think you can um in fact that's an alternative way that people look at it you can think of it as having mult you know a head is basically needs log space uh uh to to store the location to to store um you know the the location of where that head would be so if you imagine having several different heads on the input tape you can think of a log space machine as being sort of a turing machine that has multiple heads on the input tape it's it's equivalent um good question uh so let's move on then um um okay so one of the things we proved last time was that uh anything that you can do in l you can also do in polynomial time um and i'll answer some of these uh chat questions in a minute but uh the [Music] um so the class l is a subset of p this is easy to prove but i think it's nevertheless important to see why it's true because it sort of sets some definitions of things that we're going to use later so in particular we really need to know the notion of a configuration of a log space machine on an input um so because the input is is it does not change we don't really consider the input to be part of the configuration the only thing that's the the thing that's relevant in the configuration is the dynamic part of the machine the state the head locations and and the work tape contents uh so we're defining that the mach configuration for the machine on a particular input w is those four things um state the two head locations and the tape contents and the important thing to keep in mind for this theorem is that we have only a polynomial number of different configurations if you just do the calculation uh the main part is the number of different tape contents as you can have which is exponential and log n and that's a polynomial and so therefore any machine that runs in log space provided it always holds and we always assume our machines always hold they can only run for a polynomial number of steps because that's as many different configurations as they have they ran for um say an exponential number of steps they would have to be repeating um configurations and then they would be loading okay um so um there we go um so okay so let me just get back so there's a somebody asked me a question which is harder p versus zen p or l versus n l you know completely no idea um uh it's a uh you know i guess there was a common line of thinking that um if you're gonna that it's good to try to think about if you're trying to separate classes you might as well take classes that are as far apart as one another um uh you know like if you're trying to prove if you're comparing p different from np and p different from p space maybe p different from p space might be easier because p and p space seem to be even further apart than p and np nobody knows and i suspect that there's something fundamental about computation that we just don't understand and then once somebody makes a breakthrough and solves one of those problems a lot of them are going to get solved in short order but again purely speculation um okay d what is d here d would be the size of the tape alphabet okay so this is the number of different tape contents we have good all right um so let's continue on another thing we mentioned kind of quickly in passing but still an important fact is that um savage's theorem works down to the level of log space same exact proof so that means that non-deterministic log space is contained in deterministic log squared space because that's that what savage's theory does for you it's it it converts non-deterministic machines are deterministic machines at the cost of a squaring in the amount of space you need um and so i'm not going to go through this in detail but the same picture that i copied off an earlier slide with a simple modification is that instead of um you know that i'm right down the the the size of the configuration is going to be now login because that's how big the configurations are when you have a non-deterministic log space machine and so simulating that so these are this would be what the um uh the tableau would look like for an nl machine um and then you can simulate that in the same way by you know trying all possible intermediates and then splitting it you know doing the top half and then the bottom half we're using the space of course recursively um the amount of space you're going to need is going to be enough to store for one level of the recursion uh one configuration and that's the order log space and then the number of levels of recursion is going to be another factor of log n because that's log to the running time which is going to be exponential and log n which or is polynomial so the total amount of space that you would need would be log squared space again this is sort of saying the proof of savage's theorem just over again um so if it's coming too fast for you just review the proof of savage's theorem and observe that it works even if the amount of space that the machine that the non-deterministic machine starts off with is log space all right um and uh last thing i'm going to be last thing in the category of a review is a uh our uh theorem that not only is all of l within p and that's kind of trivial kind of immediate you don't even have to change the machine if you have a log space machine for some language the very same machine is a polynomial time machine for that language because it can only be running for a polynomial amount of time but we have a non-deterministic gene for some language we're going to have to change it to become a deterministic machine that runs in polynomial time and so we're going to give a deterministic polynomial times simulation of a non-deterministic log space machine um and uh we kind of did this last time a little quickly so now if we have some non-deterministic log space machine so um m which decides a language a in in log space um we're going to show how to simulate that machine um with a deterministic polynomial time machine and the key idea which which is going to come up um uh in in a later theorem so good to understand it now not only here but to uh to understand it uh for uh for the next theorem that's coming is the notion of a configuration graph i was sort of thinking about calling it a computation graph but now on further reflection i think configuration graph maybe is the more suggestive term so let's stick with that um so configuration graph for a machine on an input is just a set of all configurations that the machine has all the possible different configurations um the machine can have with edges connecting configurations that correspond to legal moves of the machine so here's some configuration this is a snapshot of the machine at a moment in time here is some other configuration another snapshot of the machine at a moment in time and you're going to draw an edge between ci and cj if cj could follow in one step from ci and you could tell by just looking at the configurations whether that could be possible obviously the head has to be one place over in cj from where it was in ci and it has to be updated according to the rules of the machine so you can tell whether um you know you so you you could fill out this graph you could write down all the possible configurations and you can put the edges down now the point is that when we have a log space machine we don't have too many config possible configurations there's only a polynomial number so the size of this whole graph is polynomial so our polynomial time simulation is going to write down that entire configuration graph of the log space machine on its input there are many configurations that can be only polynomially many so you can write down all those configurations as the nodes and then go look at each pair of nodes whether this configuration could lead to that configuration according to you know it's a non-deterministic machine so a configuration could go to several different loc you know there could be several different ways to go but those are just several different outgoing edges from a particular node in this graph representing the configuration which might have several different legal successors in the non-deterministic computation okay now the important thing here is that m accepts its input w exactly when there is a path this configuration graph that takes you from the start configuration to the accept configuration and as i mentioned let's assume as we've been doing that the machine i should have put it here but i didn't but the the machine um when it is about to accept it erases its work tape and moves both of its head to the home position at the left end of the tape so there's just one accepting configuration you have to worry about it just makes life simpler um so there's going to be a start configuration a single accept configuration in this configuration graph and now there's going to be a path indicated here that connects the start configuration to the accept configuration if and only if m accepts w because that path is the sequence of configurations that the machine would go through if you launched it on w it would start at the start and there might be several different ways to go but if there is one of them that leads you to an accept that's going to correspond to a branch of the computation that's accepting okay so that's tells us what the polynomial time algorithm is it says you on input w you you construct that configuration graph for m on w g sub mw and you test whether there's a path from c star to c except using any polynomial time um you know depth first searched or breadth first search you know um algorithm for testing whether there's a connection passed in a graph and if there is such a path you accept because that means the machine m accepted and if there was no path you reject because then m uh must have not accepted and therefore you have a uh polynomial time simulation of your non-deterministic log space machine m okay how are we doing okay so that tells us that nl is contained within p and also l is contained with an nl as before so we have kind of a this hierarchy of classes um now you can even talk about not only is l different from n l even as l different from p is it possible that anything that you can do in polynomial time you can do a lot of space don't know open question okay i'm getting a very good question here just now why is this construction taking log space it doesn't this instruction takes polynomial time this can this algorithm here is not a polynomial this is not a log space algorithm that i'm giving you i'm giving a polynomial time algorithm for stimulating a non-deterministic log space machine now later on you know i don't want to confuse the issue right now for this particular slide all i need to do is construct that graph in polynomial time it's a you know it's a polynomial size graph i can't store that whole graph in a log space memory okay so question here um [Music] you know we can see that listing out to the nodes and edges would be polynomial time but how do we actually provide structure to this graph representation i don't even know what that means so if you can clarify that for me then maybe i can try to answer it but you know a graph is just a list of nodes and a list of edges after that we know what the graph is i mean you know you may like a picture but the machine doesn't need a picture um you know our definition of you know we we just represent these things as um uh and in the end so please clarify if you want me to i'll try to i'll answer it at the next at the next pause um i'm grateful for all the questions because i'm sure any question that any of you have another 20 of you also have so it's um questions are good uh don't don't don't be bashful um and also ask the tas if i could become overloaded um okay now we're going to shift gears into some new material all right um we're going to talk about the notion that uh sort of thinking about analogous to the p versus np problem where there were these np complete problems now we have the l versus nl problem there are going to be nl complete problems and that kind of capture the essence of nl the way np complete problems capture the essence of np in a sense and that all other problems in np are reducible to them so they're kind of like the hardest np problems here we're going to have exactly analogous situation for nl um where we're going to uh show problems where all other nl problems are reducible to them so if you can kind of solve one of them like solve one of these nl complete problems in log space deterministically then you solve all of nl problems in log space deterministically so um it's a very similar looking definition to what we had before uh it's an l complete if it's in nl and then all other languages in nl should be reducible but now we have a new notion here um with an l instead of a p now before when we talked about np completeness we had polynomial time reducibility that's not going to work anymore because if you remember nl is a subset of p so all nl languages are polynomial are our languages in p and if we're talking about if we use polynomial time reducibility all languages and p are reducible to each other we need to have a notion of reducibility which is kind of weaker than the class um and so uh polynomial time reducibility just would not work here because everything would become nl complete because everything is introducible to each other so we need to have a weaker notion we're going to use log space reducibility which we have to define [Music] so here for that we're going to have to talk about the notion of a function that you can compute in log space okay and it's a little tricky here just like when we talked about language recognition in log space where we had the work tape had to be smaller than the input tape because the inputs can be large the work area is small now the output also could be large relative to the work area so we're going to have a three tape model where there's the input is going to be a read only the output is a write only it's like a printer it's something you can only write on but you can't read back because otherwise you can cheat by using the output as a kind of storage and then you have your storage area which is your your read write work tape okay so this would call this you know the traditional name of this is a log space transducer so it you know it converts inputs to outputs but uses only log space for its working memory okay so the input tape has stores in bit and symbols the work tape stores log n symbols order login symbols and then we have the output tape i mean you want to think about how big can they there's going to be a check in coming to kind of uh ask you how big could the memory could the output be but that also will save that for the end if you can mult that over if you're uh want to think ahead okay um [Music] so we think of a log space transducer as computing a function which is just a mapping from the input to the output that the transducer provides for you a transducer transducer is a deterministic machine by the way so you take the transducer you give it a w and you turn it on and then it out holds with f of w on its output tape that's what it means to be computing the function f okay and we'll say that a is log space reducible to b using the l subscript symbol on the less than or equal to sign if it's mapping reducible to b but by a reduction function that's computable in log space just the same way we defined polynomial time reducibility but there we insisted that the reduction function was computable in polynomial time um okay just quickly i got a question again uh you know why why log space here because polynomial time would be too powerful for doing reductions uh internal to p every language in p is reducible to every other language in p and so everything in nl would be reducible to everything else in l with a polynomial time reducibility and so that would not be an interesting notion we have to use a weaker notion than that a weaker kind of reduction um using a weaker model so that you don't get the otherwise the the the re reduction function would be able to answer whether um you know it would be able to solve the problem a itself if we had a polynomial time reduction and we're mapping things from logs in you know nl to other problems in nl the reduction would solve the problem that's not what you want the reduction should be constrained only to be able to do simple transformations on the uh on the problem not to solve the problem anyway you have to look at that you know this is an issue that's come up before when we talked about um what's the right notion of reduction to use for piece based completeness same exact discussion okay now there is an issue here though uh that we have to be careful of when we have a being log space reducible to b and b and l then what you want um [Music] uh if if a is log space reducible to b and b and l then you want a to be in l that's the same pattern we've always had for reductions if a is reducible to b and b is easy then a is easy so here in the notion of easy as being an l um now if you remember the proof of that that we had from before which i'll just put out for you is that um to show a log space solver for a um uh you take an input w and now if a is reducible to b you do compute the reduction and then you run the decider for b um so if we're assuming a is reducible to b and b is in l so b has a log space decider you you take your w which you want to know is it in a you map it over to the b a b problem using the reduction function and then you solve it using the decider for b and you give the same answer now this actually doesn't work anymore it doesn't work in an obvious way because if you if you're following me i hope you most of you are um there is a there is a problem here which because we're trying to give a a log space algorithm for a and that algorithm is going to be computing this reduction function mapping w to f of w f of w might itself be very large as this picture suggests here you may not be able to store f of w in the log space memory for the machine that's deciding any so this is an obstacle that we need to solve in order to prove this theorem which we need because that's the whole justification for doing these reducibilities um should be a familiar looking kind of line to what we've seen before uh so we don't have space to store f of w what do we do and and i'll also mention that this is going to be relevant to one of your homework problems so what do we do we don't have space to store the intermediate result that we need in order to solve the problem you know we started with w now we need to test if f of w is in b that can run in log space but just simply getting your hands on f w how do you what do you do about that um so what we're going to do is the following is the decider um the the decider for b which needs f of w um because it's deciding if f of w is in b um it doesn't need all of f w sitting there in front of it all at once if you think about how the turing machine operates on its input it only looks at one symbol at a time you know it starts out reading the left foremost symbol of f w then maybe he moves his head right moves the second symbol of f of w then the third symbol of f of w maybe gets up to the uh tenth symbol of f w maybe it moves his head back and goes to the ninth symbol in the eighth symbol but the turing machine's head you know which is deciding b only looks at one symbol of f of w at a time uh so instead of writing down all of f w the idea is that we are going to compute the individual symbols of f of w that we need only at the moment we need them so if the decider for b [Music] is reading the tenth symbol of f w we fire up um the transducer on w and as it's writing out its output which we don't have space to store anymore we throw away all of the output values until we get to the tenth one and then we said ah the tenth one is whatever is a c whatever the value is now we feed that into the uh decider for b we can now simulate that decider for one more step now the decider says now i need the 11th um symbol of f w okay now we can run the run the machine for one more place um but if it needs but we don't even have to do it if you know we the i think the better way to think about it is every time that decider for b needs another symbol we start the transducer over again and just keep throw away everything except for that one symbol output that we that we need so every time we do another step of simulating b we're going to have to re-run the transducer from the beginning just to recompute that or compute maybe for the first time or recomputed if we need it subsequently this is going to be slow but we don't care um to uh recompute that that symbol that that the uh simulator that the decider for b uh requires okay so i'm saying that over here recompute the symbols of f of w as needed okay so let me let's take a couple of questions and then we're going to move to a check-in so so somebody's asking why we why did we have to introduce transducer for log space reducibility when we didn't do it for polynomial time reducibility we could have for polynomial time reducibility but we didn't need to because we could just all do it on the same tape the problem is for log space the tape is the work tape is too small to hold the input on the output so we can't um you know since we're only working we have a log n bound that we have to work within uh we need to uh separate those functions from the work functions the input function and the output function in the case if we had if we have more than um you know the amount of resource we have either time or space was at least n then we could just lump them all together and have that one tape do multi you know uh multiple functions um and somebody's asking me here yeah this is mapping reducibility this m this is what we from the notion we saw before okay um does f of w lie on the input tape of b well yes so we are good question so f of w you know because what are we doing we're trying to find a decider for a here using the decider for b and the and the mapping from a to b um the reduction from a to b so the decider for b expects to find its input on an input tape um that input is going to be f of w but but you know we have to get the effect of that without actually writing down that input tape because we don't have enough room to write down the input tape for the decider for the b decider because that could be very large and we we only have we have no place to put the f of w to think about what's going on here we're making a log space machine whose input is w has to compute f of w as an intermediate value to feed it into the beta side that is not going to be possible to hold on to that whole f of w at one to altogether because it's too big but that doesn't mean we don't need it we only need one symbol at a time which we can recompute um okay so let's see um so somebody says can we just ensure that the output tape is order n so we don't need more tape than the input order n is still going to be too big where you're going to put that output even if it's or just order n first of all no the answer is no we can't because there are going to be reductions which are bigger than that but the other question is if you know can we just ensure that the output is order n you can't put the output on the input tape the input tape is read only the output tape is right only so there's no place to just even if the output is just as big as the input it doesn't help you if the output is only log in okay then we could do it but that's not going to be interesting for us the obvious the you know you're going to need for these log space reductions big outputs um as we'll see in a minute uh what's the running time for this log space reduction it's all going to be polynomial it's all going to be a log space algorithm so it's all going to be polynomial um is there any np completeness reduction which can be done in log space all of the np com all typical np completeness reductions those polynomial time reductions they all can be done in log space because they are reductions tend to be very simple transformations and log space is going to be enough to do all of them um okay uh i can't answer the second part of that too that's too complicated and i think we should move on um so um let's let's look at the first check in here uh so if we have a log space transducer that computes f and if you defeated inputs of length n how how big can the outputs be actually um so what you think about that and give me an answer i'll give you a minute uh to answer this question oh this is a tough one these are this is i i i let me just say up front there are i i struggle with this lecture because some especially the stuff in the second half it's kind of hard it's i wouldn't say it's it's technical but conceptually i think some of the material is is is a little harder maybe in part because people are not used to thinking about um memory complexity or space complexity even though i don't see why i mean i think it's an important resource to be considering but i think it's less common and i think there's some um discomfort with that okay the so we're just about done here um five more seconds please all right about to wrap wrap the chicken oh one two three all right so yes the correct answer is c um as i mentioned uh you know we're going to want to have outputs that are larger than log n and there's no reason why they wouldn't be able to be larger than log n according to the definition that i gave you gave you there's no bound on the output we're only measuring the the run the running space of this algorithm in terms of its um work tape the input and output tapes don't count so they could be more than log n they can be more than n polynomial is the right answer why because a log space transducer um if you just ignore the output it's just an ordinary log space machine and i know it can only run for a polynomial number of steps without an end up going into a loop the same argument that we gave for that before applies here as well um so if it's going to exceed a polynomial number of steps it's never going to hold and so that's going to be not allow it it's got a halt with the output on the output tape and so that it'll be disqualified as a as a log space transducer if it doesn't uh if it doesn't hold so it can't be anything longer than polynomial it's a good thing to think about to understand okay so let's continue um so we're going to show that the path problem is nl-complete now we had we defined nl completeness and we've we've seen the path problem before um and we're now going to show that path occupies that very special position for nl namely that it's an ml complete problem um so if you can solve the path problem deterministically in log space you have gotten a big result who knows how to do that and it would it would collapse all of n l down to path down to log space if you could do path in log space deterministically um okay so let's see why that is so first of all the two components of being complete are being in the language and the reduction part so in the language we've shown already uh now we want to show that for any language other language in nl it's going to be log space reducible to path in a certain sense this may not feel so surprising thinking back to our proof that nl is in uh is a subset of p because we managed to convert any nl machine and any the running of any l machine to a path problem that the the polynomial time machine then solved um and so it's really the same idea that says that path really captures any you know any um uh any and any nl machine you know the computation of any nl machine really can be seen as a path problem um where the nodes are the configurations of the machine um so let's just see how let me just try to go through that if that wasn't super clear which i'm not sure it was um so suppose we have a machine decided by a language decided by non-deterministic you know an nl machine and non-deterministic machine in log space um again i should have put this before but we're going to modify m to erase its work tape and move its head to the left and on accepting so um it has a unique accepting configuration um now i'm going to give the log space reduction that maps our language a which is in nl to the path language so thinking about what that means i'm going to take an input w which may or may not be an a and produce for you a graph with a start and target node starting targeted nodes um where w is going to be in the language if and only if g has a path from s to t and what do you think that graph is going to be that's going to be the configuration graph for the machine that decides a okay so um [Music] that is uh how it's going to look so here maybe here's a picture right so f of w where w again is your problem about membership in a is going to become a pr a problem about membership and path and it's just going to be the configuration graph for m on w um now what's left is to show that we can do this conversion in with a log space transducer so it's a log space computable reduction um so let's just try to go through that quickly um it's not conceptually not super hard um [Music] so here's our transducer let's just think about what it needs to do it needs to take an input w and convert that f of w to this thing here the computation graph of m on w the configuration graph m on w the start and except configuration so that's going to look like this down here that's what we want to eventually appear on the output tape [Music] so the way we're going to achieve that we all only have a small log space order log space work tape and the way we're going to be able to produce this output is you know the the configuration graph it's just a series of edges which are say you can go from this configuration to that configuration in one step so what we're going to do is on our work tape we're going to go through all possible pairs of configurations again just in some like odometer order just by looking at all possible strings really of length order log n that are big enough to represent two configurations every once in a while it's going to be actually a pair of configurations at that point we look at those two configurations look at m and see can this configuration go to that configuration if yes you print it out on the output if no you just move on to the next pair of configurations so it's not and then at the end you write down the start and accept configurations so i've i've indicated that here here is the transducer it says on input w for all pairs of configurations that now this is getting written down on the right work tape you output those pairs which are legal moves for m and then finally i'll put the starting accept that's it so let's just see let me take any questions here um why do we need special except state for m well we want to have i think you mean accepting configuration i just want to have this i don't want to have a multiplicity of different possible accepting configurations because then it's not really a path problem then it becomes a question of can i get from the start to one of those accepting you know nodes representing accepting configurations that's a little messy i can fix it but the simplest fix is just to make there be a single accepting configuration um well why do i output starting except at the end of the output tape that's the way i write down my path problem it's a graph followed by a start node and a target node so that's i have to follow that form that's oh i'm not sure what you're asking you want me that you want me to put that first i'm not sure what the or or why at all because it has to be a um you know here it is here's the output i'm looking for um okay do the three do the read write work tape here store pointers to configuration or some sort of counter no they store the actual configuration the configuration for m is just think about what it is it's a log space size object it's an it's a tape for m it's a location of its heads and it stayed so you're just gonna write down that stuff over right over here on the left side of this uh this left slot and on the right slide you're gonna write another configuration for m on w um and um you're going to just then put the edges in accordingly okay so somebody did that help you know some again is asking why is the configuration on the log space it's just a tape it's a log space tape that's the main thing in the configuration of the tape um on the read white work tape do we have do we only write two configurations at once yeah we're just writing down a candidate edge that we're going to output onto the output tape so that's why we have two configurations i want to know can i get from this configuration to that configuration if yes i print it out print out that pair that's an edge in my config my my configuration graph which is what i'm supposed to be outputting here can there be mo okay when we move on again direct questions to our tas who are uh would be more than happy to help you uh and we will let me just quickly give i'm a little running a little tight here time wise but let's just see um here's an example of showing some other problem is nl complete you have a homework problem on that so i thought i want to give you an example maybe we can just defer this to the recitation if so maybe we'll try to do this a little quickly um to save us some time but the two-set problem which is just like the three sad problem except with two literals per clause curiously the complement of that problem so the unsatisfiable problem um uh formulas that form an nl complete language um and so first of all you have to show it's in nl we're not going to do that it's a nice exercise it's not totally trivial to do um but it it's i you might want to try that um we're going to show that path is reducible to the complement of two set we've got to give a reduction that gives converts graphs to formulas where there is a path now when the formula is unsatisfied and that um what's going to happen is the path is going to correspond to a sequence of implications in the formula which yields a contradiction and forces it to be unsatisfiable again this is going to come a little fast but um and then you know maybe we can discuss that over the break which is next so every node in g is going to have associated variable in the formula so there's a variable for every one of the nodes for every edge there's going to be a clause of implication connecting those two associated nodes so if there's an edge from u to v then there's going to be an implication in the formula that says uh if x u is true then x v is true um and note that that's equivalent to the more conventional ways xu complement or xv these are logically equivalent so i'm not cheating you here in terms of being a two sat problem they really just look like this and lastly i'm going to put uh two additional clauses it's a x for the start variable um from the start node s here s uh i want i want to force that one to be true so it's x since i want to have two exactly two per clause as xs or xs so that forces x that that variable true and similarly and and lastly if t is true that's going to force um the the the if x t is true that's going to force x s to be false so now if there's actually a path in the graph that goes from s to t there's going to be a sequence of implications starting out with s being true forcing other things being true including forcing t to be true which then forces s to be false and that's our contradiction which shows that the formula cannot be satisfied um so now you have to prove that this works um as i said you can for the forward direction if there is a path you follow the implications to get a contradiction for the reverse let me not uh spend time here you can i'll leave this to you to think about offline um but if there is no path there is a way of assigning the variables to true and false to make a satisfying assignment to the formula so that gives the other direction okay um so and you can show it's computable in log space that's very simple because a very simple transformation there okay so uh i think we're gonna move on to the break um and uh i'm happy to take questions at this point about this does the configuration going back include the input no the configuration does not i mean as i said the configuration for m on w is the state the head positions and the work tape contents not the input tape because then you would be it's not there for a reason the input is huge um but you don't need the input there because the input is going to be constant for everybody everybody can look at that input which is a fixed uh sort of external thing um uh somebody's asking me are there any np complete problems in [Music] there are definitely np complete theories some i don't i don't know um uh there are some problems in number three where it's you know like factoring where we don't know the status somewhere between p and np um you know it's formulated as a language of course but uh there are problems in um solving certain kinds of uh equations uh low degree equations um that that uh i don't remember now exactly those are actually known to be np-complete um now us but nl-completa i don't know if they're nl-complete number theory problems oh good question somebody's asking me does nl also have an alternative definition using certificates or witnesses yeah um yes sort of um for nl you can make a certificate which is again polynomial size certificate but it has to be you're only allowed to read it with a one-way head so it's like a one-way one-way certificate um so it had to be you can only process it in a certain way that's that's a nice exercise actually itself um but anyway let us uh we are now um johnny um and we're going to move back we're going to continue so everybody return uh this is um what's next on the agenda proving that nl equals cohen l this is a hard proof um i'm going to try to break it down as much as i can and let's hope you you get i i hope you i hope you get it uh i'll try to be as helpful as i can as i can okay um but if you if you're finding it tough you won't be alone so um first of all we're going to show the way we're going to solve this is by showing that the complement of path is solvable in n in nl because the complement of path is just as path is complete for nl the complement is complete for co and l um and so by doing that problem in nl we're going to reduce all of co all of cohen l will be reducible to problems in n l and so therefore will be n n l colon l will be then inside n l and then uh n l is going to be equal to coin um if that sequence of logical connections um uh is not clear don't worry the point is is that we want go back and figure out why that's enough later but what this means is we want to give a non-deterministic machine which will accept when there is no path from s to t okay and and please don't say why don't we just take the machine for path and flip the answer you can't do that with a non-deterministic machine um so you better if you're thinking that that's allowed go back and review non-determinism um so you want to make a non-deterministic machine which is going to accept when there's no path so some branch is going to make a sequence of guesses and it has to be sure that there's no path and then it's going to be um and then it can accept when there's no path now if you can find a way of like making a separator something that cuts the graph in half and separates s from t then you would be good um the only problem is um there's no um there's no obvious way of doing that because those kind of separators even if they were probably too big to write down in um in log space so i'm going to give you a completely different way of doing it and um i'm going to make this is a little different presentation than what's in the book i think hopefully this is a little longer and therefore a little clearer um we'll see uh so first of all i'm going to define a notion of a non-deterministic machine computing a function and that's a simple idea what you want is on the different branches so you have some function f which has for every w there's a output f of w um and what and the non-deterministic machine can operate that on all of its branches it's allowed to either give f of w or say reject mean punt this is or say i don't know so every branch has to give the right f the right answer so all the all the branches that give an answer have to agree because there's only one right answer all the branches that give an answer have to give the right answer or they can say i don't know um the only thing is you have to also say that at least one of the branches actually gives an answer so somebody doesn't cannot reject somebody cannot say i don't know um so at least one of the branches gives an answer and gives the gives the answer and all the other branches can either give the answer or they can say they can just reject okay um but there's no notion of accepting there's just an accept notion of this non-deterministic machine on some branches giving the output value and other branches just punting and saying reject maybe reject is the wrong word i could just say punt um [Music] all right uh so we're going to be talking about functions that you can compute with um non-deterministic machines with nl machines uh in particular all right so we're going to look at this path language this path function now now this is not exactly the same as the path language this is a function here written with lowercase so given a graph s and t i'm going to say yes if there is a path and no if there's no path and this is a function now which is going to output yes or no not a language um this is a function it's very closely related i understand you know so if you can solve the function you can do the language um but what we're going to give is a nl machine a non-deterministic machine which is going to compute this function and therefore you can use that to do the path language two important things for us is here if g is some graph and here's the starting node s um r is all of the nodes that you can reach from s this is a this is a some uh collection of nodes and c which stands for count is the number of reachable nodes so i've written it down here more if you like it more formally uh r is the number is the collection of nodes for where the from for which there's a path from s to that node and c is the size of r so this you have to understand these two because we're going to be playing with this for the next three slides okay now first of all this is kind of a little bit of an exercise theorem but it's still going to be a useful fact that we're going to end up needing later but it's also a little bit of just to test your understanding suppose there's some nl machine which computes this path function so um you know on the different branches of the non-determinism given you know a graph a g s and t there are going to be some branches which may output yes or some branches that may open no and other branches may say i don't know but the machine always has to give the right answer if it's going to give any answer so all branches either have to say yes or all branches all branches have to say yes or punt or all branches have to say no or punt because one of those answers is going to be the right answer um so suppose i have a way of computing path by an nl machine then can i also compute can i make some other nl machine which computes the count of the number of reached uh the number of nodes reachable so if i can test if a node is reachable can i figure out how many nodes are reachable this is supposed to be easy this is kind of a little bit of a practice um so if i can figure out if nodes are reachable yes or no then i can say figure out how many nodes are reachable you just go through them one by one testing if they're reachable and count the ones that are that's the only that's that's all i have in mind so start with a counter that's set to zero initially and go through each of the nodes of g one by one and i use my nl machine that computes path that's what i mean by this part um so i test if um the nl machine says yes there is a path then i increase the counter and if it says there's no path then i just continue without increasing the count now when i'm running my nl machine to calculate this compute this function that nl machine might punt might reject sometimes on some branches that's okay you know i'm i'm also allowed i'm also an nl machine i'm computing a value um and i also might punt on some uh branches uh so at the end i'm gonna output that count okay so what i'm gonna prove next is the converse of this and that's and that's the magical hard part that if i can compute the count then i can com then i can do the test uh of whether um uh individual nodes are uh connected have a path from s um okay so let's just see somebody's asking in non-deterministic machines uh so you know like m is not allowed to loop no if a machine if any one of these machines like an nl machine loops it's going to be going forever that's not allowed so no looping um i'm sure that's relevant but no lu no looping but i'm more worried is that you understand this uh theorem here um i think we have a check incoming let's let's see okay this might be helpful so consider the statement that path complement is in l that's what we're trying to prove and also that some nl machine can compute the path function these are going to be related facts which one can we prove from the other easily i mean they're both going to be true so in some sense it's trivial but i want to know which one can we prove kind of immediately without doing much work that i can solve this path problem in nl the complement of the path problem in an l or that i can compute the path function in analysis so what do you think um [Music] okay um almost done here yeah ending uh you guys didn't do well [Laughter] that's okay uh the actually the right answer is c um most of you got that if i can solve the path function sorry the yes no value i can use that now to solve both path and path complement that you know uh that's seems more clear-cut but suppose i can solve the path complement problem in an nl and i can also i also know i can solve the path problem in nl that that we've already shown um so knowing both of those um you know if i given a g s and t what i can do is not deterministically pick which of those two directions you know i pick i'm going to guess well uh it's in path or it's in the complement of path so there are two different non-deterministic ways to go one of those is going to always end up rejecting um and so that's going to end up hunting the other direction is going to sometimes end up accepting and sometimes punting and based upon whether which side is ends up one or the other is going to have some except um is going to be accepting and so the one that's accepting is going to tell me whether to answer yes or no so actually both directions um both implications follow pretty easily um okay anyway let's see let's try uh to show this is this is the hard part uh and we have five minutes let's see how far we can get um so this theorem works by magic so uh you know it kind of blew everybody's mind when it was first came out so let's just see it's really not that hard but it's sort of it's kind of twisted um so suppose there some machine can compute c the count the number reachable from s i'm going to use that to solve path um the path function to test yes i can but yes if there is a path or no there is no path for each node so if i know how many nodes are reachable then i can solve now for individual nodes which is strange that you can do that now i'm not telling you how to compute c that's for later which i probably won't get to but just imagine pretend we can somehow figure out what the count is of the number of reachable nodes okay so here is my uh non-deterministic algorithm for computing path first i'm going to compute c or let's say c is given and now maybe the best thing to do is to try to give you the idea up front um what we're going to do since we're a little short on time what we're going to do is suppose i tell you there are in this graph a hundred nodes reachable from s so c is a hundred there's a hundred reachable nodes now i wanna know i say well i i i i don't really that's all very nice but i'd like to know this particular node t is that reachable from x now you're i'm a non-deterministic machine now if t was reachable then i'd be fine because non-deterministically i don't even care about the hundred i take and non-deterministically on some branch starting from s i'm gonna hit t and that branch is gonna say yes the other branches maybe they'll punt but some branches are going to get the right answer the problem is suppose t is not reachable then you want some branches to say no and how could that branch ever say no unless it's sure that t is not reachable and how can one branch be sure the idea is this suppose i know that there are a hundred reachable nodes what i'm what what i'm going to do non-deterministically is i'm going to guess those hundred nodes one by one can't keep you can't store them all because it could be a hundred could be a big number uh i'm gonna guess them one by one i'm gonna guess them and every time i guess a note i'm going to prove it's reachable by guessing the path that shows it's reachable so i'm going to guess 100 nodes prove that they're reachable and then see is was t one of those reachable notes if it was well and then i would have found it and i would notice a yes but if t was not one of the hundred reachable nodes and i know there's only a hundred so if t is not one of those nodes and i in other words if i found them all and t wasn't one of them then i know it's not reachable and that's how using the count i can be sure that certain nodes are not reachable because i just find all the ones that are prove that they are check that the count agrees with what i was given and then say no t is not reachable if it's not one of those nodes that i've found you know to be reachable which adds up to my given count that's the whole idea of course how do you get the count oddly enough it just it's really it's kind of the same idea repeat it over and over again but uh i guess we'll have to do that next time so let's just write this down and we'll kind of uh use that as the beginning of uh thursday's lecture um so we're going to go through each node u one by one we're now gonna guess for each node whether there's a path to it or not so i'm gonna call it either p or n um again this is now think about my 100 nodes i'm going to be guessing all 100 nodes uh i'm going to nondeterministically pick a path um from that node that i guessed is reachable so if i guess a node there is a path i'm going to confirm there's a path by non-deterministically picking it if i don't find that path i just reject punt on that on that on that branch if that path that i found actually led me to t that so you that node that i'm working on is currently t then i know to accept but otherwise i'm just going to count the number of nodes that i find are reachable um if i've guessed that u is not reachable i'm just going to skip it um at the end i see whether the number of nodes that i've determined are reachable agrees with my original count c so does k equal c or not if it doesn't equal they're not equal then i didn't find all the reachable nodes i didn't guess right and so i punt i say well i bad branch of the non-determinism i i just give up but some branch of the non-determinism is going to guess all of the correct nodes which are reachable and then if t hadn't been found already to be one of them at this point i know t is not reachable and so i cannot put no okay um so that's that's the that's the whole thing um what is m m is the good question m is the number of nodes of the graph i should have said that so you don't want to go to you don't want to get into a loop um so you better cut off your picking of a path uh to some cutoff value so you're going to cut it off at m which is the number of nodes which is longer going to be long enough actually that uh we're going to play with that in a bit later but um okay let's just see how do i know i did not visit the same node twice when counting because i'm just going to go through all of the nodes in some order you know to pick any order you know the the nodes appear in some order in the uh representation of the graph on the input you know but so in the old order i'm just going to go through the nodes in order therefore i'm never going to see the same node twice um what does step four mean um so yeah step four is i'm standing for means i'm for each node i'm guessing that that node is either um has a path to it from s or does not have a path to it from s um so you know kind of thinking about it the original we're at a time so why don't i um you know i'm happy to discuss this um in the office hours i'm just going to skip over the rest of the slides here um and review like we have a missing check in uh my choice let's just uh i want to make sure everybody's got uh all their check-ins here so why don't we just uh if we know nl is equal to coin l we also we show to sat complement is nl-complete it also then follows that two stat itself is in l complete because n l equals common l so i'm going to give you the answer to this just because i want to want you all to uh finish this poll still some of you are getting wrong uh okay uh so please answer it quick and then we're gonna end are we all done get your participation points here three seconds okay ending okay um doesn't matter so here we we ran over sorry about that quick review this is what we didn't quite finish as part five but we'll finish that next time okay when showing path is nl complete we also need to list the nodes for constructing the graph the slides only mention edges yeah i kind of skipped that but yeah you can just write down all the nodes um again but that's also going to just take log space as you as you observe yeah technically when you're writing down a graph you write down a list of the nodes and you write down a list of the edges i kind of skipped writing down the nodes but yeah it's the same doesn't matter so i'm going to say goodbye to you all thank you you 2 00:00:28,390 --> 00:00:28,400 hi folks welcome back um so we will continue our discussion uh that we had um that we've been doing for the past few lectures um we first talked about time complexity and then we shifted gears to talk about space complexity um and we saw we had a couple of lectures on pspace uh kind of culminating in proving that there were languages which are piece based complete namely this tqbf language which is where we started and then we also proved that there are problems around involving games such as the generalized geography game where determining which side has a winning strategy is this case piece based complete at the end of the lecture uh last time we moved to a different regime of space namely from polynomial space down to log space and we introduced the classes l and nl and so i'm going to begin today's lecture by reviewing some of the material on lnl which i think came a little too quickly last time and then we have two important theorems we're going to cover today one is about proving that there are complete languages for nl um that has a bearing on the l versus nl question you know log space deterministic log space versus non-deterministic log space that's yet another unsolved problem in our field and so there's a notion of a complete problem from for nl and um then we're going to prove a theorem that was in its day very surprising to people i remember when it came out um in the 1980s um that nl in fact is closed under complementation that the nl class and cohen l class uh class uh both uh collapse uh to one that they're equal which is not the way we believe the situation to be for np but until someone has a proof that they're different uh strange things can happen okay um so with that i will um move myself to uh into the corner and uh let's do our review um so we are um in order to talk about space complexity classes that are smaller than n we had to introduce a new model which was the two tape model where there was a read-only tape that had the input on it um which you normally would think of something very large the whole internet or uh uh um you know something so big that you can't read it into your kind of your local memory um and uh then you have a worktop which is your your local memory and the way we're going to think about it in this uh in the context of log space is that that work tape is logarithmic in the size of the input and that is enough to have small counters or pointers into the input um because the reference location of the input is just needs you only need login bits to do that so we gave a couple of examples of the l and n of l and nl languages so this language of ww reverse as you may remember so here is an input um in ww reverse it's a string follow you know it's a palindromic string which is of even length and so you can make a machine in log space here that can test whether it's input is of that form and the work tape is only all it needs is a pointer into um or a couple of pointers that refer to the corresponding places of the input that you're looking at at the moment so you maybe look start out looking at the two outside a's and then the and then the this b symbols that are next to that and you can write down on your tape where you're looking currently and so that's going to be enough for you to you may have to zigzag of course back and forth a lot in order to do that test but that's completely fine um using the the model we're not going to be measuring time we're only going to be focusing on how much space we're using another example that we gave is the path language where you're given a graph and a start node and a target node and you want to know is there a path is there a path um this directed graph that goes from s to t and that's a language that's also that language is an nl in fact not known to be an l so the way that would look shifting to an input of uh in the path language you would have a graph represented say by a sequence of edges and a start and a target and the work tape would keep track of the current node um so the nondeterministic machine would guess a path that takes you from s to t node by node and the work tape would keep track of the current node okay so i hope you have this develop a little bit of an intuition for these classes l and n l we're going to be spending the the entire lecture today talking about that um okay um so as i mentioned the l and n l um problem is an unsolved problem and it's very much uh analogous to the p versus np problem except as i mentioned as we'll show that uh nl and its complement are end up being the same which is not something that seems to be the case for np that we don't know um uh can we think of this as a multi-head turing machine i'm getting a question about that which is i think you can um in fact that's an alternative way that people look at it you can think of it as having mult you know a head is basically needs log space uh uh to to store the location to to store um you know the the location of where that head would be so if you imagine having several different heads on the input tape you can think of a log space machine as being sort of a turing machine that has multiple heads on the input tape it's it's equivalent um good question uh so let's move on then um um okay so one of the things we proved last time was that uh anything that you can do in l you can also do in polynomial time um and i'll answer some of these uh chat questions in a minute but uh the [Music] um so the class l is a subset of p this is easy to prove but i think it's nevertheless important to see why it's true because it sort of sets some definitions of things that we're going to use later so in particular we really need to know the notion of a configuration of a log space machine on an input um so because the input is is it does not change we don't really consider the input to be part of the configuration the only thing that's the the thing that's relevant in the configuration is the dynamic part of the machine the state the head locations and and the work tape contents uh so we're defining that the mach configuration for the machine on a particular input w is those four things um state the two head locations and the tape contents and the important thing to keep in mind for this theorem is that we have only a polynomial number of different configurations if you just do the calculation uh the main part is the number of different tape contents as you can have which is exponential and log n and that's a polynomial and so therefore any machine that runs in log space provided it always holds and we always assume our machines always hold they can only run for a polynomial number of steps because that's as many different configurations as they have they ran for um say an exponential number of steps they would have to be repeating um configurations and then they would be loading okay um so um there we go um so okay so let me just get back so there's a somebody asked me a question which is harder p versus zen p or l versus n l you know completely no idea um uh it's a uh you know i guess there was a common line of thinking that um if you're gonna that it's good to try to think about if you're trying to separate classes you might as well take classes that are as far apart as one another um uh you know like if you're trying to prove if you're comparing p different from np and p different from p space maybe p different from p space might be easier because p and p space seem to be even further apart than p and np nobody knows and i suspect that there's something fundamental about computation that we just don't understand and then once somebody makes a breakthrough and solves one of those problems a lot of them are going to get solved in short order but again purely speculation um okay d what is d here d would be the size of the tape alphabet okay so this is the number of different tape contents we have good all right um so let's continue on another thing we mentioned kind of quickly in passing but still an important fact is that um savage's theorem works down to the level of log space same exact proof so that means that non-deterministic log space is contained in deterministic log squared space because that's that what savage's theory does for you it's it it converts non-deterministic machines are deterministic machines at the cost of a squaring in the amount of space you need um and so i'm not going to go through this in detail but the same picture that i copied off an earlier slide with a simple modification is that instead of um you know that i'm right down the the the size of the configuration is going to be now login because that's how big the configurations are when you have a non-deterministic log space machine and so simulating that so these are this would be what the um uh the tableau would look like for an nl machine um and then you can simulate that in the same way by you know trying all possible intermediates and then splitting it you know doing the top half and then the bottom half we're using the space of course recursively um the amount of space you're going to need is going to be enough to store for one level of the recursion uh one configuration and that's the order log space and then the number of levels of recursion is going to be another factor of log n because that's log to the running time which is going to be exponential and log n which or is polynomial so the total amount of space that you would need would be log squared space again this is sort of saying the proof of savage's theorem just over again um so if it's coming too fast for you just review the proof of savage's theorem and observe that it works even if the amount of space that the machine that the non-deterministic machine starts off with is log space all right um and uh last thing i'm going to be last thing in the category of a review is a uh our uh theorem that not only is all of l within p and that's kind of trivial kind of immediate you don't even have to change the machine if you have a log space machine for some language the very same machine is a polynomial time machine for that language because it can only be running for a polynomial amount of time but we have a non-deterministic gene for some language we're going to have to change it to become a deterministic machine that runs in polynomial time and so we're going to give a deterministic polynomial times simulation of a non-deterministic log space machine um and uh we kind of did this last time a little quickly so now if we have some non-deterministic log space machine so um m which decides a language a in in log space um we're going to show how to simulate that machine um with a deterministic polynomial time machine and the key idea which which is going to come up um uh in in a later theorem so good to understand it now not only here but to uh to understand it uh for uh for the next theorem that's coming is the notion of a configuration graph i was sort of thinking about calling it a computation graph but now on further reflection i think configuration graph maybe is the more suggestive term so let's stick with that um so configuration graph for a machine on an input is just a set of all configurations that the machine has all the possible different configurations um the machine can have with edges connecting configurations that correspond to legal moves of the machine so here's some configuration this is a snapshot of the machine at a moment in time here is some other configuration another snapshot of the machine at a moment in time and you're going to draw an edge between ci and cj if cj could follow in one step from ci and you could tell by just looking at the configurations whether that could be possible obviously the head has to be one place over in cj from where it was in ci and it has to be updated according to the rules of the machine so you can tell whether um you know you so you you could fill out this graph you could write down all the possible configurations and you can put the edges down now the point is that when we have a log space machine we don't have too many config possible configurations there's only a polynomial number so the size of this whole graph is polynomial so our polynomial time simulation is going to write down that entire configuration graph of the log space machine on its input there are many configurations that can be only polynomially many so you can write down all those configurations as the nodes and then go look at each pair of nodes whether this configuration could lead to that configuration according to you know it's a non-deterministic machine so a configuration could go to several different loc you know there could be several different ways to go but those are just several different outgoing edges from a particular node in this graph representing the configuration which might have several different legal successors in the non-deterministic computation okay now the important thing here is that m accepts its input w exactly when there is a path this configuration graph that takes you from the start configuration to the accept configuration and as i mentioned let's assume as we've been doing that the machine i should have put it here but i didn't but the the machine um when it is about to accept it erases its work tape and moves both of its head to the home position at the left end of the tape so there's just one accepting configuration you have to worry about it just makes life simpler um so there's going to be a start configuration a single accept configuration in this configuration graph and now there's going to be a path indicated here that connects the start configuration to the accept configuration if and only if m accepts w because that path is the sequence of configurations that the machine would go through if you launched it on w it would start at the start and there might be several different ways to go but if there is one of them that leads you to an accept that's going to correspond to a branch of the computation that's accepting okay so that's tells us what the polynomial time algorithm is it says you on input w you you construct that configuration graph for m on w g sub mw and you test whether there's a path from c star to c except using any polynomial time um you know depth first searched or breadth first search you know um algorithm for testing whether there's a connection passed in a graph and if there is such a path you accept because that means the machine m accepted and if there was no path you reject because then m uh must have not accepted and therefore you have a uh polynomial time simulation of your non-deterministic log space machine m okay how are we doing okay so that tells us that nl is contained within p and also l is contained with an nl as before so we have kind of a this hierarchy of classes um now you can even talk about not only is l different from n l even as l different from p is it possible that anything that you can do in polynomial time you can do a lot of space don't know open question okay i'm getting a very good question here just now why is this construction taking log space it doesn't this instruction takes polynomial time this can this algorithm here is not a polynomial this is not a log space algorithm that i'm giving you i'm giving a polynomial time algorithm for stimulating a non-deterministic log space machine now later on you know i don't want to confuse the issue right now for this particular slide all i need to do is construct that graph in polynomial time it's a you know it's a polynomial size graph i can't store that whole graph in a log space memory okay so question here um [Music] you know we can see that listing out to the nodes and edges would be polynomial time but how do we actually provide structure to this graph representation i don't even know what that means so if you can clarify that for me then maybe i can try to answer it but you know a graph is just a list of nodes and a list of edges after that we know what the graph is i mean you know you may like a picture but the machine doesn't need a picture um you know our definition of you know we we just represent these things as um uh and in the end so please clarify if you want me to i'll try to i'll answer it at the next at the next pause um i'm grateful for all the questions because i'm sure any question that any of you have another 20 of you also have so it's um questions are good uh don't don't don't be bashful um and also ask the tas if i could become overloaded um okay now we're going to shift gears into some new material all right um we're going to talk about the notion that uh sort of thinking about analogous to the p versus np problem where there were these np complete problems now we have the l versus nl problem there are going to be nl complete problems and that kind of capture the essence of nl the way np complete problems capture the essence of np in a sense and that all other problems in np are reducible to them so they're kind of like the hardest np problems here we're going to have exactly analogous situation for nl um where we're going to uh show problems where all other nl problems are reducible to them so if you can kind of solve one of them like solve one of these nl complete problems in log space deterministically then you solve all of nl problems in log space deterministically so um it's a very similar looking definition to what we had before uh it's an l complete if it's in nl and then all other languages in nl should be reducible but now we have a new notion here um with an l instead of a p now before when we talked about np completeness we had polynomial time reducibility that's not going to work anymore because if you remember nl is a subset of p so all nl languages are polynomial are our languages in p and if we're talking about if we use polynomial time reducibility all languages and p are reducible to each other we need to have a notion of reducibility which is kind of weaker than the class um and so uh polynomial time reducibility just would not work here because everything would become nl complete because everything is introducible to each other so we need to have a weaker notion we're going to use log space reducibility which we have to define [Music] so here for that we're going to have to talk about the notion of a function that you can compute in log space okay and it's a little tricky here just like when we talked about language recognition in log space where we had the work tape had to be smaller than the input tape because the inputs can be large the work area is small now the output also could be large relative to the work area so we're going to have a three tape model where there's the input is going to be a read only the output is a write only it's like a printer it's something you can only write on but you can't read back because otherwise you can cheat by using the output as a kind of storage and then you have your storage area which is your your read write work tape okay so this would call this you know the traditional name of this is a log space transducer so it you know it converts inputs to outputs but uses only log space for its working memory okay so the input tape has stores in bit and symbols the work tape stores log n symbols order login symbols and then we have the output tape i mean you want to think about how big can they there's going to be a check in coming to kind of uh ask you how big could the memory could the output be but that also will save that for the end if you can mult that over if you're uh want to think ahead okay um [Music] so we think of a log space transducer as computing a function which is just a mapping from the input to the output that the transducer provides for you a transducer transducer is a deterministic machine by the way so you take the transducer you give it a w and you turn it on and then it out holds with f of w on its output tape that's what it means to be computing the function f okay and we'll say that a is log space reducible to b using the l subscript symbol on the less than or equal to sign if it's mapping reducible to b but by a reduction function that's computable in log space just the same way we defined polynomial time reducibility but there we insisted that the reduction function was computable in polynomial time um okay just quickly i got a question again uh you know why why log space here because polynomial time would be too powerful for doing reductions uh internal to p every language in p is reducible to every other language in p and so everything in nl would be reducible to everything else in l with a polynomial time reducibility and so that would not be an interesting notion we have to use a weaker notion than that a weaker kind of reduction um using a weaker model so that you don't get the otherwise the the the re reduction function would be able to answer whether um you know it would be able to solve the problem a itself if we had a polynomial time reduction and we're mapping things from logs in you know nl to other problems in nl the reduction would solve the problem that's not what you want the reduction should be constrained only to be able to do simple transformations on the uh on the problem not to solve the problem anyway you have to look at that you know this is an issue that's come up before when we talked about um what's the right notion of reduction to use for piece based completeness same exact discussion okay now there is an issue here though uh that we have to be careful of when we have a being log space reducible to b and b and l then what you want um [Music] uh if if a is log space reducible to b and b and l then you want a to be in l that's the same pattern we've always had for reductions if a is reducible to b and b is easy then a is easy so here in the notion of easy as being an l um now if you remember the proof of that that we had from before which i'll just put out for you is that um to show a log space solver for a um uh you take an input w and now if a is reducible to b you do compute the reduction and then you run the decider for b um so if we're assuming a is reducible to b and b is in l so b has a log space decider you you take your w which you want to know is it in a you map it over to the b a b problem using the reduction function and then you solve it using the decider for b and you give the same answer now this actually doesn't work anymore it doesn't work in an obvious way because if you if you're following me i hope you most of you are um there is a there is a problem here which because we're trying to give a a log space algorithm for a and that algorithm is going to be computing this reduction function mapping w to f of w f of w might itself be very large as this picture suggests here you may not be able to store f of w in the log space memory for the machine that's deciding any so this is an obstacle that we need to solve in order to prove this theorem which we need because that's the whole justification for doing these reducibilities um should be a familiar looking kind of line to what we've seen before uh so we don't have space to store f of w what do we do and and i'll also mention that this is going to be relevant to one of your homework problems so what do we do we don't have space to store the intermediate result that we need in order to solve the problem you know we started with w now we need to test if f of w is in b that can run in log space but just simply getting your hands on f w how do you what do you do about that um so what we're going to do is the following is the decider um the the decider for b which needs f of w um because it's deciding if f of w is in b um it doesn't need all of f w sitting there in front of it all at once if you think about how the turing machine operates on its input it only looks at one symbol at a time you know it starts out reading the left foremost symbol of f w then maybe he moves his head right moves the second symbol of f of w then the third symbol of f of w maybe gets up to the uh tenth symbol of f w maybe it moves his head back and goes to the ninth symbol in the eighth symbol but the turing machine's head you know which is deciding b only looks at one symbol of f of w at a time uh so instead of writing down all of f w the idea is that we are going to compute the individual symbols of f of w that we need only at the moment we need them so if the decider for b [Music] is reading the tenth symbol of f w we fire up um the transducer on w and as it's writing out its output which we don't have space to store anymore we throw away all of the output values until we get to the tenth one and then we said ah the tenth one is whatever is a c whatever the value is now we feed that into the uh decider for b we can now simulate that decider for one more step now the decider says now i need the 11th um symbol of f w okay now we can run the run the machine for one more place um but if it needs but we don't even have to do it if you know we the i think the better way to think about it is every time that decider for b needs another symbol we start the transducer over again and just keep throw away everything except for that one symbol output that we that we need so every time we do another step of simulating b we're going to have to re-run the transducer from the beginning just to recompute that or compute maybe for the first time or recomputed if we need it subsequently this is going to be slow but we don't care um to uh recompute that that symbol that that the uh simulator that the decider for b uh requires okay so i'm saying that over here recompute the symbols of f of w as needed okay so let me let's take a couple of questions and then we're going to move to a check-in so so somebody's asking why we why did we have to introduce transducer for log space reducibility when we didn't do it for polynomial time reducibility we could have for polynomial time reducibility but we didn't need to because we could just all do it on the same tape the problem is for log space the tape is the work tape is too small to hold the input on the output so we can't um you know since we're only working we have a log n bound that we have to work within uh we need to uh separate those functions from the work functions the input function and the output function in the case if we had if we have more than um you know the amount of resource we have either time or space was at least n then we could just lump them all together and have that one tape do multi you know uh multiple functions um and somebody's asking me here yeah this is mapping reducibility this m this is what we from the notion we saw before okay um does f of w lie on the input tape of b well yes so we are good question so f of w you know because what are we doing we're trying to find a decider for a here using the decider for b and the and the mapping from a to b um the reduction from a to b so the decider for b expects to find its input on an input tape um that input is going to be f of w but but you know we have to get the effect of that without actually writing down that input tape because we don't have enough room to write down the input tape for the decider for the b decider because that could be very large and we we only have we have no place to put the f of w to think about what's going on here we're making a log space machine whose input is w has to compute f of w as an intermediate value to feed it into the beta side that is not going to be possible to hold on to that whole f of w at one to altogether because it's too big but that doesn't mean we don't need it we only need one symbol at a time which we can recompute um okay so let's see um so somebody says can we just ensure that the output tape is order n so we don't need more tape than the input order n is still going to be too big where you're going to put that output even if it's or just order n first of all no the answer is no we can't because there are going to be reductions which are bigger than that but the other question is if you know can we just ensure that the output is order n you can't put the output on the input tape the input tape is read only the output tape is right only so there's no place to just even if the output is just as big as the input it doesn't help you if the output is only log in okay then we could do it but that's not going to be interesting for us the obvious the you know you're going to need for these log space reductions big outputs um as we'll see in a minute uh what's the running time for this log space reduction it's all going to be polynomial it's all going to be a log space algorithm so it's all going to be polynomial um is there any np completeness reduction which can be done in log space all of the np com all typical np completeness reductions those polynomial time reductions they all can be done in log space because they are reductions tend to be very simple transformations and log space is going to be enough to do all of them um okay uh i can't answer the second part of that too that's too complicated and i think we should move on um so um let's let's look at the first check in here uh so if we have a log space transducer that computes f and if you defeated inputs of length n how how big can the outputs be actually um so what you think about that and give me an answer i'll give you a minute uh to answer this question oh this is a tough one these are this is i i i let me just say up front there are i i struggle with this lecture because some especially the stuff in the second half it's kind of hard it's i wouldn't say it's it's technical but conceptually i think some of the material is is is a little harder maybe in part because people are not used to thinking about um memory complexity or space complexity even though i don't see why i mean i think it's an important resource to be considering but i think it's less common and i think there's some um discomfort with that okay the so we're just about done here um five more seconds please all right about to wrap wrap the chicken oh one two three all right so yes the correct answer is c um as i mentioned uh you know we're going to want to have outputs that are larger than log n and there's no reason why they wouldn't be able to be larger than log n according to the definition that i gave you gave you there's no bound on the output we're only measuring the the run the running space of this algorithm in terms of its um work tape the input and output tapes don't count so they could be more than log n they can be more than n polynomial is the right answer why because a log space transducer um if you just ignore the output it's just an ordinary log space machine and i know it can only run for a polynomial number of steps without an end up going into a loop the same argument that we gave for that before applies here as well um so if it's going to exceed a polynomial number of steps it's never going to hold and so that's going to be not allow it it's got a halt with the output on the output tape and so that it'll be disqualified as a as a log space transducer if it doesn't uh if it doesn't hold so it can't be anything longer than polynomial it's a good thing to think about to understand okay so let's continue um so we're going to show that the path problem is nl-complete now we had we defined nl completeness and we've we've seen the path problem before um and we're now going to show that path occupies that very special position for nl namely that it's an ml complete problem um so if you can solve the path problem deterministically in log space you have gotten a big result who knows how to do that and it would it would collapse all of n l down to path down to log space if you could do path in log space deterministically um okay so let's see why that is so first of all the two components of being complete are being in the language and the reduction part so in the language we've shown already uh now we want to show that for any language other language in nl it's going to be log space reducible to path in a certain sense this may not feel so surprising thinking back to our proof that nl is in uh is a subset of p because we managed to convert any nl machine and any the running of any l machine to a path problem that the the polynomial time machine then solved um and so it's really the same idea that says that path really captures any you know any um uh any and any nl machine you know the computation of any nl machine really can be seen as a path problem um where the nodes are the configurations of the machine um so let's just see how let me just try to go through that if that wasn't super clear which i'm not sure it was um so suppose we have a machine decided by a language decided by non-deterministic you know an nl machine and non-deterministic machine in log space um again i should have put this before but we're going to modify m to erase its work tape and move its head to the left and on accepting so um it has a unique accepting configuration um now i'm going to give the log space reduction that maps our language a which is in nl to the path language so thinking about what that means i'm going to take an input w which may or may not be an a and produce for you a graph with a start and target node starting targeted nodes um where w is going to be in the language if and only if g has a path from s to t and what do you think that graph is going to be that's going to be the configuration graph for the machine that decides a okay so um [Music] that is uh how it's going to look so here maybe here's a picture right so f of w where w again is your problem about membership in a is going to become a pr a problem about membership and path and it's just going to be the configuration graph for m on w um now what's left is to show that we can do this conversion in with a log space transducer so it's a log space computable reduction um so let's just try to go through that quickly um it's not conceptually not super hard um [Music] so here's our transducer let's just think about what it needs to do it needs to take an input w and convert that f of w to this thing here the computation graph of m on w the configuration graph m on w the start and except configuration so that's going to look like this down here that's what we want to eventually appear on the output tape [Music] so the way we're going to achieve that we all only have a small log space order log space work tape and the way we're going to be able to produce this output is you know the the configuration graph it's just a series of edges which are say you can go from this configuration to that configuration in one step so what we're going to do is on our work tape we're going to go through all possible pairs of configurations again just in some like odometer order just by looking at all possible strings really of length order log n that are big enough to represent two configurations every once in a while it's going to be actually a pair of configurations at that point we look at those two configurations look at m and see can this configuration go to that configuration if yes you print it out on the output if no you just move on to the next pair of configurations so it's not and then at the end you write down the start and accept configurations so i've i've indicated that here here is the transducer it says on input w for all pairs of configurations that now this is getting written down on the right work tape you output those pairs which are legal moves for m and then finally i'll put the starting accept that's it so let's just see let me take any questions here um why do we need special except state for m well we want to have i think you mean accepting configuration i just want to have this i don't want to have a multiplicity of different possible accepting configurations because then it's not really a path problem then it becomes a question of can i get from the start to one of those accepting you know nodes representing accepting configurations that's a little messy i can fix it but the simplest fix is just to make there be a single accepting configuration um well why do i output starting except at the end of the output tape that's the way i write down my path problem it's a graph followed by a start node and a target node so that's i have to follow that form that's oh i'm not sure what you're asking you want me that you want me to put that first i'm not sure what the or or why at all because it has to be a um you know here it is here's the output i'm looking for um okay do the three do the read write work tape here store pointers to configuration or some sort of counter no they store the actual configuration the configuration for m is just think about what it is it's a log space size object it's an it's a tape for m it's a location of its heads and it stayed so you're just gonna write down that stuff over right over here on the left side of this uh this left slot and on the right slide you're gonna write another configuration for m on w um and um you're going to just then put the edges in accordingly okay so somebody did that help you know some again is asking why is the configuration on the log space it's just a tape it's a log space tape that's the main thing in the configuration of the tape um on the read white work tape do we have do we only write two configurations at once yeah we're just writing down a candidate edge that we're going to output onto the output tape so that's why we have two configurations i want to know can i get from this configuration to that configuration if yes i print it out print out that pair that's an edge in my config my my configuration graph which is what i'm supposed to be outputting here can there be mo okay when we move on again direct questions to our tas who are uh would be more than happy to help you uh and we will let me just quickly give i'm a little running a little tight here time wise but let's just see um here's an example of showing some other problem is nl complete you have a homework problem on that so i thought i want to give you an example maybe we can just defer this to the recitation if so maybe we'll try to do this a little quickly um to save us some time but the two-set problem which is just like the three sad problem except with two literals per clause curiously the complement of that problem so the unsatisfiable problem um uh formulas that form an nl complete language um and so first of all you have to show it's in nl we're not going to do that it's a nice exercise it's not totally trivial to do um but it it's i you might want to try that um we're going to show that path is reducible to the complement of two set we've got to give a reduction that gives converts graphs to formulas where there is a path now when the formula is unsatisfied and that um what's going to happen is the path is going to correspond to a sequence of implications in the formula which yields a contradiction and forces it to be unsatisfiable again this is going to come a little fast but um and then you know maybe we can discuss that over the break which is next so every node in g is going to have associated variable in the formula so there's a variable for every one of the nodes for every edge there's going to be a clause of implication connecting those two associated nodes so if there's an edge from u to v then there's going to be an implication in the formula that says uh if x u is true then x v is true um and note that that's equivalent to the more conventional ways xu complement or xv these are logically equivalent so i'm not cheating you here in terms of being a two sat problem they really just look like this and lastly i'm going to put uh two additional clauses it's a x for the start variable um from the start node s here s uh i want i want to force that one to be true so it's x since i want to have two exactly two per clause as xs or xs so that forces x that that variable true and similarly and and lastly if t is true that's going to force um the the the if x t is true that's going to force x s to be false so now if there's actually a path in the graph that goes from s to t there's going to be a sequence of implications starting out with s being true forcing other things being true including forcing t to be true which then forces s to be false and that's our contradiction which shows that the formula cannot be satisfied um so now you have to prove that this works um as i said you can for the forward direction if there is a path you follow the implications to get a contradiction for the reverse let me not uh spend time here you can i'll leave this to you to think about offline um but if there is no path there is a way of assigning the variables to true and false to make a satisfying assignment to the formula so that gives the other direction okay um so and you can show it's computable in log space that's very simple because a very simple transformation there okay so uh i think we're gonna move on to the break um and uh i'm happy to take questions at this point about this does the configuration going back include the input no the configuration does not i mean as i said the configuration for m on w is the state the head positions and the work tape contents not the input tape because then you would be it's not there for a reason the input is huge um but you don't need the input there because the input is going to be constant for everybody everybody can look at that input which is a fixed uh sort of external thing um uh somebody's asking me are there any np complete problems in [Music] there are definitely np complete theories some i don't i don't know um uh there are some problems in number three where it's you know like factoring where we don't know the status somewhere between p and np um you know it's formulated as a language of course but uh there are problems in um solving certain kinds of uh equations uh low degree equations um that that uh i don't remember now exactly those are actually known to be np-complete um now us but nl-completa i don't know if they're nl-complete number theory problems oh good question somebody's asking me does nl also have an alternative definition using certificates or witnesses yeah um yes sort of um for nl you can make a certificate which is again polynomial size certificate but it has to be you're only allowed to read it with a one-way head so it's like a one-way one-way certificate um so it had to be you can only process it in a certain way that's that's a nice exercise actually itself um but anyway let us uh we are now um johnny um and we're going to move back we're going to continue so everybody return uh this is um what's next on the agenda proving that nl equals cohen l this is a hard proof um i'm going to try to break it down as much as i can and let's hope you you get i i hope you i hope you get it uh i'll try to be as helpful as i can as i can okay um but if you if you're finding it tough you won't be alone so um first of all we're going to show the way we're going to solve this is by showing that the complement of path is solvable in n in nl because the complement of path is just as path is complete for nl the complement is complete for co and l um and so by doing that problem in nl we're going to reduce all of co all of cohen l will be reducible to problems in n l and so therefore will be n n l colon l will be then inside n l and then uh n l is going to be equal to coin um if that sequence of logical connections um uh is not clear don't worry the point is is that we want go back and figure out why that's enough later but what this means is we want to give a non-deterministic machine which will accept when there is no path from s to t okay and and please don't say why don't we just take the machine for path and flip the answer you can't do that with a non-deterministic machine um so you better if you're thinking that that's allowed go back and review non-determinism um so you want to make a non-deterministic machine which is going to accept when there's no path so some branch is going to make a sequence of guesses and it has to be sure that there's no path and then it's going to be um and then it can accept when there's no path now if you can find a way of like making a separator something that cuts the graph in half and separates s from t then you would be good um the only problem is um there's no um there's no obvious way of doing that because those kind of separators even if they were probably too big to write down in um in log space so i'm going to give you a completely different way of doing it and um i'm going to make this is a little different presentation than what's in the book i think hopefully this is a little longer and therefore a little clearer um we'll see uh so first of all i'm going to define a notion of a non-deterministic machine computing a function and that's a simple idea what you want is on the different branches so you have some function f which has for every w there's a output f of w um and what and the non-deterministic machine can operate that on all of its branches it's allowed to either give f of w or say reject mean punt this is or say i don't know so every branch has to give the right f the right answer so all the all the branches that give an answer have to agree because there's only one right answer all the branches that give an answer have to give the right answer or they can say i don't know um the only thing is you have to also say that at least one of the branches actually gives an answer so somebody doesn't cannot reject somebody cannot say i don't know um so at least one of the branches gives an answer and gives the gives the answer and all the other branches can either give the answer or they can say they can just reject okay um but there's no notion of accepting there's just an accept notion of this non-deterministic machine on some branches giving the output value and other branches just punting and saying reject maybe reject is the wrong word i could just say punt um [Music] all right uh so we're going to be talking about functions that you can compute with um non-deterministic machines with nl machines uh in particular all right so we're going to look at this path language this path function now now this is not exactly the same as the path language this is a function here written with lowercase so given a graph s and t i'm going to say yes if there is a path and no if there's no path and this is a function now which is going to output yes or no not a language um this is a function it's very closely related i understand you know so if you can solve the function you can do the language um but what we're going to give is a nl machine a non-deterministic machine which is going to compute this function and therefore you can use that to do the path language two important things for us is here if g is some graph and here's the starting node s um r is all of the nodes that you can reach from s this is a this is a some uh collection of nodes and c which stands for count is the number of reachable nodes so i've written it down here more if you like it more formally uh r is the number is the collection of nodes for where the from for which there's a path from s to that node and c is the size of r so this you have to understand these two because we're going to be playing with this for the next three slides okay now first of all this is kind of a little bit of an exercise theorem but it's still going to be a useful fact that we're going to end up needing later but it's also a little bit of just to test your understanding suppose there's some nl machine which computes this path function so um you know on the different branches of the non-determinism given you know a graph a g s and t there are going to be some branches which may output yes or some branches that may open no and other branches may say i don't know but the machine always has to give the right answer if it's going to give any answer so all branches either have to say yes or all branches all branches have to say yes or punt or all branches have to say no or punt because one of those answers is going to be the right answer um so suppose i have a way of computing path by an nl machine then can i also compute can i make some other nl machine which computes the count of the number of reached uh the number of nodes reachable so if i can test if a node is reachable can i figure out how many nodes are reachable this is supposed to be easy this is kind of a little bit of a practice um so if i can figure out if nodes are reachable yes or no then i can say figure out how many nodes are reachable you just go through them one by one testing if they're reachable and count the ones that are that's the only that's that's all i have in mind so start with a counter that's set to zero initially and go through each of the nodes of g one by one and i use my nl machine that computes path that's what i mean by this part um so i test if um the nl machine says yes there is a path then i increase the counter and if it says there's no path then i just continue without increasing the count now when i'm running my nl machine to calculate this compute this function that nl machine might punt might reject sometimes on some branches that's okay you know i'm i'm also allowed i'm also an nl machine i'm computing a value um and i also might punt on some uh branches uh so at the end i'm gonna output that count okay so what i'm gonna prove next is the converse of this and that's and that's the magical hard part that if i can compute the count then i can com then i can do the test uh of whether um uh individual nodes are uh connected have a path from s um okay so let's just see somebody's asking in non-deterministic machines uh so you know like m is not allowed to loop no if a machine if any one of these machines like an nl machine loops it's going to be going forever that's not allowed so no looping um i'm sure that's relevant but no lu no looping but i'm more worried is that you understand this uh theorem here um i think we have a check incoming let's let's see okay this might be helpful so consider the statement that path complement is in l that's what we're trying to prove and also that some nl machine can compute the path function these are going to be related facts which one can we prove from the other easily i mean they're both going to be true so in some sense it's trivial but i want to know which one can we prove kind of immediately without doing much work that i can solve this path problem in nl the complement of the path problem in an l or that i can compute the path function in analysis so what do you think um [Music] okay um almost done here yeah ending uh you guys didn't do well [Laughter] that's okay uh the actually the right answer is c um most of you got that if i can solve the path function sorry the yes no value i can use that now to solve both path and path complement that you know uh that's seems more clear-cut but suppose i can solve the path complement problem in an nl and i can also i also know i can solve the path problem in nl that that we've already shown um so knowing both of those um you know if i given a g s and t what i can do is not deterministically pick which of those two directions you know i pick i'm going to guess well uh it's in path or it's in the complement of path so there are two different non-deterministic ways to go one of those is going to always end up rejecting um and so that's going to end up hunting the other direction is going to sometimes end up accepting and sometimes punting and based upon whether which side is ends up one or the other is going to have some except um is going to be accepting and so the one that's accepting is going to tell me whether to answer yes or no so actually both directions um both implications follow pretty easily um okay anyway let's see let's try uh to show this is this is the hard part uh and we have five minutes let's see how far we can get um so this theorem works by magic so uh you know it kind of blew everybody's mind when it was first came out so let's just see it's really not that hard but it's sort of it's kind of twisted um so suppose there some machine can compute c the count the number reachable from s i'm going to use that to solve path um the path function to test yes i can but yes if there is a path or no there is no path for each node so if i know how many nodes are reachable then i can solve now for individual nodes which is strange that you can do that now i'm not telling you how to compute c that's for later which i probably won't get to but just imagine pretend we can somehow figure out what the count is of the number of reachable nodes okay so here is my uh non-deterministic algorithm for computing path first i'm going to compute c or let's say c is given and now maybe the best thing to do is to try to give you the idea up front um what we're going to do since we're a little short on time what we're going to do is suppose i tell you there are in this graph a hundred nodes reachable from s so c is a hundred there's a hundred reachable nodes now i wanna know i say well i i i i don't really that's all very nice but i'd like to know this particular node t is that reachable from x now you're i'm a non-deterministic machine now if t was reachable then i'd be fine because non-deterministically i don't even care about the hundred i take and non-deterministically on some branch starting from s i'm gonna hit t and that branch is gonna say yes the other branches maybe they'll punt but some branches are going to get the right answer the problem is suppose t is not reachable then you want some branches to say no and how could that branch ever say no unless it's sure that t is not reachable and how can one branch be sure the idea is this suppose i know that there are a hundred reachable nodes what i'm what what i'm going to do non-deterministically is i'm going to guess those hundred nodes one by one can't keep you can't store them all because it could be a hundred could be a big number uh i'm gonna guess them one by one i'm gonna guess them and every time i guess a note i'm going to prove it's reachable by guessing the path that shows it's reachable so i'm going to guess 100 nodes prove that they're reachable and then see is was t one of those reachable notes if it was well and then i would have found it and i would notice a yes but if t was not one of the hundred reachable nodes and i know there's only a hundred so if t is not one of those nodes and i in other words if i found them all and t wasn't one of them then i know it's not reachable and that's how using the count i can be sure that certain nodes are not reachable because i just find all the ones that are prove that they are check that the count agrees with what i was given and then say no t is not reachable if it's not one of those nodes that i've found you know to be reachable which adds up to my given count that's the whole idea of course how do you get the count oddly enough it just it's really it's kind of the same idea repeat it over and over again but uh i guess we'll have to do that next time so let's just write this down and we'll kind of uh use that as the beginning of uh thursday's lecture um so we're going to go through each node u one by one we're now gonna guess for each node whether there's a path to it or not so i'm gonna call it either p or n um again this is now think about my 100 nodes i'm going to be guessing all 100 nodes uh i'm going to nondeterministically pick a path um from that node that i guessed is reachable so if i guess a node there is a path i'm going to confirm there's a path by non-deterministically picking it if i don't find that path i just reject punt on that on that on that branch if that path that i found actually led me to t that so you that node that i'm working on is currently t then i know to accept but otherwise i'm just going to count the number of nodes that i find are reachable um if i've guessed that u is not reachable i'm just going to skip it um at the end i see whether the number of nodes that i've determined are reachable agrees with my original count c so does k equal c or not if it doesn't equal they're not equal then i didn't find all the reachable nodes i didn't guess right and so i punt i say well i bad branch of the non-determinism i i just give up but some branch of the non-determinism is going to guess all of the correct nodes which are reachable and then if t hadn't been found already to be one of them at this point i know t is not reachable and so i cannot put no okay um so that's that's the that's the whole thing um what is m m is the good question m is the number of nodes of the graph i should have said that so you don't want to go to you don't want to get into a loop um so you better cut off your picking of a path uh to some cutoff value so you're going to cut it off at m which is the number of nodes which is longer going to be long enough actually that uh we're going to play with that in a bit later but um okay let's just see how do i know i did not visit the same node twice when counting because i'm just going to go through all of the nodes in some order you know to pick any order you know the the nodes appear in some order in the uh representation of the graph on the input you know but so in the old order i'm just going to go through the nodes in order therefore i'm never going to see the same node twice um what does step four mean um so yeah step four is i'm standing for means i'm for each node i'm guessing that that node is either um has a path to it from s or does not have a path to it from s um so you know kind of thinking about it the original we're at a time so why don't i um you know i'm happy to discuss this um in the office hours i'm just going to skip over the rest of the slides here um and review like we have a missing check in uh my choice let's just uh i want to make sure everybody's got uh all their check-ins here so why don't we just uh if we know nl is equal to coin l we also we show to sat complement is nl-complete it also then follows that two stat itself is in l complete because n l equals common l so i'm going to give you the answer to this just because i want to want you all to uh finish this poll still some of you are getting wrong uh okay uh so please answer it quick and then we're gonna end are we all done get your participation points here three seconds okay ending okay um doesn't matter so here we we ran over sorry about that quick review this is what we didn't quite finish as part five but we'll finish that next time okay when showing path is nl complete we also need to list the nodes for constructing the graph the slides only mention edges yeah i kind of skipped that but yeah you can just write down all the nodes um again but that's also going to just take log space as you as you observe yeah technically when you're writing down a graph you write down a list of the nodes and you write down a list of the edges i kind of skipped writing down the nodes but yeah it's the same doesn't matter so i'm going to say goodbye to you all thank you you 3 00:00:28,400 --> 00:00:31,509 hi folks welcome back um so we will continue our discussion uh that we had um that we've been doing for the past few lectures um we first talked about time complexity and then we shifted gears to talk about space complexity um and we saw we had a couple of lectures on pspace uh kind of culminating in proving that there were languages which are piece based complete namely this tqbf language which is where we started and then we also proved that there are problems around involving games such as the generalized geography game where determining which side has a winning strategy is this case piece based complete at the end of the lecture uh last time we moved to a different regime of space namely from polynomial space down to log space and we introduced the classes l and nl and so i'm going to begin today's lecture by reviewing some of the material on lnl which i think came a little too quickly last time and then we have two important theorems we're going to cover today one is about proving that there are complete languages for nl um that has a bearing on the l versus nl question you know log space deterministic log space versus non-deterministic log space that's yet another unsolved problem in our field and so there's a notion of a complete problem from for nl and um then we're going to prove a theorem that was in its day very surprising to people i remember when it came out um in the 1980s um that nl in fact is closed under complementation that the nl class and cohen l class uh class uh both uh collapse uh to one that they're equal which is not the way we believe the situation to be for np but until someone has a proof that they're different uh strange things can happen okay um so with that i will um move myself to uh into the corner and uh let's do our review um so we are um in order to talk about space complexity classes that are smaller than n we had to introduce a new model which was the two tape model where there was a read-only tape that had the input on it um which you normally would think of something very large the whole internet or uh uh um you know something so big that you can't read it into your kind of your local memory um and uh then you have a worktop which is your your local memory and the way we're going to think about it in this uh in the context of log space is that that work tape is logarithmic in the size of the input and that is enough to have small counters or pointers into the input um because the reference location of the input is just needs you only need login bits to do that so we gave a couple of examples of the l and n of l and nl languages so this language of ww reverse as you may remember so here is an input um in ww reverse it's a string follow you know it's a palindromic string which is of even length and so you can make a machine in log space here that can test whether it's input is of that form and the work tape is only all it needs is a pointer into um or a couple of pointers that refer to the corresponding places of the input that you're looking at at the moment so you maybe look start out looking at the two outside a's and then the and then the this b symbols that are next to that and you can write down on your tape where you're looking currently and so that's going to be enough for you to you may have to zigzag of course back and forth a lot in order to do that test but that's completely fine um using the the model we're not going to be measuring time we're only going to be focusing on how much space we're using another example that we gave is the path language where you're given a graph and a start node and a target node and you want to know is there a path is there a path um this directed graph that goes from s to t and that's a language that's also that language is an nl in fact not known to be an l so the way that would look shifting to an input of uh in the path language you would have a graph represented say by a sequence of edges and a start and a target and the work tape would keep track of the current node um so the nondeterministic machine would guess a path that takes you from s to t node by node and the work tape would keep track of the current node okay so i hope you have this develop a little bit of an intuition for these classes l and n l we're going to be spending the the entire lecture today talking about that um okay um so as i mentioned the l and n l um problem is an unsolved problem and it's very much uh analogous to the p versus np problem except as i mentioned as we'll show that uh nl and its complement are end up being the same which is not something that seems to be the case for np that we don't know um uh can we think of this as a multi-head turing machine i'm getting a question about that which is i think you can um in fact that's an alternative way that people look at it you can think of it as having mult you know a head is basically needs log space uh uh to to store the location to to store um you know the the location of where that head would be so if you imagine having several different heads on the input tape you can think of a log space machine as being sort of a turing machine that has multiple heads on the input tape it's it's equivalent um good question uh so let's move on then um um okay so one of the things we proved last time was that uh anything that you can do in l you can also do in polynomial time um and i'll answer some of these uh chat questions in a minute but uh the [Music] um so the class l is a subset of p this is easy to prove but i think it's nevertheless important to see why it's true because it sort of sets some definitions of things that we're going to use later so in particular we really need to know the notion of a configuration of a log space machine on an input um so because the input is is it does not change we don't really consider the input to be part of the configuration the only thing that's the the thing that's relevant in the configuration is the dynamic part of the machine the state the head locations and and the work tape contents uh so we're defining that the mach configuration for the machine on a particular input w is those four things um state the two head locations and the tape contents and the important thing to keep in mind for this theorem is that we have only a polynomial number of different configurations if you just do the calculation uh the main part is the number of different tape contents as you can have which is exponential and log n and that's a polynomial and so therefore any machine that runs in log space provided it always holds and we always assume our machines always hold they can only run for a polynomial number of steps because that's as many different configurations as they have they ran for um say an exponential number of steps they would have to be repeating um configurations and then they would be loading okay um so um there we go um so okay so let me just get back so there's a somebody asked me a question which is harder p versus zen p or l versus n l you know completely no idea um uh it's a uh you know i guess there was a common line of thinking that um if you're gonna that it's good to try to think about if you're trying to separate classes you might as well take classes that are as far apart as one another um uh you know like if you're trying to prove if you're comparing p different from np and p different from p space maybe p different from p space might be easier because p and p space seem to be even further apart than p and np nobody knows and i suspect that there's something fundamental about computation that we just don't understand and then once somebody makes a breakthrough and solves one of those problems a lot of them are going to get solved in short order but again purely speculation um okay d what is d here d would be the size of the tape alphabet okay so this is the number of different tape contents we have good all right um so let's continue on another thing we mentioned kind of quickly in passing but still an important fact is that um savage's theorem works down to the level of log space same exact proof so that means that non-deterministic log space is contained in deterministic log squared space because that's that what savage's theory does for you it's it it converts non-deterministic machines are deterministic machines at the cost of a squaring in the amount of space you need um and so i'm not going to go through this in detail but the same picture that i copied off an earlier slide with a simple modification is that instead of um you know that i'm right down the the the size of the configuration is going to be now login because that's how big the configurations are when you have a non-deterministic log space machine and so simulating that so these are this would be what the um uh the tableau would look like for an nl machine um and then you can simulate that in the same way by you know trying all possible intermediates and then splitting it you know doing the top half and then the bottom half we're using the space of course recursively um the amount of space you're going to need is going to be enough to store for one level of the recursion uh one configuration and that's the order log space and then the number of levels of recursion is going to be another factor of log n because that's log to the running time which is going to be exponential and log n which or is polynomial so the total amount of space that you would need would be log squared space again this is sort of saying the proof of savage's theorem just over again um so if it's coming too fast for you just review the proof of savage's theorem and observe that it works even if the amount of space that the machine that the non-deterministic machine starts off with is log space all right um and uh last thing i'm going to be last thing in the category of a review is a uh our uh theorem that not only is all of l within p and that's kind of trivial kind of immediate you don't even have to change the machine if you have a log space machine for some language the very same machine is a polynomial time machine for that language because it can only be running for a polynomial amount of time but we have a non-deterministic gene for some language we're going to have to change it to become a deterministic machine that runs in polynomial time and so we're going to give a deterministic polynomial times simulation of a non-deterministic log space machine um and uh we kind of did this last time a little quickly so now if we have some non-deterministic log space machine so um m which decides a language a in in log space um we're going to show how to simulate that machine um with a deterministic polynomial time machine and the key idea which which is going to come up um uh in in a later theorem so good to understand it now not only here but to uh to understand it uh for uh for the next theorem that's coming is the notion of a configuration graph i was sort of thinking about calling it a computation graph but now on further reflection i think configuration graph maybe is the more suggestive term so let's stick with that um so configuration graph for a machine on an input is just a set of all configurations that the machine has all the possible different configurations um the machine can have with edges connecting configurations that correspond to legal moves of the machine so here's some configuration this is a snapshot of the machine at a moment in time here is some other configuration another snapshot of the machine at a moment in time and you're going to draw an edge between ci and cj if cj could follow in one step from ci and you could tell by just looking at the configurations whether that could be possible obviously the head has to be one place over in cj from where it was in ci and it has to be updated according to the rules of the machine so you can tell whether um you know you so you you could fill out this graph you could write down all the possible configurations and you can put the edges down now the point is that when we have a log space machine we don't have too many config possible configurations there's only a polynomial number so the size of this whole graph is polynomial so our polynomial time simulation is going to write down that entire configuration graph of the log space machine on its input there are many configurations that can be only polynomially many so you can write down all those configurations as the nodes and then go look at each pair of nodes whether this configuration could lead to that configuration according to you know it's a non-deterministic machine so a configuration could go to several different loc you know there could be several different ways to go but those are just several different outgoing edges from a particular node in this graph representing the configuration which might have several different legal successors in the non-deterministic computation okay now the important thing here is that m accepts its input w exactly when there is a path this configuration graph that takes you from the start configuration to the accept configuration and as i mentioned let's assume as we've been doing that the machine i should have put it here but i didn't but the the machine um when it is about to accept it erases its work tape and moves both of its head to the home position at the left end of the tape so there's just one accepting configuration you have to worry about it just makes life simpler um so there's going to be a start configuration a single accept configuration in this configuration graph and now there's going to be a path indicated here that connects the start configuration to the accept configuration if and only if m accepts w because that path is the sequence of configurations that the machine would go through if you launched it on w it would start at the start and there might be several different ways to go but if there is one of them that leads you to an accept that's going to correspond to a branch of the computation that's accepting okay so that's tells us what the polynomial time algorithm is it says you on input w you you construct that configuration graph for m on w g sub mw and you test whether there's a path from c star to c except using any polynomial time um you know depth first searched or breadth first search you know um algorithm for testing whether there's a connection passed in a graph and if there is such a path you accept because that means the machine m accepted and if there was no path you reject because then m uh must have not accepted and therefore you have a uh polynomial time simulation of your non-deterministic log space machine m okay how are we doing okay so that tells us that nl is contained within p and also l is contained with an nl as before so we have kind of a this hierarchy of classes um now you can even talk about not only is l different from n l even as l different from p is it possible that anything that you can do in polynomial time you can do a lot of space don't know open question okay i'm getting a very good question here just now why is this construction taking log space it doesn't this instruction takes polynomial time this can this algorithm here is not a polynomial this is not a log space algorithm that i'm giving you i'm giving a polynomial time algorithm for stimulating a non-deterministic log space machine now later on you know i don't want to confuse the issue right now for this particular slide all i need to do is construct that graph in polynomial time it's a you know it's a polynomial size graph i can't store that whole graph in a log space memory okay so question here um [Music] you know we can see that listing out to the nodes and edges would be polynomial time but how do we actually provide structure to this graph representation i don't even know what that means so if you can clarify that for me then maybe i can try to answer it but you know a graph is just a list of nodes and a list of edges after that we know what the graph is i mean you know you may like a picture but the machine doesn't need a picture um you know our definition of you know we we just represent these things as um uh and in the end so please clarify if you want me to i'll try to i'll answer it at the next at the next pause um i'm grateful for all the questions because i'm sure any question that any of you have another 20 of you also have so it's um questions are good uh don't don't don't be bashful um and also ask the tas if i could become overloaded um okay now we're going to shift gears into some new material all right um we're going to talk about the notion that uh sort of thinking about analogous to the p versus np problem where there were these np complete problems now we have the l versus nl problem there are going to be nl complete problems and that kind of capture the essence of nl the way np complete problems capture the essence of np in a sense and that all other problems in np are reducible to them so they're kind of like the hardest np problems here we're going to have exactly analogous situation for nl um where we're going to uh show problems where all other nl problems are reducible to them so if you can kind of solve one of them like solve one of these nl complete problems in log space deterministically then you solve all of nl problems in log space deterministically so um it's a very similar looking definition to what we had before uh it's an l complete if it's in nl and then all other languages in nl should be reducible but now we have a new notion here um with an l instead of a p now before when we talked about np completeness we had polynomial time reducibility that's not going to work anymore because if you remember nl is a subset of p so all nl languages are polynomial are our languages in p and if we're talking about if we use polynomial time reducibility all languages and p are reducible to each other we need to have a notion of reducibility which is kind of weaker than the class um and so uh polynomial time reducibility just would not work here because everything would become nl complete because everything is introducible to each other so we need to have a weaker notion we're going to use log space reducibility which we have to define [Music] so here for that we're going to have to talk about the notion of a function that you can compute in log space okay and it's a little tricky here just like when we talked about language recognition in log space where we had the work tape had to be smaller than the input tape because the inputs can be large the work area is small now the output also could be large relative to the work area so we're going to have a three tape model where there's the input is going to be a read only the output is a write only it's like a printer it's something you can only write on but you can't read back because otherwise you can cheat by using the output as a kind of storage and then you have your storage area which is your your read write work tape okay so this would call this you know the traditional name of this is a log space transducer so it you know it converts inputs to outputs but uses only log space for its working memory okay so the input tape has stores in bit and symbols the work tape stores log n symbols order login symbols and then we have the output tape i mean you want to think about how big can they there's going to be a check in coming to kind of uh ask you how big could the memory could the output be but that also will save that for the end if you can mult that over if you're uh want to think ahead okay um [Music] so we think of a log space transducer as computing a function which is just a mapping from the input to the output that the transducer provides for you a transducer transducer is a deterministic machine by the way so you take the transducer you give it a w and you turn it on and then it out holds with f of w on its output tape that's what it means to be computing the function f okay and we'll say that a is log space reducible to b using the l subscript symbol on the less than or equal to sign if it's mapping reducible to b but by a reduction function that's computable in log space just the same way we defined polynomial time reducibility but there we insisted that the reduction function was computable in polynomial time um okay just quickly i got a question again uh you know why why log space here because polynomial time would be too powerful for doing reductions uh internal to p every language in p is reducible to every other language in p and so everything in nl would be reducible to everything else in l with a polynomial time reducibility and so that would not be an interesting notion we have to use a weaker notion than that a weaker kind of reduction um using a weaker model so that you don't get the otherwise the the the re reduction function would be able to answer whether um you know it would be able to solve the problem a itself if we had a polynomial time reduction and we're mapping things from logs in you know nl to other problems in nl the reduction would solve the problem that's not what you want the reduction should be constrained only to be able to do simple transformations on the uh on the problem not to solve the problem anyway you have to look at that you know this is an issue that's come up before when we talked about um what's the right notion of reduction to use for piece based completeness same exact discussion okay now there is an issue here though uh that we have to be careful of when we have a being log space reducible to b and b and l then what you want um [Music] uh if if a is log space reducible to b and b and l then you want a to be in l that's the same pattern we've always had for reductions if a is reducible to b and b is easy then a is easy so here in the notion of easy as being an l um now if you remember the proof of that that we had from before which i'll just put out for you is that um to show a log space solver for a um uh you take an input w and now if a is reducible to b you do compute the reduction and then you run the decider for b um so if we're assuming a is reducible to b and b is in l so b has a log space decider you you take your w which you want to know is it in a you map it over to the b a b problem using the reduction function and then you solve it using the decider for b and you give the same answer now this actually doesn't work anymore it doesn't work in an obvious way because if you if you're following me i hope you most of you are um there is a there is a problem here which because we're trying to give a a log space algorithm for a and that algorithm is going to be computing this reduction function mapping w to f of w f of w might itself be very large as this picture suggests here you may not be able to store f of w in the log space memory for the machine that's deciding any so this is an obstacle that we need to solve in order to prove this theorem which we need because that's the whole justification for doing these reducibilities um should be a familiar looking kind of line to what we've seen before uh so we don't have space to store f of w what do we do and and i'll also mention that this is going to be relevant to one of your homework problems so what do we do we don't have space to store the intermediate result that we need in order to solve the problem you know we started with w now we need to test if f of w is in b that can run in log space but just simply getting your hands on f w how do you what do you do about that um so what we're going to do is the following is the decider um the the decider for b which needs f of w um because it's deciding if f of w is in b um it doesn't need all of f w sitting there in front of it all at once if you think about how the turing machine operates on its input it only looks at one symbol at a time you know it starts out reading the left foremost symbol of f w then maybe he moves his head right moves the second symbol of f of w then the third symbol of f of w maybe gets up to the uh tenth symbol of f w maybe it moves his head back and goes to the ninth symbol in the eighth symbol but the turing machine's head you know which is deciding b only looks at one symbol of f of w at a time uh so instead of writing down all of f w the idea is that we are going to compute the individual symbols of f of w that we need only at the moment we need them so if the decider for b [Music] is reading the tenth symbol of f w we fire up um the transducer on w and as it's writing out its output which we don't have space to store anymore we throw away all of the output values until we get to the tenth one and then we said ah the tenth one is whatever is a c whatever the value is now we feed that into the uh decider for b we can now simulate that decider for one more step now the decider says now i need the 11th um symbol of f w okay now we can run the run the machine for one more place um but if it needs but we don't even have to do it if you know we the i think the better way to think about it is every time that decider for b needs another symbol we start the transducer over again and just keep throw away everything except for that one symbol output that we that we need so every time we do another step of simulating b we're going to have to re-run the transducer from the beginning just to recompute that or compute maybe for the first time or recomputed if we need it subsequently this is going to be slow but we don't care um to uh recompute that that symbol that that the uh simulator that the decider for b uh requires okay so i'm saying that over here recompute the symbols of f of w as needed okay so let me let's take a couple of questions and then we're going to move to a check-in so so somebody's asking why we why did we have to introduce transducer for log space reducibility when we didn't do it for polynomial time reducibility we could have for polynomial time reducibility but we didn't need to because we could just all do it on the same tape the problem is for log space the tape is the work tape is too small to hold the input on the output so we can't um you know since we're only working we have a log n bound that we have to work within uh we need to uh separate those functions from the work functions the input function and the output function in the case if we had if we have more than um you know the amount of resource we have either time or space was at least n then we could just lump them all together and have that one tape do multi you know uh multiple functions um and somebody's asking me here yeah this is mapping reducibility this m this is what we from the notion we saw before okay um does f of w lie on the input tape of b well yes so we are good question so f of w you know because what are we doing we're trying to find a decider for a here using the decider for b and the and the mapping from a to b um the reduction from a to b so the decider for b expects to find its input on an input tape um that input is going to be f of w but but you know we have to get the effect of that without actually writing down that input tape because we don't have enough room to write down the input tape for the decider for the b decider because that could be very large and we we only have we have no place to put the f of w to think about what's going on here we're making a log space machine whose input is w has to compute f of w as an intermediate value to feed it into the beta side that is not going to be possible to hold on to that whole f of w at one to altogether because it's too big but that doesn't mean we don't need it we only need one symbol at a time which we can recompute um okay so let's see um so somebody says can we just ensure that the output tape is order n so we don't need more tape than the input order n is still going to be too big where you're going to put that output even if it's or just order n first of all no the answer is no we can't because there are going to be reductions which are bigger than that but the other question is if you know can we just ensure that the output is order n you can't put the output on the input tape the input tape is read only the output tape is right only so there's no place to just even if the output is just as big as the input it doesn't help you if the output is only log in okay then we could do it but that's not going to be interesting for us the obvious the you know you're going to need for these log space reductions big outputs um as we'll see in a minute uh what's the running time for this log space reduction it's all going to be polynomial it's all going to be a log space algorithm so it's all going to be polynomial um is there any np completeness reduction which can be done in log space all of the np com all typical np completeness reductions those polynomial time reductions they all can be done in log space because they are reductions tend to be very simple transformations and log space is going to be enough to do all of them um okay uh i can't answer the second part of that too that's too complicated and i think we should move on um so um let's let's look at the first check in here uh so if we have a log space transducer that computes f and if you defeated inputs of length n how how big can the outputs be actually um so what you think about that and give me an answer i'll give you a minute uh to answer this question oh this is a tough one these are this is i i i let me just say up front there are i i struggle with this lecture because some especially the stuff in the second half it's kind of hard it's i wouldn't say it's it's technical but conceptually i think some of the material is is is a little harder maybe in part because people are not used to thinking about um memory complexity or space complexity even though i don't see why i mean i think it's an important resource to be considering but i think it's less common and i think there's some um discomfort with that okay the so we're just about done here um five more seconds please all right about to wrap wrap the chicken oh one two three all right so yes the correct answer is c um as i mentioned uh you know we're going to want to have outputs that are larger than log n and there's no reason why they wouldn't be able to be larger than log n according to the definition that i gave you gave you there's no bound on the output we're only measuring the the run the running space of this algorithm in terms of its um work tape the input and output tapes don't count so they could be more than log n they can be more than n polynomial is the right answer why because a log space transducer um if you just ignore the output it's just an ordinary log space machine and i know it can only run for a polynomial number of steps without an end up going into a loop the same argument that we gave for that before applies here as well um so if it's going to exceed a polynomial number of steps it's never going to hold and so that's going to be not allow it it's got a halt with the output on the output tape and so that it'll be disqualified as a as a log space transducer if it doesn't uh if it doesn't hold so it can't be anything longer than polynomial it's a good thing to think about to understand okay so let's continue um so we're going to show that the path problem is nl-complete now we had we defined nl completeness and we've we've seen the path problem before um and we're now going to show that path occupies that very special position for nl namely that it's an ml complete problem um so if you can solve the path problem deterministically in log space you have gotten a big result who knows how to do that and it would it would collapse all of n l down to path down to log space if you could do path in log space deterministically um okay so let's see why that is so first of all the two components of being complete are being in the language and the reduction part so in the language we've shown already uh now we want to show that for any language other language in nl it's going to be log space reducible to path in a certain sense this may not feel so surprising thinking back to our proof that nl is in uh is a subset of p because we managed to convert any nl machine and any the running of any l machine to a path problem that the the polynomial time machine then solved um and so it's really the same idea that says that path really captures any you know any um uh any and any nl machine you know the computation of any nl machine really can be seen as a path problem um where the nodes are the configurations of the machine um so let's just see how let me just try to go through that if that wasn't super clear which i'm not sure it was um so suppose we have a machine decided by a language decided by non-deterministic you know an nl machine and non-deterministic machine in log space um again i should have put this before but we're going to modify m to erase its work tape and move its head to the left and on accepting so um it has a unique accepting configuration um now i'm going to give the log space reduction that maps our language a which is in nl to the path language so thinking about what that means i'm going to take an input w which may or may not be an a and produce for you a graph with a start and target node starting targeted nodes um where w is going to be in the language if and only if g has a path from s to t and what do you think that graph is going to be that's going to be the configuration graph for the machine that decides a okay so um [Music] that is uh how it's going to look so here maybe here's a picture right so f of w where w again is your problem about membership in a is going to become a pr a problem about membership and path and it's just going to be the configuration graph for m on w um now what's left is to show that we can do this conversion in with a log space transducer so it's a log space computable reduction um so let's just try to go through that quickly um it's not conceptually not super hard um [Music] so here's our transducer let's just think about what it needs to do it needs to take an input w and convert that f of w to this thing here the computation graph of m on w the configuration graph m on w the start and except configuration so that's going to look like this down here that's what we want to eventually appear on the output tape [Music] so the way we're going to achieve that we all only have a small log space order log space work tape and the way we're going to be able to produce this output is you know the the configuration graph it's just a series of edges which are say you can go from this configuration to that configuration in one step so what we're going to do is on our work tape we're going to go through all possible pairs of configurations again just in some like odometer order just by looking at all possible strings really of length order log n that are big enough to represent two configurations every once in a while it's going to be actually a pair of configurations at that point we look at those two configurations look at m and see can this configuration go to that configuration if yes you print it out on the output if no you just move on to the next pair of configurations so it's not and then at the end you write down the start and accept configurations so i've i've indicated that here here is the transducer it says on input w for all pairs of configurations that now this is getting written down on the right work tape you output those pairs which are legal moves for m and then finally i'll put the starting accept that's it so let's just see let me take any questions here um why do we need special except state for m well we want to have i think you mean accepting configuration i just want to have this i don't want to have a multiplicity of different possible accepting configurations because then it's not really a path problem then it becomes a question of can i get from the start to one of those accepting you know nodes representing accepting configurations that's a little messy i can fix it but the simplest fix is just to make there be a single accepting configuration um well why do i output starting except at the end of the output tape that's the way i write down my path problem it's a graph followed by a start node and a target node so that's i have to follow that form that's oh i'm not sure what you're asking you want me that you want me to put that first i'm not sure what the or or why at all because it has to be a um you know here it is here's the output i'm looking for um okay do the three do the read write work tape here store pointers to configuration or some sort of counter no they store the actual configuration the configuration for m is just think about what it is it's a log space size object it's an it's a tape for m it's a location of its heads and it stayed so you're just gonna write down that stuff over right over here on the left side of this uh this left slot and on the right slide you're gonna write another configuration for m on w um and um you're going to just then put the edges in accordingly okay so somebody did that help you know some again is asking why is the configuration on the log space it's just a tape it's a log space tape that's the main thing in the configuration of the tape um on the read white work tape do we have do we only write two configurations at once yeah we're just writing down a candidate edge that we're going to output onto the output tape so that's why we have two configurations i want to know can i get from this configuration to that configuration if yes i print it out print out that pair that's an edge in my config my my configuration graph which is what i'm supposed to be outputting here can there be mo okay when we move on again direct questions to our tas who are uh would be more than happy to help you uh and we will let me just quickly give i'm a little running a little tight here time wise but let's just see um here's an example of showing some other problem is nl complete you have a homework problem on that so i thought i want to give you an example maybe we can just defer this to the recitation if so maybe we'll try to do this a little quickly um to save us some time but the two-set problem which is just like the three sad problem except with two literals per clause curiously the complement of that problem so the unsatisfiable problem um uh formulas that form an nl complete language um and so first of all you have to show it's in nl we're not going to do that it's a nice exercise it's not totally trivial to do um but it it's i you might want to try that um we're going to show that path is reducible to the complement of two set we've got to give a reduction that gives converts graphs to formulas where there is a path now when the formula is unsatisfied and that um what's going to happen is the path is going to correspond to a sequence of implications in the formula which yields a contradiction and forces it to be unsatisfiable again this is going to come a little fast but um and then you know maybe we can discuss that over the break which is next so every node in g is going to have associated variable in the formula so there's a variable for every one of the nodes for every edge there's going to be a clause of implication connecting those two associated nodes so if there's an edge from u to v then there's going to be an implication in the formula that says uh if x u is true then x v is true um and note that that's equivalent to the more conventional ways xu complement or xv these are logically equivalent so i'm not cheating you here in terms of being a two sat problem they really just look like this and lastly i'm going to put uh two additional clauses it's a x for the start variable um from the start node s here s uh i want i want to force that one to be true so it's x since i want to have two exactly two per clause as xs or xs so that forces x that that variable true and similarly and and lastly if t is true that's going to force um the the the if x t is true that's going to force x s to be false so now if there's actually a path in the graph that goes from s to t there's going to be a sequence of implications starting out with s being true forcing other things being true including forcing t to be true which then forces s to be false and that's our contradiction which shows that the formula cannot be satisfied um so now you have to prove that this works um as i said you can for the forward direction if there is a path you follow the implications to get a contradiction for the reverse let me not uh spend time here you can i'll leave this to you to think about offline um but if there is no path there is a way of assigning the variables to true and false to make a satisfying assignment to the formula so that gives the other direction okay um so and you can show it's computable in log space that's very simple because a very simple transformation there okay so uh i think we're gonna move on to the break um and uh i'm happy to take questions at this point about this does the configuration going back include the input no the configuration does not i mean as i said the configuration for m on w is the state the head positions and the work tape contents not the input tape because then you would be it's not there for a reason the input is huge um but you don't need the input there because the input is going to be constant for everybody everybody can look at that input which is a fixed uh sort of external thing um uh somebody's asking me are there any np complete problems in [Music] there are definitely np complete theories some i don't i don't know um uh there are some problems in number three where it's you know like factoring where we don't know the status somewhere between p and np um you know it's formulated as a language of course but uh there are problems in um solving certain kinds of uh equations uh low degree equations um that that uh i don't remember now exactly those are actually known to be np-complete um now us but nl-completa i don't know if they're nl-complete number theory problems oh good question somebody's asking me does nl also have an alternative definition using certificates or witnesses yeah um yes sort of um for nl you can make a certificate which is again polynomial size certificate but it has to be you're only allowed to read it with a one-way head so it's like a one-way one-way certificate um so it had to be you can only process it in a certain way that's that's a nice exercise actually itself um but anyway let us uh we are now um johnny um and we're going to move back we're going to continue so everybody return uh this is um what's next on the agenda proving that nl equals cohen l this is a hard proof um i'm going to try to break it down as much as i can and let's hope you you get i i hope you i hope you get it uh i'll try to be as helpful as i can as i can okay um but if you if you're finding it tough you won't be alone so um first of all we're going to show the way we're going to solve this is by showing that the complement of path is solvable in n in nl because the complement of path is just as path is complete for nl the complement is complete for co and l um and so by doing that problem in nl we're going to reduce all of co all of cohen l will be reducible to problems in n l and so therefore will be n n l colon l will be then inside n l and then uh n l is going to be equal to coin um if that sequence of logical connections um uh is not clear don't worry the point is is that we want go back and figure out why that's enough later but what this means is we want to give a non-deterministic machine which will accept when there is no path from s to t okay and and please don't say why don't we just take the machine for path and flip the answer you can't do that with a non-deterministic machine um so you better if you're thinking that that's allowed go back and review non-determinism um so you want to make a non-deterministic machine which is going to accept when there's no path so some branch is going to make a sequence of guesses and it has to be sure that there's no path and then it's going to be um and then it can accept when there's no path now if you can find a way of like making a separator something that cuts the graph in half and separates s from t then you would be good um the only problem is um there's no um there's no obvious way of doing that because those kind of separators even if they were probably too big to write down in um in log space so i'm going to give you a completely different way of doing it and um i'm going to make this is a little different presentation than what's in the book i think hopefully this is a little longer and therefore a little clearer um we'll see uh so first of all i'm going to define a notion of a non-deterministic machine computing a function and that's a simple idea what you want is on the different branches so you have some function f which has for every w there's a output f of w um and what and the non-deterministic machine can operate that on all of its branches it's allowed to either give f of w or say reject mean punt this is or say i don't know so every branch has to give the right f the right answer so all the all the branches that give an answer have to agree because there's only one right answer all the branches that give an answer have to give the right answer or they can say i don't know um the only thing is you have to also say that at least one of the branches actually gives an answer so somebody doesn't cannot reject somebody cannot say i don't know um so at least one of the branches gives an answer and gives the gives the answer and all the other branches can either give the answer or they can say they can just reject okay um but there's no notion of accepting there's just an accept notion of this non-deterministic machine on some branches giving the output value and other branches just punting and saying reject maybe reject is the wrong word i could just say punt um [Music] all right uh so we're going to be talking about functions that you can compute with um non-deterministic machines with nl machines uh in particular all right so we're going to look at this path language this path function now now this is not exactly the same as the path language this is a function here written with lowercase so given a graph s and t i'm going to say yes if there is a path and no if there's no path and this is a function now which is going to output yes or no not a language um this is a function it's very closely related i understand you know so if you can solve the function you can do the language um but what we're going to give is a nl machine a non-deterministic machine which is going to compute this function and therefore you can use that to do the path language two important things for us is here if g is some graph and here's the starting node s um r is all of the nodes that you can reach from s this is a this is a some uh collection of nodes and c which stands for count is the number of reachable nodes so i've written it down here more if you like it more formally uh r is the number is the collection of nodes for where the from for which there's a path from s to that node and c is the size of r so this you have to understand these two because we're going to be playing with this for the next three slides okay now first of all this is kind of a little bit of an exercise theorem but it's still going to be a useful fact that we're going to end up needing later but it's also a little bit of just to test your understanding suppose there's some nl machine which computes this path function so um you know on the different branches of the non-determinism given you know a graph a g s and t there are going to be some branches which may output yes or some branches that may open no and other branches may say i don't know but the machine always has to give the right answer if it's going to give any answer so all branches either have to say yes or all branches all branches have to say yes or punt or all branches have to say no or punt because one of those answers is going to be the right answer um so suppose i have a way of computing path by an nl machine then can i also compute can i make some other nl machine which computes the count of the number of reached uh the number of nodes reachable so if i can test if a node is reachable can i figure out how many nodes are reachable this is supposed to be easy this is kind of a little bit of a practice um so if i can figure out if nodes are reachable yes or no then i can say figure out how many nodes are reachable you just go through them one by one testing if they're reachable and count the ones that are that's the only that's that's all i have in mind so start with a counter that's set to zero initially and go through each of the nodes of g one by one and i use my nl machine that computes path that's what i mean by this part um so i test if um the nl machine says yes there is a path then i increase the counter and if it says there's no path then i just continue without increasing the count now when i'm running my nl machine to calculate this compute this function that nl machine might punt might reject sometimes on some branches that's okay you know i'm i'm also allowed i'm also an nl machine i'm computing a value um and i also might punt on some uh branches uh so at the end i'm gonna output that count okay so what i'm gonna prove next is the converse of this and that's and that's the magical hard part that if i can compute the count then i can com then i can do the test uh of whether um uh individual nodes are uh connected have a path from s um okay so let's just see somebody's asking in non-deterministic machines uh so you know like m is not allowed to loop no if a machine if any one of these machines like an nl machine loops it's going to be going forever that's not allowed so no looping um i'm sure that's relevant but no lu no looping but i'm more worried is that you understand this uh theorem here um i think we have a check incoming let's let's see okay this might be helpful so consider the statement that path complement is in l that's what we're trying to prove and also that some nl machine can compute the path function these are going to be related facts which one can we prove from the other easily i mean they're both going to be true so in some sense it's trivial but i want to know which one can we prove kind of immediately without doing much work that i can solve this path problem in nl the complement of the path problem in an l or that i can compute the path function in analysis so what do you think um [Music] okay um almost done here yeah ending uh you guys didn't do well [Laughter] that's okay uh the actually the right answer is c um most of you got that if i can solve the path function sorry the yes no value i can use that now to solve both path and path complement that you know uh that's seems more clear-cut but suppose i can solve the path complement problem in an nl and i can also i also know i can solve the path problem in nl that that we've already shown um so knowing both of those um you know if i given a g s and t what i can do is not deterministically pick which of those two directions you know i pick i'm going to guess well uh it's in path or it's in the complement of path so there are two different non-deterministic ways to go one of those is going to always end up rejecting um and so that's going to end up hunting the other direction is going to sometimes end up accepting and sometimes punting and based upon whether which side is ends up one or the other is going to have some except um is going to be accepting and so the one that's accepting is going to tell me whether to answer yes or no so actually both directions um both implications follow pretty easily um okay anyway let's see let's try uh to show this is this is the hard part uh and we have five minutes let's see how far we can get um so this theorem works by magic so uh you know it kind of blew everybody's mind when it was first came out so let's just see it's really not that hard but it's sort of it's kind of twisted um so suppose there some machine can compute c the count the number reachable from s i'm going to use that to solve path um the path function to test yes i can but yes if there is a path or no there is no path for each node so if i know how many nodes are reachable then i can solve now for individual nodes which is strange that you can do that now i'm not telling you how to compute c that's for later which i probably won't get to but just imagine pretend we can somehow figure out what the count is of the number of reachable nodes okay so here is my uh non-deterministic algorithm for computing path first i'm going to compute c or let's say c is given and now maybe the best thing to do is to try to give you the idea up front um what we're going to do since we're a little short on time what we're going to do is suppose i tell you there are in this graph a hundred nodes reachable from s so c is a hundred there's a hundred reachable nodes now i wanna know i say well i i i i don't really that's all very nice but i'd like to know this particular node t is that reachable from x now you're i'm a non-deterministic machine now if t was reachable then i'd be fine because non-deterministically i don't even care about the hundred i take and non-deterministically on some branch starting from s i'm gonna hit t and that branch is gonna say yes the other branches maybe they'll punt but some branches are going to get the right answer the problem is suppose t is not reachable then you want some branches to say no and how could that branch ever say no unless it's sure that t is not reachable and how can one branch be sure the idea is this suppose i know that there are a hundred reachable nodes what i'm what what i'm going to do non-deterministically is i'm going to guess those hundred nodes one by one can't keep you can't store them all because it could be a hundred could be a big number uh i'm gonna guess them one by one i'm gonna guess them and every time i guess a note i'm going to prove it's reachable by guessing the path that shows it's reachable so i'm going to guess 100 nodes prove that they're reachable and then see is was t one of those reachable notes if it was well and then i would have found it and i would notice a yes but if t was not one of the hundred reachable nodes and i know there's only a hundred so if t is not one of those nodes and i in other words if i found them all and t wasn't one of them then i know it's not reachable and that's how using the count i can be sure that certain nodes are not reachable because i just find all the ones that are prove that they are check that the count agrees with what i was given and then say no t is not reachable if it's not one of those nodes that i've found you know to be reachable which adds up to my given count that's the whole idea of course how do you get the count oddly enough it just it's really it's kind of the same idea repeat it over and over again but uh i guess we'll have to do that next time so let's just write this down and we'll kind of uh use that as the beginning of uh thursday's lecture um so we're going to go through each node u one by one we're now gonna guess for each node whether there's a path to it or not so i'm gonna call it either p or n um again this is now think about my 100 nodes i'm going to be guessing all 100 nodes uh i'm going to nondeterministically pick a path um from that node that i guessed is reachable so if i guess a node there is a path i'm going to confirm there's a path by non-deterministically picking it if i don't find that path i just reject punt on that on that on that branch if that path that i found actually led me to t that so you that node that i'm working on is currently t then i know to accept but otherwise i'm just going to count the number of nodes that i find are reachable um if i've guessed that u is not reachable i'm just going to skip it um at the end i see whether the number of nodes that i've determined are reachable agrees with my original count c so does k equal c or not if it doesn't equal they're not equal then i didn't find all the reachable nodes i didn't guess right and so i punt i say well i bad branch of the non-determinism i i just give up but some branch of the non-determinism is going to guess all of the correct nodes which are reachable and then if t hadn't been found already to be one of them at this point i know t is not reachable and so i cannot put no okay um so that's that's the that's the whole thing um what is m m is the good question m is the number of nodes of the graph i should have said that so you don't want to go to you don't want to get into a loop um so you better cut off your picking of a path uh to some cutoff value so you're going to cut it off at m which is the number of nodes which is longer going to be long enough actually that uh we're going to play with that in a bit later but um okay let's just see how do i know i did not visit the same node twice when counting because i'm just going to go through all of the nodes in some order you know to pick any order you know the the nodes appear in some order in the uh representation of the graph on the input you know but so in the old order i'm just going to go through the nodes in order therefore i'm never going to see the same node twice um what does step four mean um so yeah step four is i'm standing for means i'm for each node i'm guessing that that node is either um has a path to it from s or does not have a path to it from s um so you know kind of thinking about it the original we're at a time so why don't i um you know i'm happy to discuss this um in the office hours i'm just going to skip over the rest of the slides here um and review like we have a missing check in uh my choice let's just uh i want to make sure everybody's got uh all their check-ins here so why don't we just uh if we know nl is equal to coin l we also we show to sat complement is nl-complete it also then follows that two stat itself is in l complete because n l equals common l so i'm going to give you the answer to this just because i want to want you all to uh finish this poll still some of you are getting wrong uh okay uh so please answer it quick and then we're gonna end are we all done get your participation points here three seconds okay ending okay um doesn't matter so here we we ran over sorry about that quick review this is what we didn't quite finish as part five but we'll finish that next time okay when showing path is nl complete we also need to list the nodes for constructing the graph the slides only mention edges yeah i kind of skipped that but yeah you can just write down all the nodes um again but that's also going to just take log space as you as you observe yeah technically when you're writing down a graph you write down a list of the nodes and you write down a list of the edges i kind of skipped writing down the nodes but yeah it's the same doesn't matter so i'm going to say goodbye to you all thank you you 4 00:00:31,509 --> 00:00:34,310 5 00:00:34,310 --> 00:00:37,110 6 00:00:37,110 --> 00:00:39,670 7 00:00:39,670 --> 00:00:41,830 8 00:00:41,830 --> 00:00:44,150 9 00:00:44,150 --> 00:00:47,590 10 00:00:47,590 --> 00:00:51,189 11 00:00:51,189 --> 00:00:51,199 12 00:00:51,199 --> 00:00:52,229 13 00:00:52,229 --> 00:00:54,470 14 00:00:54,470 --> 00:00:56,310 15 00:00:56,310 --> 00:00:57,910 16 00:00:57,910 --> 00:01:00,869 17 00:01:00,869 --> 00:01:04,310 18 00:01:04,310 --> 00:01:06,789 19 00:01:06,789 --> 00:01:09,030 20 00:01:09,030 --> 00:01:10,630 21 00:01:10,630 --> 00:01:12,789 22 00:01:12,789 --> 00:01:14,469 23 00:01:14,469 --> 00:01:15,830 24 00:01:15,830 --> 00:01:15,840 25 00:01:15,840 --> 00:01:16,710 26 00:01:16,710 --> 00:01:19,510 27 00:01:19,510 --> 00:01:21,590 28 00:01:21,590 --> 00:01:21,600 29 00:01:21,600 --> 00:01:22,870 30 00:01:22,870 --> 00:01:25,830 31 00:01:25,830 --> 00:01:28,070 32 00:01:28,070 --> 00:01:29,910 33 00:01:29,910 --> 00:01:31,429 34 00:01:31,429 --> 00:01:33,190 35 00:01:33,190 --> 00:01:34,789 36 00:01:34,789 --> 00:01:36,390 37 00:01:36,390 --> 00:01:38,149 38 00:01:38,149 --> 00:01:41,270 39 00:01:41,270 --> 00:01:43,910 40 00:01:43,910 --> 00:01:45,830 41 00:01:45,830 --> 00:01:48,550 42 00:01:48,550 --> 00:01:49,830 43 00:01:49,830 --> 00:01:52,069 44 00:01:52,069 --> 00:01:54,389 45 00:01:54,389 --> 00:01:57,030 46 00:01:57,030 --> 00:01:59,030 47 00:01:59,030 --> 00:02:01,030 48 00:02:01,030 --> 00:02:05,270 49 00:02:05,270 --> 00:02:07,350 50 00:02:07,350 --> 00:02:09,109 51 00:02:09,109 --> 00:02:13,270 52 00:02:13,270 --> 00:02:15,589 53 00:02:15,589 --> 00:02:18,710 54 00:02:18,710 --> 00:02:21,510 55 00:02:21,510 --> 00:02:23,510 56 00:02:23,510 --> 00:02:26,630 57 00:02:26,630 --> 00:02:28,949 58 00:02:28,949 --> 00:02:31,110 59 00:02:31,110 --> 00:02:31,120 60 00:02:31,120 --> 00:02:32,869 61 00:02:32,869 --> 00:02:32,879 62 00:02:32,879 --> 00:02:33,750 63 00:02:33,750 --> 00:02:37,110 64 00:02:37,110 --> 00:02:40,229 65 00:02:40,229 --> 00:02:41,830 66 00:02:41,830 --> 00:02:44,229 67 00:02:44,229 --> 00:02:47,670 68 00:02:47,670 --> 00:02:47,680 69 00:02:47,680 --> 00:02:49,110 70 00:02:49,110 --> 00:02:50,790 71 00:02:50,790 --> 00:02:54,229 72 00:02:54,229 --> 00:02:56,869 73 00:02:56,869 --> 00:02:56,879 74 00:02:56,879 --> 00:02:57,830 75 00:02:57,830 --> 00:03:00,390 76 00:03:00,390 --> 00:03:02,470 77 00:03:02,470 --> 00:03:05,350 78 00:03:05,350 --> 00:03:07,030 79 00:03:07,030 --> 00:03:08,710 80 00:03:08,710 --> 00:03:11,110 81 00:03:11,110 --> 00:03:11,120 82 00:03:11,120 --> 00:03:12,149 83 00:03:12,149 --> 00:03:12,159 84 00:03:12,159 --> 00:03:12,949 85 00:03:12,949 --> 00:03:13,750 86 00:03:13,750 --> 00:03:15,589 87 00:03:15,589 --> 00:03:18,550 88 00:03:18,550 --> 00:03:21,030 89 00:03:21,030 --> 00:03:23,670 90 00:03:23,670 --> 00:03:25,750 91 00:03:25,750 --> 00:03:27,430 92 00:03:27,430 --> 00:03:29,110 93 00:03:29,110 --> 00:03:31,509 94 00:03:31,509 --> 00:03:34,149 95 00:03:34,149 --> 00:03:35,910 96 00:03:35,910 --> 00:03:39,190 97 00:03:39,190 --> 00:03:42,390 98 00:03:42,390 --> 00:03:43,990 99 00:03:43,990 --> 00:03:48,470 100 00:03:48,470 --> 00:03:48,480 101 00:03:48,480 --> 00:03:49,750 102 00:03:49,750 --> 00:03:49,760 103 00:03:49,760 --> 00:03:53,270 104 00:03:53,270 --> 00:03:55,750 105 00:03:55,750 --> 00:04:00,070 106 00:04:00,070 --> 00:04:02,470 107 00:04:02,470 --> 00:04:04,550 108 00:04:04,550 --> 00:04:07,910 109 00:04:07,910 --> 00:04:09,350 110 00:04:09,350 --> 00:04:11,670 111 00:04:11,670 --> 00:04:11,680 112 00:04:11,680 --> 00:04:13,350 113 00:04:13,350 --> 00:04:15,270 114 00:04:15,270 --> 00:04:17,430 115 00:04:17,430 --> 00:04:19,270 116 00:04:19,270 --> 00:04:22,790 117 00:04:22,790 --> 00:04:26,710 118 00:04:26,710 --> 00:04:29,270 119 00:04:29,270 --> 00:04:31,670 120 00:04:31,670 --> 00:04:33,590 121 00:04:33,590 --> 00:04:35,189 122 00:04:35,189 --> 00:04:37,350 123 00:04:37,350 --> 00:04:39,749 124 00:04:39,749 --> 00:04:41,110 125 00:04:41,110 --> 00:04:43,830 126 00:04:43,830 --> 00:04:46,390 127 00:04:46,390 --> 00:04:46,400 128 00:04:46,400 --> 00:04:47,830 129 00:04:47,830 --> 00:04:49,749 130 00:04:49,749 --> 00:04:52,310 131 00:04:52,310 --> 00:04:54,230 132 00:04:54,230 --> 00:04:57,749 133 00:04:57,749 --> 00:04:59,830 134 00:04:59,830 --> 00:05:01,590 135 00:05:01,590 --> 00:05:03,029 136 00:05:03,029 --> 00:05:03,039 137 00:05:03,039 --> 00:05:04,710 138 00:05:04,710 --> 00:05:06,870 139 00:05:06,870 --> 00:05:06,880 140 00:05:06,880 --> 00:05:08,230 141 00:05:08,230 --> 00:05:09,670 142 00:05:09,670 --> 00:05:11,510 143 00:05:11,510 --> 00:05:13,110 144 00:05:13,110 --> 00:05:14,230 145 00:05:14,230 --> 00:05:17,670 146 00:05:17,670 --> 00:05:18,710 147 00:05:18,710 --> 00:05:21,909 148 00:05:21,909 --> 00:05:23,830 149 00:05:23,830 --> 00:05:27,510 150 00:05:27,510 --> 00:05:27,520 151 00:05:27,520 --> 00:05:28,550 152 00:05:28,550 --> 00:05:31,909 153 00:05:31,909 --> 00:05:33,350 154 00:05:33,350 --> 00:05:35,670 155 00:05:35,670 --> 00:05:38,310 156 00:05:38,310 --> 00:05:38,320 157 00:05:38,320 --> 00:05:39,510 158 00:05:39,510 --> 00:05:41,510 159 00:05:41,510 --> 00:05:43,909 160 00:05:43,909 --> 00:05:46,629 161 00:05:46,629 --> 00:05:48,790 162 00:05:48,790 --> 00:05:51,749 163 00:05:51,749 --> 00:05:54,150 164 00:05:54,150 --> 00:05:56,629 165 00:05:56,629 --> 00:05:59,430 166 00:05:59,430 --> 00:06:01,189 167 00:06:01,189 --> 00:06:03,510 168 00:06:03,510 --> 00:06:05,590 169 00:06:05,590 --> 00:06:07,909 170 00:06:07,909 --> 00:06:07,919 171 00:06:07,919 --> 00:06:08,870 172 00:06:08,870 --> 00:06:10,629 173 00:06:10,629 --> 00:06:13,830 174 00:06:13,830 --> 00:06:15,990 175 00:06:15,990 --> 00:06:17,029 176 00:06:17,029 --> 00:06:19,510 177 00:06:19,510 --> 00:06:21,749 178 00:06:21,749 --> 00:06:24,469 179 00:06:24,469 --> 00:06:26,230 180 00:06:26,230 --> 00:06:26,240 181 00:06:26,240 --> 00:06:27,350 182 00:06:27,350 --> 00:06:29,350 183 00:06:29,350 --> 00:06:35,350 184 00:06:35,350 --> 00:06:35,360 185 00:06:35,360 --> 00:06:37,590 186 00:06:37,590 --> 00:06:40,070 187 00:06:40,070 --> 00:06:41,270 188 00:06:41,270 --> 00:06:43,510 189 00:06:43,510 --> 00:06:45,590 190 00:06:45,590 --> 00:06:47,350 191 00:06:47,350 --> 00:06:50,150 192 00:06:50,150 --> 00:06:53,749 193 00:06:53,749 --> 00:06:53,759 194 00:06:53,759 --> 00:06:54,629 195 00:06:54,629 --> 00:06:58,950 196 00:06:58,950 --> 00:06:58,960 197 00:06:58,960 --> 00:06:59,909 198 00:06:59,909 --> 00:07:02,230 199 00:07:02,230 --> 00:07:04,469 200 00:07:04,469 --> 00:07:06,070 201 00:07:06,070 --> 00:07:08,230 202 00:07:08,230 --> 00:07:10,309 203 00:07:10,309 --> 00:07:12,070 204 00:07:12,070 --> 00:07:15,430 205 00:07:15,430 --> 00:07:16,710 206 00:07:16,710 --> 00:07:16,720 207 00:07:16,720 --> 00:07:17,830 208 00:07:17,830 --> 00:07:21,350 209 00:07:21,350 --> 00:07:23,270 210 00:07:23,270 --> 00:07:24,790 211 00:07:24,790 --> 00:07:27,110 212 00:07:27,110 --> 00:07:31,350 213 00:07:31,350 --> 00:07:33,670 214 00:07:33,670 --> 00:07:36,790 215 00:07:36,790 --> 00:07:36,800 216 00:07:36,800 --> 00:07:37,040 217 00:07:37,040 --> 00:07:37,050 218 00:07:37,050 --> 00:07:38,710 219 00:07:38,710 --> 00:07:38,720 220 00:07:38,720 --> 00:07:39,990 221 00:07:39,990 --> 00:07:42,629 222 00:07:42,629 --> 00:07:44,869 223 00:07:44,869 --> 00:07:47,430 224 00:07:47,430 --> 00:07:49,749 225 00:07:49,749 --> 00:07:51,110 226 00:07:51,110 --> 00:07:52,790 227 00:07:52,790 --> 00:07:52,800 228 00:07:52,800 --> 00:07:57,510 229 00:07:57,510 --> 00:07:59,589 230 00:07:59,589 --> 00:08:02,070 231 00:08:02,070 --> 00:08:03,510 232 00:08:03,510 --> 00:08:06,790 233 00:08:06,790 --> 00:08:09,270 234 00:08:09,270 --> 00:08:11,830 235 00:08:11,830 --> 00:08:13,990 236 00:08:13,990 --> 00:08:16,230 237 00:08:16,230 --> 00:08:19,270 238 00:08:19,270 --> 00:08:20,629 239 00:08:20,629 --> 00:08:22,390 240 00:08:22,390 --> 00:08:25,510 241 00:08:25,510 --> 00:08:27,670 242 00:08:27,670 --> 00:08:29,670 243 00:08:29,670 --> 00:08:31,029 244 00:08:31,029 --> 00:08:34,310 245 00:08:34,310 --> 00:08:37,029 246 00:08:37,029 --> 00:08:39,029 247 00:08:39,029 --> 00:08:42,070 248 00:08:42,070 --> 00:08:44,470 249 00:08:44,470 --> 00:08:46,630 250 00:08:46,630 --> 00:08:48,150 251 00:08:48,150 --> 00:08:50,389 252 00:08:50,389 --> 00:08:52,630 253 00:08:52,630 --> 00:08:54,389 254 00:08:54,389 --> 00:08:56,949 255 00:08:56,949 --> 00:08:58,630 256 00:08:58,630 --> 00:08:58,640 257 00:08:58,640 --> 00:08:59,509 258 00:08:59,509 --> 00:09:01,590 259 00:09:01,590 --> 00:09:03,670 260 00:09:03,670 --> 00:09:06,150 261 00:09:06,150 --> 00:09:08,630 262 00:09:08,630 --> 00:09:11,269 263 00:09:11,269 --> 00:09:13,670 264 00:09:13,670 --> 00:09:16,150 265 00:09:16,150 --> 00:09:17,509 266 00:09:17,509 --> 00:09:17,519 267 00:09:17,519 --> 00:09:18,630 268 00:09:18,630 --> 00:09:20,949 269 00:09:20,949 --> 00:09:20,959 270 00:09:20,959 --> 00:09:22,949 271 00:09:22,949 --> 00:09:24,630 272 00:09:24,630 --> 00:09:27,110 273 00:09:27,110 --> 00:09:28,150 274 00:09:28,150 --> 00:09:28,160 275 00:09:28,160 --> 00:09:29,829 276 00:09:29,829 --> 00:09:32,070 277 00:09:32,070 --> 00:09:33,509 278 00:09:33,509 --> 00:09:36,790 279 00:09:36,790 --> 00:09:38,230 280 00:09:38,230 --> 00:09:40,150 281 00:09:40,150 --> 00:09:42,550 282 00:09:42,550 --> 00:09:44,230 283 00:09:44,230 --> 00:09:44,240 284 00:09:44,240 --> 00:09:46,070 285 00:09:46,070 --> 00:09:46,870 286 00:09:46,870 --> 00:09:49,030 287 00:09:49,030 --> 00:09:52,470 288 00:09:52,470 --> 00:09:54,470 289 00:09:54,470 --> 00:09:55,990 290 00:09:55,990 --> 00:09:57,509 291 00:09:57,509 --> 00:09:59,670 292 00:09:59,670 --> 00:10:02,870 293 00:10:02,870 --> 00:10:05,110 294 00:10:05,110 --> 00:10:07,430 295 00:10:07,430 --> 00:10:09,750 296 00:10:09,750 --> 00:10:11,670 297 00:10:11,670 --> 00:10:11,680 298 00:10:11,680 --> 00:10:12,870 299 00:10:12,870 --> 00:10:12,880 300 00:10:12,880 --> 00:10:14,230 301 00:10:14,230 --> 00:10:16,310 302 00:10:16,310 --> 00:10:18,630 303 00:10:18,630 --> 00:10:21,829 304 00:10:21,829 --> 00:10:23,509 305 00:10:23,509 --> 00:10:25,269 306 00:10:25,269 --> 00:10:25,279 307 00:10:25,279 --> 00:10:26,310 308 00:10:26,310 --> 00:10:27,590 309 00:10:27,590 --> 00:10:29,190 310 00:10:29,190 --> 00:10:31,990 311 00:10:31,990 --> 00:10:33,269 312 00:10:33,269 --> 00:10:35,509 313 00:10:35,509 --> 00:10:37,670 314 00:10:37,670 --> 00:10:37,680 315 00:10:37,680 --> 00:10:39,590 316 00:10:39,590 --> 00:10:40,630 317 00:10:40,630 --> 00:10:43,350 318 00:10:43,350 --> 00:10:45,990 319 00:10:45,990 --> 00:10:47,990 320 00:10:47,990 --> 00:10:49,829 321 00:10:49,829 --> 00:10:54,389 322 00:10:54,389 --> 00:10:54,399 323 00:10:54,399 --> 00:10:55,190 324 00:10:55,190 --> 00:10:56,949 325 00:10:56,949 --> 00:11:00,389 326 00:11:00,389 --> 00:11:01,910 327 00:11:01,910 --> 00:11:03,350 328 00:11:03,350 --> 00:11:04,790 329 00:11:04,790 --> 00:11:06,630 330 00:11:06,630 --> 00:11:09,269 331 00:11:09,269 --> 00:11:11,990 332 00:11:11,990 --> 00:11:13,590 333 00:11:13,590 --> 00:11:16,630 334 00:11:16,630 --> 00:11:17,829 335 00:11:17,829 --> 00:11:20,710 336 00:11:20,710 --> 00:11:22,870 337 00:11:22,870 --> 00:11:25,110 338 00:11:25,110 --> 00:11:25,120 339 00:11:25,120 --> 00:11:26,150 340 00:11:26,150 --> 00:11:27,590 341 00:11:27,590 --> 00:11:29,670 342 00:11:29,670 --> 00:11:31,750 343 00:11:31,750 --> 00:11:31,760 344 00:11:31,760 --> 00:11:32,710 345 00:11:32,710 --> 00:11:34,550 346 00:11:34,550 --> 00:11:35,750 347 00:11:35,750 --> 00:11:38,230 348 00:11:38,230 --> 00:11:40,389 349 00:11:40,389 --> 00:11:42,150 350 00:11:42,150 --> 00:11:43,190 351 00:11:43,190 --> 00:11:43,200 352 00:11:43,200 --> 00:11:44,389 353 00:11:44,389 --> 00:11:45,990 354 00:11:45,990 --> 00:11:47,910 355 00:11:47,910 --> 00:11:50,550 356 00:11:50,550 --> 00:11:51,350 357 00:11:51,350 --> 00:11:52,790 358 00:11:52,790 --> 00:11:54,790 359 00:11:54,790 --> 00:11:54,800 360 00:11:54,800 --> 00:11:55,750 361 00:11:55,750 --> 00:11:58,150 362 00:11:58,150 --> 00:12:00,310 363 00:12:00,310 --> 00:12:00,320 364 00:12:00,320 --> 00:12:01,030 365 00:12:01,030 --> 00:12:04,150 366 00:12:04,150 --> 00:12:04,160 367 00:12:04,160 --> 00:12:05,190 368 00:12:05,190 --> 00:12:05,200 369 00:12:05,200 --> 00:12:05,990 370 00:12:05,990 --> 00:12:08,150 371 00:12:08,150 --> 00:12:09,430 372 00:12:09,430 --> 00:12:11,350 373 00:12:11,350 --> 00:12:11,360 374 00:12:11,360 --> 00:12:12,710 375 00:12:12,710 --> 00:12:14,470 376 00:12:14,470 --> 00:12:15,509 377 00:12:15,509 --> 00:12:16,949 378 00:12:16,949 --> 00:12:19,509 379 00:12:19,509 --> 00:12:19,519 380 00:12:19,519 --> 00:12:20,870 381 00:12:20,870 --> 00:12:20,880 382 00:12:20,880 --> 00:12:22,150 383 00:12:22,150 --> 00:12:23,910 384 00:12:23,910 --> 00:12:25,670 385 00:12:25,670 --> 00:12:27,590 386 00:12:27,590 --> 00:12:30,550 387 00:12:30,550 --> 00:12:32,790 388 00:12:32,790 --> 00:12:34,710 389 00:12:34,710 --> 00:12:36,629 390 00:12:36,629 --> 00:12:38,949 391 00:12:38,949 --> 00:12:39,990 392 00:12:39,990 --> 00:12:41,750 393 00:12:41,750 --> 00:12:43,990 394 00:12:43,990 --> 00:12:45,750 395 00:12:45,750 --> 00:12:47,670 396 00:12:47,670 --> 00:12:49,110 397 00:12:49,110 --> 00:12:51,430 398 00:12:51,430 --> 00:12:54,230 399 00:12:54,230 --> 00:12:56,310 400 00:12:56,310 --> 00:12:58,870 401 00:12:58,870 --> 00:13:00,870 402 00:13:00,870 --> 00:13:02,470 403 00:13:02,470 --> 00:13:07,030 404 00:13:07,030 --> 00:13:08,069 405 00:13:08,069 --> 00:13:08,079 406 00:13:08,079 --> 00:13:09,509 407 00:13:09,509 --> 00:13:11,670 408 00:13:11,670 --> 00:13:13,910 409 00:13:13,910 --> 00:13:17,030 410 00:13:17,030 --> 00:13:18,550 411 00:13:18,550 --> 00:13:20,470 412 00:13:20,470 --> 00:13:23,829 413 00:13:23,829 --> 00:13:25,269 414 00:13:25,269 --> 00:13:27,590 415 00:13:27,590 --> 00:13:29,990 416 00:13:29,990 --> 00:13:31,590 417 00:13:31,590 --> 00:13:33,269 418 00:13:33,269 --> 00:13:34,870 419 00:13:34,870 --> 00:13:37,910 420 00:13:37,910 --> 00:13:40,710 421 00:13:40,710 --> 00:13:42,389 422 00:13:42,389 --> 00:13:44,790 423 00:13:44,790 --> 00:13:47,269 424 00:13:47,269 --> 00:13:49,670 425 00:13:49,670 --> 00:13:52,310 426 00:13:52,310 --> 00:13:55,509 427 00:13:55,509 --> 00:13:55,519 428 00:13:55,519 --> 00:13:56,629 429 00:13:56,629 --> 00:13:59,430 430 00:13:59,430 --> 00:14:04,550 431 00:14:04,550 --> 00:14:07,670 432 00:14:07,670 --> 00:14:07,680 433 00:14:07,680 --> 00:14:08,870 434 00:14:08,870 --> 00:14:11,670 435 00:14:11,670 --> 00:14:11,680 436 00:14:11,680 --> 00:14:13,269 437 00:14:13,269 --> 00:14:13,279 438 00:14:13,279 --> 00:14:14,870 439 00:14:14,870 --> 00:14:17,030 440 00:14:17,030 --> 00:14:17,040 441 00:14:17,040 --> 00:14:18,230 442 00:14:18,230 --> 00:14:20,949 443 00:14:20,949 --> 00:14:20,959 444 00:14:20,959 --> 00:14:22,389 445 00:14:22,389 --> 00:14:25,350 446 00:14:25,350 --> 00:14:26,389 447 00:14:26,389 --> 00:14:26,399 448 00:14:26,399 --> 00:14:27,750 449 00:14:27,750 --> 00:14:32,069 450 00:14:32,069 --> 00:14:34,710 451 00:14:34,710 --> 00:14:38,230 452 00:14:38,230 --> 00:14:40,069 453 00:14:40,069 --> 00:14:42,550 454 00:14:42,550 --> 00:14:44,230 455 00:14:44,230 --> 00:14:46,150 456 00:14:46,150 --> 00:14:48,150 457 00:14:48,150 --> 00:14:50,949 458 00:14:50,949 --> 00:14:52,470 459 00:14:52,470 --> 00:14:55,030 460 00:14:55,030 --> 00:14:57,350 461 00:14:57,350 --> 00:14:59,509 462 00:14:59,509 --> 00:15:02,069 463 00:15:02,069 --> 00:15:03,829 464 00:15:03,829 --> 00:15:06,470 465 00:15:06,470 --> 00:15:07,910 466 00:15:07,910 --> 00:15:10,230 467 00:15:10,230 --> 00:15:12,710 468 00:15:12,710 --> 00:15:12,720 469 00:15:12,720 --> 00:15:13,829 470 00:15:13,829 --> 00:15:15,829 471 00:15:15,829 --> 00:15:17,750 472 00:15:17,750 --> 00:15:20,470 473 00:15:20,470 --> 00:15:23,509 474 00:15:23,509 --> 00:15:24,790 475 00:15:24,790 --> 00:15:26,629 476 00:15:26,629 --> 00:15:30,389 477 00:15:30,389 --> 00:15:32,629 478 00:15:32,629 --> 00:15:34,150 479 00:15:34,150 --> 00:15:36,470 480 00:15:36,470 --> 00:15:39,430 481 00:15:39,430 --> 00:15:41,829 482 00:15:41,829 --> 00:15:43,749 483 00:15:43,749 --> 00:15:46,790 484 00:15:46,790 --> 00:15:49,749 485 00:15:49,749 --> 00:15:51,829 486 00:15:51,829 --> 00:15:54,069 487 00:15:54,069 --> 00:15:56,310 488 00:15:56,310 --> 00:15:58,949 489 00:15:58,949 --> 00:15:58,959 490 00:15:58,959 --> 00:15:59,910 491 00:15:59,910 --> 00:16:01,670 492 00:16:01,670 --> 00:16:04,230 493 00:16:04,230 --> 00:16:04,240 494 00:16:04,240 --> 00:16:05,509 495 00:16:05,509 --> 00:16:08,470 496 00:16:08,470 --> 00:16:08,480 497 00:16:08,480 --> 00:16:12,790 498 00:16:12,790 --> 00:16:15,829 499 00:16:15,829 --> 00:16:18,629 500 00:16:18,629 --> 00:16:21,269 501 00:16:21,269 --> 00:16:23,189 502 00:16:23,189 --> 00:16:24,710 503 00:16:24,710 --> 00:16:26,550 504 00:16:26,550 --> 00:16:28,949 505 00:16:28,949 --> 00:16:31,110 506 00:16:31,110 --> 00:16:33,189 507 00:16:33,189 --> 00:16:35,509 508 00:16:35,509 --> 00:16:37,749 509 00:16:37,749 --> 00:16:39,670 510 00:16:39,670 --> 00:16:41,269 511 00:16:41,269 --> 00:16:43,030 512 00:16:43,030 --> 00:16:45,030 513 00:16:45,030 --> 00:16:46,550 514 00:16:46,550 --> 00:16:48,710 515 00:16:48,710 --> 00:16:50,710 516 00:16:50,710 --> 00:16:52,470 517 00:16:52,470 --> 00:16:54,949 518 00:16:54,949 --> 00:16:54,959 519 00:16:54,959 --> 00:16:57,749 520 00:16:57,749 --> 00:17:00,870 521 00:17:00,870 --> 00:17:05,750 522 00:17:05,750 --> 00:17:09,029 523 00:17:09,029 --> 00:17:11,429 524 00:17:11,429 --> 00:17:13,590 525 00:17:13,590 --> 00:17:15,829 526 00:17:15,829 --> 00:17:18,390 527 00:17:18,390 --> 00:17:20,309 528 00:17:20,309 --> 00:17:23,510 529 00:17:23,510 --> 00:17:27,029 530 00:17:27,029 --> 00:17:29,909 531 00:17:29,909 --> 00:17:31,590 532 00:17:31,590 --> 00:17:34,310 533 00:17:34,310 --> 00:17:35,750 534 00:17:35,750 --> 00:17:37,430 535 00:17:37,430 --> 00:17:37,440 536 00:17:37,440 --> 00:17:39,350 537 00:17:39,350 --> 00:17:40,390 538 00:17:40,390 --> 00:17:42,230 539 00:17:42,230 --> 00:17:42,240 540 00:17:42,240 --> 00:17:44,230 541 00:17:44,230 --> 00:17:46,710 542 00:17:46,710 --> 00:17:49,750 543 00:17:49,750 --> 00:17:51,830 544 00:17:51,830 --> 00:17:53,029 545 00:17:53,029 --> 00:17:53,039 546 00:17:53,039 --> 00:17:54,789 547 00:17:54,789 --> 00:17:58,630 548 00:17:58,630 --> 00:18:00,549 549 00:18:00,549 --> 00:18:02,710 550 00:18:02,710 --> 00:18:05,110 551 00:18:05,110 --> 00:18:07,830 552 00:18:07,830 --> 00:18:09,110 553 00:18:09,110 --> 00:18:10,470 554 00:18:10,470 --> 00:18:11,669 555 00:18:11,669 --> 00:18:13,590 556 00:18:13,590 --> 00:18:15,190 557 00:18:15,190 --> 00:18:16,549 558 00:18:16,549 --> 00:18:18,789 559 00:18:18,789 --> 00:18:19,990 560 00:18:19,990 --> 00:18:22,310 561 00:18:22,310 --> 00:18:23,430 562 00:18:23,430 --> 00:18:26,470 563 00:18:26,470 --> 00:18:29,669 564 00:18:29,669 --> 00:18:30,789 565 00:18:30,789 --> 00:18:33,510 566 00:18:33,510 --> 00:18:36,470 567 00:18:36,470 --> 00:18:39,750 568 00:18:39,750 --> 00:18:39,760 569 00:18:39,760 --> 00:18:40,710 570 00:18:40,710 --> 00:18:40,720 571 00:18:40,720 --> 00:18:42,310 572 00:18:42,310 --> 00:18:44,710 573 00:18:44,710 --> 00:18:45,909 574 00:18:45,909 --> 00:18:48,230 575 00:18:48,230 --> 00:18:50,390 576 00:18:50,390 --> 00:18:51,990 577 00:18:51,990 --> 00:18:54,150 578 00:18:54,150 --> 00:18:56,070 579 00:18:56,070 --> 00:18:58,310 580 00:18:58,310 --> 00:19:00,549 581 00:19:00,549 --> 00:19:03,350 582 00:19:03,350 --> 00:19:06,310 583 00:19:06,310 --> 00:19:07,669 584 00:19:07,669 --> 00:19:10,870 585 00:19:10,870 --> 00:19:10,880 586 00:19:10,880 --> 00:19:11,909 587 00:19:11,909 --> 00:19:13,750 588 00:19:13,750 --> 00:19:15,590 589 00:19:15,590 --> 00:19:17,350 590 00:19:17,350 --> 00:19:19,430 591 00:19:19,430 --> 00:19:21,590 592 00:19:21,590 --> 00:19:21,600 593 00:19:21,600 --> 00:19:22,789 594 00:19:22,789 --> 00:19:24,630 595 00:19:24,630 --> 00:19:27,909 596 00:19:27,909 --> 00:19:27,919 597 00:19:27,919 --> 00:19:29,430 598 00:19:29,430 --> 00:19:31,270 599 00:19:31,270 --> 00:19:34,310 600 00:19:34,310 --> 00:19:36,630 601 00:19:36,630 --> 00:19:38,230 602 00:19:38,230 --> 00:19:39,510 603 00:19:39,510 --> 00:19:42,070 604 00:19:42,070 --> 00:19:49,590 605 00:19:49,590 --> 00:19:52,070 606 00:19:52,070 --> 00:19:53,669 607 00:19:53,669 --> 00:19:56,789 608 00:19:56,789 --> 00:19:59,029 609 00:19:59,029 --> 00:20:00,390 610 00:20:00,390 --> 00:20:03,110 611 00:20:03,110 --> 00:20:06,870 612 00:20:06,870 --> 00:20:07,990 613 00:20:07,990 --> 00:20:08,000 614 00:20:08,000 --> 00:20:10,149 615 00:20:10,149 --> 00:20:11,990 616 00:20:11,990 --> 00:20:13,669 617 00:20:13,669 --> 00:20:15,590 618 00:20:15,590 --> 00:20:17,830 619 00:20:17,830 --> 00:20:19,430 620 00:20:19,430 --> 00:20:20,950 621 00:20:20,950 --> 00:20:22,630 622 00:20:22,630 --> 00:20:24,310 623 00:20:24,310 --> 00:20:24,320 624 00:20:24,320 --> 00:20:25,350 625 00:20:25,350 --> 00:20:28,470 626 00:20:28,470 --> 00:20:30,710 627 00:20:30,710 --> 00:20:33,110 628 00:20:33,110 --> 00:20:35,750 629 00:20:35,750 --> 00:20:35,760 630 00:20:35,760 --> 00:20:38,070 631 00:20:38,070 --> 00:20:39,750 632 00:20:39,750 --> 00:20:39,760 633 00:20:39,760 --> 00:20:40,230 634 00:20:40,230 --> 00:20:40,240 635 00:20:40,240 --> 00:20:42,070 636 00:20:42,070 --> 00:20:44,390 637 00:20:44,390 --> 00:20:46,310 638 00:20:46,310 --> 00:20:46,320 639 00:20:46,320 --> 00:20:47,430 640 00:20:47,430 --> 00:20:49,350 641 00:20:49,350 --> 00:20:50,789 642 00:20:50,789 --> 00:20:52,789 643 00:20:52,789 --> 00:20:54,630 644 00:20:54,630 --> 00:20:56,710 645 00:20:56,710 --> 00:21:00,470 646 00:21:00,470 --> 00:21:01,750 647 00:21:01,750 --> 00:21:03,270 648 00:21:03,270 --> 00:21:05,990 649 00:21:05,990 --> 00:21:08,149 650 00:21:08,149 --> 00:21:08,159 651 00:21:08,159 --> 00:21:09,110 652 00:21:09,110 --> 00:21:10,950 653 00:21:10,950 --> 00:21:12,630 654 00:21:12,630 --> 00:21:14,549 655 00:21:14,549 --> 00:21:14,559 656 00:21:14,559 --> 00:21:15,669 657 00:21:15,669 --> 00:21:18,230 658 00:21:18,230 --> 00:21:20,230 659 00:21:20,230 --> 00:21:21,750 660 00:21:21,750 --> 00:21:23,350 661 00:21:23,350 --> 00:21:23,360 662 00:21:23,360 --> 00:21:24,310 663 00:21:24,310 --> 00:21:25,669 664 00:21:25,669 --> 00:21:26,870 665 00:21:26,870 --> 00:21:29,190 666 00:21:29,190 --> 00:21:32,630 667 00:21:32,630 --> 00:21:33,830 668 00:21:33,830 --> 00:21:36,549 669 00:21:36,549 --> 00:21:38,789 670 00:21:38,789 --> 00:21:40,549 671 00:21:40,549 --> 00:21:40,559 672 00:21:40,559 --> 00:21:41,669 673 00:21:41,669 --> 00:21:44,549 674 00:21:44,549 --> 00:21:45,990 675 00:21:45,990 --> 00:21:47,029 676 00:21:47,029 --> 00:21:51,590 677 00:21:51,590 --> 00:21:53,190 678 00:21:53,190 --> 00:21:55,750 679 00:21:55,750 --> 00:21:58,230 680 00:21:58,230 --> 00:22:00,870 681 00:22:00,870 --> 00:22:03,350 682 00:22:03,350 --> 00:22:06,230 683 00:22:06,230 --> 00:22:06,240 684 00:22:06,240 --> 00:22:07,590 685 00:22:07,590 --> 00:22:10,830 686 00:22:10,830 --> 00:22:13,830 687 00:22:13,830 --> 00:22:16,870 688 00:22:16,870 --> 00:22:18,710 689 00:22:18,710 --> 00:22:20,390 690 00:22:20,390 --> 00:22:22,070 691 00:22:22,070 --> 00:22:24,830 692 00:22:24,830 --> 00:22:26,789 693 00:22:26,789 --> 00:22:29,110 694 00:22:29,110 --> 00:22:29,120 695 00:22:29,120 --> 00:22:30,070 696 00:22:30,070 --> 00:22:32,310 697 00:22:32,310 --> 00:22:34,870 698 00:22:34,870 --> 00:22:36,390 699 00:22:36,390 --> 00:22:38,390 700 00:22:38,390 --> 00:22:40,789 701 00:22:40,789 --> 00:22:43,590 702 00:22:43,590 --> 00:22:43,600 703 00:22:43,600 --> 00:22:46,470 704 00:22:46,470 --> 00:22:46,480 705 00:22:46,480 --> 00:22:47,270 706 00:22:47,270 --> 00:22:49,270 707 00:22:49,270 --> 00:22:51,270 708 00:22:51,270 --> 00:22:54,390 709 00:22:54,390 --> 00:22:56,549 710 00:22:56,549 --> 00:22:58,470 711 00:22:58,470 --> 00:23:01,350 712 00:23:01,350 --> 00:23:01,360 713 00:23:01,360 --> 00:23:02,149 714 00:23:02,149 --> 00:23:02,159 715 00:23:02,159 --> 00:23:03,350 716 00:23:03,350 --> 00:23:05,430 717 00:23:05,430 --> 00:23:07,990 718 00:23:07,990 --> 00:23:09,669 719 00:23:09,669 --> 00:23:09,679 720 00:23:09,679 --> 00:23:11,669 721 00:23:11,669 --> 00:23:14,710 722 00:23:14,710 --> 00:23:16,470 723 00:23:16,470 --> 00:23:16,480 724 00:23:16,480 --> 00:23:17,990 725 00:23:17,990 --> 00:23:18,000 726 00:23:18,000 --> 00:23:19,430 727 00:23:19,430 --> 00:23:23,669 728 00:23:23,669 --> 00:23:26,470 729 00:23:26,470 --> 00:23:28,789 730 00:23:28,789 --> 00:23:30,950 731 00:23:30,950 --> 00:23:32,630 732 00:23:32,630 --> 00:23:32,640 733 00:23:32,640 --> 00:23:33,909 734 00:23:33,909 --> 00:23:36,149 735 00:23:36,149 --> 00:23:39,350 736 00:23:39,350 --> 00:23:39,360 737 00:23:39,360 --> 00:23:40,149 738 00:23:40,149 --> 00:23:41,430 739 00:23:41,430 --> 00:23:43,269 740 00:23:43,269 --> 00:23:45,750 741 00:23:45,750 --> 00:23:47,669 742 00:23:47,669 --> 00:23:49,350 743 00:23:49,350 --> 00:23:50,870 744 00:23:50,870 --> 00:23:53,110 745 00:23:53,110 --> 00:23:54,650 746 00:23:54,650 --> 00:23:54,660 747 00:23:54,660 --> 00:23:57,110 748 00:23:57,110 --> 00:23:58,950 749 00:23:58,950 --> 00:24:01,430 750 00:24:01,430 --> 00:24:03,190 751 00:24:03,190 --> 00:24:05,669 752 00:24:05,669 --> 00:24:08,070 753 00:24:08,070 --> 00:24:09,750 754 00:24:09,750 --> 00:24:11,830 755 00:24:11,830 --> 00:24:13,990 756 00:24:13,990 --> 00:24:15,350 757 00:24:15,350 --> 00:24:17,510 758 00:24:17,510 --> 00:24:19,029 759 00:24:19,029 --> 00:24:21,190 760 00:24:21,190 --> 00:24:24,789 761 00:24:24,789 --> 00:24:28,149 762 00:24:28,149 --> 00:24:28,159 763 00:24:28,159 --> 00:24:29,350 764 00:24:29,350 --> 00:24:31,510 765 00:24:31,510 --> 00:24:33,350 766 00:24:33,350 --> 00:24:35,750 767 00:24:35,750 --> 00:24:35,760 768 00:24:35,760 --> 00:24:36,789 769 00:24:36,789 --> 00:24:38,710 770 00:24:38,710 --> 00:24:39,990 771 00:24:39,990 --> 00:24:42,070 772 00:24:42,070 --> 00:24:43,750 773 00:24:43,750 --> 00:24:45,430 774 00:24:45,430 --> 00:24:50,630 775 00:24:50,630 --> 00:24:52,470 776 00:24:52,470 --> 00:24:54,390 777 00:24:54,390 --> 00:24:56,950 778 00:24:56,950 --> 00:24:58,950 779 00:24:58,950 --> 00:25:01,430 780 00:25:01,430 --> 00:25:03,430 781 00:25:03,430 --> 00:25:04,549 782 00:25:04,549 --> 00:25:07,510 783 00:25:07,510 --> 00:25:07,520 784 00:25:07,520 --> 00:25:08,630 785 00:25:08,630 --> 00:25:08,640 786 00:25:08,640 --> 00:25:09,350 787 00:25:09,350 --> 00:25:11,430 788 00:25:11,430 --> 00:25:13,029 789 00:25:13,029 --> 00:25:15,029 790 00:25:15,029 --> 00:25:16,870 791 00:25:16,870 --> 00:25:18,789 792 00:25:18,789 --> 00:25:20,630 793 00:25:20,630 --> 00:25:22,549 794 00:25:22,549 --> 00:25:25,350 795 00:25:25,350 --> 00:25:27,269 796 00:25:27,269 --> 00:25:28,470 797 00:25:28,470 --> 00:25:30,950 798 00:25:30,950 --> 00:25:31,920 799 00:25:31,920 --> 00:25:31,930 800 00:25:31,930 --> 00:25:33,110 801 00:25:33,110 --> 00:25:35,510 802 00:25:35,510 --> 00:25:37,590 803 00:25:37,590 --> 00:25:39,590 804 00:25:39,590 --> 00:25:41,269 805 00:25:41,269 --> 00:25:44,470 806 00:25:44,470 --> 00:25:46,630 807 00:25:46,630 --> 00:25:50,710 808 00:25:50,710 --> 00:25:50,720 809 00:25:50,720 --> 00:25:52,310 810 00:25:52,310 --> 00:25:55,110 811 00:25:55,110 --> 00:25:57,110 812 00:25:57,110 --> 00:25:59,110 813 00:25:59,110 --> 00:26:01,909 814 00:26:01,909 --> 00:26:03,830 815 00:26:03,830 --> 00:26:07,029 816 00:26:07,029 --> 00:26:09,350 817 00:26:09,350 --> 00:26:13,110 818 00:26:13,110 --> 00:26:16,470 819 00:26:16,470 --> 00:26:18,310 820 00:26:18,310 --> 00:26:20,630 821 00:26:20,630 --> 00:26:23,029 822 00:26:23,029 --> 00:26:24,789 823 00:26:24,789 --> 00:26:27,029 824 00:26:27,029 --> 00:26:29,110 825 00:26:29,110 --> 00:26:32,149 826 00:26:32,149 --> 00:26:32,159 827 00:26:32,159 --> 00:26:34,470 828 00:26:34,470 --> 00:26:36,470 829 00:26:36,470 --> 00:26:38,870 830 00:26:38,870 --> 00:26:42,710 831 00:26:42,710 --> 00:26:46,230 832 00:26:46,230 --> 00:26:48,870 833 00:26:48,870 --> 00:26:48,880 834 00:26:48,880 --> 00:26:50,070 835 00:26:50,070 --> 00:26:52,710 836 00:26:52,710 --> 00:26:52,720 837 00:26:52,720 --> 00:26:54,230 838 00:26:54,230 --> 00:26:54,240 839 00:26:54,240 --> 00:26:55,430 840 00:26:55,430 --> 00:26:57,430 841 00:26:57,430 --> 00:27:00,149 842 00:27:00,149 --> 00:27:01,990 843 00:27:01,990 --> 00:27:04,950 844 00:27:04,950 --> 00:27:06,549 845 00:27:06,549 --> 00:27:08,630 846 00:27:08,630 --> 00:27:10,230 847 00:27:10,230 --> 00:27:11,990 848 00:27:11,990 --> 00:27:13,909 849 00:27:13,909 --> 00:27:13,919 850 00:27:13,919 --> 00:27:15,830 851 00:27:15,830 --> 00:27:17,510 852 00:27:17,510 --> 00:27:19,350 853 00:27:19,350 --> 00:27:24,070 854 00:27:24,070 --> 00:27:27,110 855 00:27:27,110 --> 00:27:28,870 856 00:27:28,870 --> 00:27:30,389 857 00:27:30,389 --> 00:27:32,310 858 00:27:32,310 --> 00:27:33,990 859 00:27:33,990 --> 00:27:34,000 860 00:27:34,000 --> 00:27:34,870 861 00:27:34,870 --> 00:27:38,149 862 00:27:38,149 --> 00:27:40,470 863 00:27:40,470 --> 00:27:42,070 864 00:27:42,070 --> 00:27:44,389 865 00:27:44,389 --> 00:27:46,549 866 00:27:46,549 --> 00:27:47,510 867 00:27:47,510 --> 00:27:47,520 868 00:27:47,520 --> 00:27:49,430 869 00:27:49,430 --> 00:27:52,070 870 00:27:52,070 --> 00:27:53,750 871 00:27:53,750 --> 00:27:56,070 872 00:27:56,070 --> 00:27:58,710 873 00:27:58,710 --> 00:28:00,230 874 00:28:00,230 --> 00:28:04,630 875 00:28:04,630 --> 00:28:04,640 876 00:28:04,640 --> 00:28:05,830 877 00:28:05,830 --> 00:28:07,909 878 00:28:07,909 --> 00:28:09,750 879 00:28:09,750 --> 00:28:14,549 880 00:28:14,549 --> 00:28:16,470 881 00:28:16,470 --> 00:28:18,149 882 00:28:18,149 --> 00:28:18,159 883 00:28:18,159 --> 00:28:18,470 884 00:28:18,470 --> 00:28:18,480 885 00:28:18,480 --> 00:28:20,389 886 00:28:20,389 --> 00:28:20,399 887 00:28:20,399 --> 00:28:22,230 888 00:28:22,230 --> 00:28:24,789 889 00:28:24,789 --> 00:28:27,350 890 00:28:27,350 --> 00:28:29,430 891 00:28:29,430 --> 00:28:31,830 892 00:28:31,830 --> 00:28:33,669 893 00:28:33,669 --> 00:28:36,549 894 00:28:36,549 --> 00:28:36,559 895 00:28:36,559 --> 00:28:37,350 896 00:28:37,350 --> 00:28:38,870 897 00:28:38,870 --> 00:28:40,789 898 00:28:40,789 --> 00:28:42,070 899 00:28:42,070 --> 00:28:44,470 900 00:28:44,470 --> 00:28:44,480 901 00:28:44,480 --> 00:28:46,389 902 00:28:46,389 --> 00:28:50,470 903 00:28:50,470 --> 00:28:50,480 904 00:28:50,480 --> 00:28:52,149 905 00:28:52,149 --> 00:28:52,159 906 00:28:52,159 --> 00:28:54,870 907 00:28:54,870 --> 00:28:57,430 908 00:28:57,430 --> 00:29:00,310 909 00:29:00,310 --> 00:29:02,549 910 00:29:02,549 --> 00:29:04,950 911 00:29:04,950 --> 00:29:06,950 912 00:29:06,950 --> 00:29:09,830 913 00:29:09,830 --> 00:29:09,840 914 00:29:09,840 --> 00:29:11,750 915 00:29:11,750 --> 00:29:13,269 916 00:29:13,269 --> 00:29:15,909 917 00:29:15,909 --> 00:29:18,310 918 00:29:18,310 --> 00:29:20,950 919 00:29:20,950 --> 00:29:22,070 920 00:29:22,070 --> 00:29:25,190 921 00:29:25,190 --> 00:29:27,510 922 00:29:27,510 --> 00:29:29,350 923 00:29:29,350 --> 00:29:29,360 924 00:29:29,360 --> 00:29:30,470 925 00:29:30,470 --> 00:29:38,830 926 00:29:38,830 --> 00:29:42,310 927 00:29:42,310 --> 00:29:45,350 928 00:29:45,350 --> 00:29:47,350 929 00:29:47,350 --> 00:29:49,750 930 00:29:49,750 --> 00:29:49,760 931 00:29:49,760 --> 00:29:50,549 932 00:29:50,549 --> 00:29:53,190 933 00:29:53,190 --> 00:30:01,510 934 00:30:01,510 --> 00:30:03,269 935 00:30:03,269 --> 00:30:03,279 936 00:30:03,279 --> 00:30:04,549 937 00:30:04,549 --> 00:30:07,510 938 00:30:07,510 --> 00:30:09,510 939 00:30:09,510 --> 00:30:12,870 940 00:30:12,870 --> 00:30:15,029 941 00:30:15,029 --> 00:30:17,350 942 00:30:17,350 --> 00:30:18,789 943 00:30:18,789 --> 00:30:18,799 944 00:30:18,799 --> 00:30:19,669 945 00:30:19,669 --> 00:30:23,430 946 00:30:23,430 --> 00:30:29,750 947 00:30:29,750 --> 00:30:29,760 948 00:30:29,760 --> 00:30:30,789 949 00:30:30,789 --> 00:30:30,799 950 00:30:30,799 --> 00:30:35,029 951 00:30:35,029 --> 00:30:36,630 952 00:30:36,630 --> 00:30:38,230 953 00:30:38,230 --> 00:30:39,830 954 00:30:39,830 --> 00:30:39,840 955 00:30:39,840 --> 00:30:41,110 956 00:30:41,110 --> 00:30:42,630 957 00:30:42,630 --> 00:30:45,190 958 00:30:45,190 --> 00:30:45,200 959 00:30:45,200 --> 00:30:46,230 960 00:30:46,230 --> 00:30:47,909 961 00:30:47,909 --> 00:30:50,710 962 00:30:50,710 --> 00:30:53,029 963 00:30:53,029 --> 00:30:54,630 964 00:30:54,630 --> 00:30:56,630 965 00:30:56,630 --> 00:30:58,070 966 00:30:58,070 --> 00:31:02,149 967 00:31:02,149 --> 00:31:02,159 968 00:31:02,159 --> 00:31:03,430 969 00:31:03,430 --> 00:31:04,870 970 00:31:04,870 --> 00:31:07,029 971 00:31:07,029 --> 00:31:08,470 972 00:31:08,470 --> 00:31:10,549 973 00:31:10,549 --> 00:31:14,149 974 00:31:14,149 --> 00:31:16,230 975 00:31:16,230 --> 00:31:18,070 976 00:31:18,070 --> 00:31:20,630 977 00:31:20,630 --> 00:31:20,640 978 00:31:20,640 --> 00:31:21,669 979 00:31:21,669 --> 00:31:23,190 980 00:31:23,190 --> 00:31:23,200 981 00:31:23,200 --> 00:31:24,950 982 00:31:24,950 --> 00:31:24,960 983 00:31:24,960 --> 00:31:26,950 984 00:31:26,950 --> 00:31:28,470 985 00:31:28,470 --> 00:31:28,480 986 00:31:28,480 --> 00:31:29,990 987 00:31:29,990 --> 00:31:32,870 988 00:31:32,870 --> 00:31:35,990 989 00:31:35,990 --> 00:31:36,000 990 00:31:36,000 --> 00:31:38,070 991 00:31:38,070 --> 00:31:40,549 992 00:31:40,549 --> 00:31:40,559 993 00:31:40,559 --> 00:31:41,669 994 00:31:41,669 --> 00:31:44,389 995 00:31:44,389 --> 00:31:46,789 996 00:31:46,789 --> 00:31:48,070 997 00:31:48,070 --> 00:31:50,389 998 00:31:50,389 --> 00:31:52,870 999 00:31:52,870 --> 00:31:54,549 1000 00:31:54,549 --> 00:31:55,909 1001 00:31:55,909 --> 00:31:57,909 1002 00:31:57,909 --> 00:31:59,669 1003 00:31:59,669 --> 00:32:01,269 1004 00:32:01,269 --> 00:32:03,269 1005 00:32:03,269 --> 00:32:03,279 1006 00:32:03,279 --> 00:32:04,310 1007 00:32:04,310 --> 00:32:06,870 1008 00:32:06,870 --> 00:32:08,070 1009 00:32:08,070 --> 00:32:09,909 1010 00:32:09,909 --> 00:32:11,909 1011 00:32:11,909 --> 00:32:15,029 1012 00:32:15,029 --> 00:32:20,470 1013 00:32:20,470 --> 00:32:25,590 1014 00:32:25,590 --> 00:32:27,269 1015 00:32:27,269 --> 00:32:30,149 1016 00:32:30,149 --> 00:32:33,990 1017 00:32:33,990 --> 00:32:35,430 1018 00:32:35,430 --> 00:32:39,350 1019 00:32:39,350 --> 00:32:40,710 1020 00:32:40,710 --> 00:32:40,720 1021 00:32:40,720 --> 00:32:41,509 1022 00:32:41,509 --> 00:32:42,470 1023 00:32:42,470 --> 00:32:42,480 1024 00:32:42,480 --> 00:32:44,070 1025 00:32:44,070 --> 00:32:48,549 1026 00:32:48,549 --> 00:32:52,070 1027 00:32:52,070 --> 00:32:52,080 1028 00:32:52,080 --> 00:32:53,110 1029 00:32:53,110 --> 00:32:53,120 1030 00:32:53,120 --> 00:32:54,789 1031 00:32:54,789 --> 00:32:54,799 1032 00:32:54,799 --> 00:32:57,269 1033 00:32:57,269 --> 00:32:59,110 1034 00:32:59,110 --> 00:33:01,350 1035 00:33:01,350 --> 00:33:03,350 1036 00:33:03,350 --> 00:33:06,310 1037 00:33:06,310 --> 00:33:08,710 1038 00:33:08,710 --> 00:33:10,789 1039 00:33:10,789 --> 00:33:10,799 1040 00:33:10,799 --> 00:33:11,990 1041 00:33:11,990 --> 00:33:13,430 1042 00:33:13,430 --> 00:33:15,990 1043 00:33:15,990 --> 00:33:19,190 1044 00:33:19,190 --> 00:33:21,509 1045 00:33:21,509 --> 00:33:22,630 1046 00:33:22,630 --> 00:33:25,110 1047 00:33:25,110 --> 00:33:28,549 1048 00:33:28,549 --> 00:33:30,950 1049 00:33:30,950 --> 00:33:30,960 1050 00:33:30,960 --> 00:33:31,909 1051 00:33:31,909 --> 00:33:33,669 1052 00:33:33,669 --> 00:33:35,750 1053 00:33:35,750 --> 00:33:37,830 1054 00:33:37,830 --> 00:33:37,840 1055 00:33:37,840 --> 00:33:38,789 1056 00:33:38,789 --> 00:33:41,830 1057 00:33:41,830 --> 00:33:46,149 1058 00:33:46,149 --> 00:33:47,509 1059 00:33:47,509 --> 00:33:49,029 1060 00:33:49,029 --> 00:33:53,430 1061 00:33:53,430 --> 00:33:57,350 1062 00:33:57,350 --> 00:33:59,430 1063 00:33:59,430 --> 00:34:01,190 1064 00:34:01,190 --> 00:34:04,830 1065 00:34:04,830 --> 00:34:04,840 1066 00:34:04,840 --> 00:34:06,549 1067 00:34:06,549 --> 00:34:08,310 1068 00:34:08,310 --> 00:34:10,629 1069 00:34:10,629 --> 00:34:12,470 1070 00:34:12,470 --> 00:34:12,480 1071 00:34:12,480 --> 00:34:13,510 1072 00:34:13,510 --> 00:34:13,520 1073 00:34:13,520 --> 00:34:14,470 1074 00:34:14,470 --> 00:34:17,669 1075 00:34:17,669 --> 00:34:18,629 1076 00:34:18,629 --> 00:34:21,510 1077 00:34:21,510 --> 00:34:24,790 1078 00:34:24,790 --> 00:34:26,310 1079 00:34:26,310 --> 00:34:29,510 1080 00:34:29,510 --> 00:34:31,349 1081 00:34:31,349 --> 00:34:32,389 1082 00:34:32,389 --> 00:34:36,230 1083 00:34:36,230 --> 00:34:36,240 1084 00:34:36,240 --> 00:34:42,629 1085 00:34:42,629 --> 00:34:44,470 1086 00:34:44,470 --> 00:34:45,990 1087 00:34:45,990 --> 00:34:47,990 1088 00:34:47,990 --> 00:34:49,909 1089 00:34:49,909 --> 00:34:51,190 1090 00:34:51,190 --> 00:34:53,510 1091 00:34:53,510 --> 00:34:55,829 1092 00:34:55,829 --> 00:34:57,030 1093 00:34:57,030 --> 00:35:00,230 1094 00:35:00,230 --> 00:35:03,190 1095 00:35:03,190 --> 00:35:05,589 1096 00:35:05,589 --> 00:35:08,150 1097 00:35:08,150 --> 00:35:10,390 1098 00:35:10,390 --> 00:35:11,670 1099 00:35:11,670 --> 00:35:14,630 1100 00:35:14,630 --> 00:35:16,710 1101 00:35:16,710 --> 00:35:18,550 1102 00:35:18,550 --> 00:35:20,550 1103 00:35:20,550 --> 00:35:20,560 1104 00:35:20,560 --> 00:35:21,270 1105 00:35:21,270 --> 00:35:23,030 1106 00:35:23,030 --> 00:35:25,109 1107 00:35:25,109 --> 00:35:26,230 1108 00:35:26,230 --> 00:35:29,750 1109 00:35:29,750 --> 00:35:33,030 1110 00:35:33,030 --> 00:35:34,470 1111 00:35:34,470 --> 00:35:36,950 1112 00:35:36,950 --> 00:35:41,990 1113 00:35:41,990 --> 00:35:42,000 1114 00:35:42,000 --> 00:35:42,829 1115 00:35:42,829 --> 00:35:46,150 1116 00:35:46,150 --> 00:35:46,160 1117 00:35:46,160 --> 00:35:47,270 1118 00:35:47,270 --> 00:35:49,270 1119 00:35:49,270 --> 00:35:49,280 1120 00:35:49,280 --> 00:35:50,310 1121 00:35:50,310 --> 00:35:52,390 1122 00:35:52,390 --> 00:35:54,870 1123 00:35:54,870 --> 00:35:56,710 1124 00:35:56,710 --> 00:35:58,630 1125 00:35:58,630 --> 00:36:01,190 1126 00:36:01,190 --> 00:36:01,200 1127 00:36:01,200 --> 00:36:03,109 1128 00:36:03,109 --> 00:36:05,829 1129 00:36:05,829 --> 00:36:05,839 1130 00:36:05,839 --> 00:36:07,589 1131 00:36:07,589 --> 00:36:09,349 1132 00:36:09,349 --> 00:36:13,270 1133 00:36:13,270 --> 00:36:15,829 1134 00:36:15,829 --> 00:36:15,839 1135 00:36:15,839 --> 00:36:16,790 1136 00:36:16,790 --> 00:36:21,829 1137 00:36:21,829 --> 00:36:24,470 1138 00:36:24,470 --> 00:36:26,630 1139 00:36:26,630 --> 00:36:28,710 1140 00:36:28,710 --> 00:36:30,310 1141 00:36:30,310 --> 00:36:32,950 1142 00:36:32,950 --> 00:36:35,589 1143 00:36:35,589 --> 00:36:36,550 1144 00:36:36,550 --> 00:36:38,069 1145 00:36:38,069 --> 00:36:40,790 1146 00:36:40,790 --> 00:36:42,150 1147 00:36:42,150 --> 00:36:44,150 1148 00:36:44,150 --> 00:36:45,990 1149 00:36:45,990 --> 00:36:48,710 1150 00:36:48,710 --> 00:36:48,720 1151 00:36:48,720 --> 00:36:49,670 1152 00:36:49,670 --> 00:36:52,790 1153 00:36:52,790 --> 00:36:55,910 1154 00:36:55,910 --> 00:36:58,550 1155 00:36:58,550 --> 00:37:00,870 1156 00:37:00,870 --> 00:37:02,230 1157 00:37:02,230 --> 00:37:03,750 1158 00:37:03,750 --> 00:37:06,829 1159 00:37:06,829 --> 00:37:14,630 1160 00:37:14,630 --> 00:37:17,109 1161 00:37:17,109 --> 00:37:18,710 1162 00:37:18,710 --> 00:37:20,710 1163 00:37:20,710 --> 00:37:22,150 1164 00:37:22,150 --> 00:37:23,430 1165 00:37:23,430 --> 00:37:25,190 1166 00:37:25,190 --> 00:37:27,670 1167 00:37:27,670 --> 00:37:28,870 1168 00:37:28,870 --> 00:37:30,230 1169 00:37:30,230 --> 00:37:31,510 1170 00:37:31,510 --> 00:37:33,750 1171 00:37:33,750 --> 00:37:35,750 1172 00:37:35,750 --> 00:37:37,510 1173 00:37:37,510 --> 00:37:37,520 1174 00:37:37,520 --> 00:37:38,310 1175 00:37:38,310 --> 00:37:40,230 1176 00:37:40,230 --> 00:37:42,390 1177 00:37:42,390 --> 00:37:44,630 1178 00:37:44,630 --> 00:37:46,230 1179 00:37:46,230 --> 00:37:48,470 1180 00:37:48,470 --> 00:37:50,470 1181 00:37:50,470 --> 00:37:51,670 1182 00:37:51,670 --> 00:37:54,150 1183 00:37:54,150 --> 00:37:55,990 1184 00:37:55,990 --> 00:37:58,150 1185 00:37:58,150 --> 00:37:58,160 1186 00:37:58,160 --> 00:37:59,190 1187 00:37:59,190 --> 00:38:01,829 1188 00:38:01,829 --> 00:38:01,839 1189 00:38:01,839 --> 00:38:04,310 1190 00:38:04,310 --> 00:38:05,990 1191 00:38:05,990 --> 00:38:07,829 1192 00:38:07,829 --> 00:38:09,430 1193 00:38:09,430 --> 00:38:11,510 1194 00:38:11,510 --> 00:38:11,520 1195 00:38:11,520 --> 00:38:14,310 1196 00:38:14,310 --> 00:38:14,320 1197 00:38:14,320 --> 00:38:15,510 1198 00:38:15,510 --> 00:38:16,630 1199 00:38:16,630 --> 00:38:18,390 1200 00:38:18,390 --> 00:38:21,270 1201 00:38:21,270 --> 00:38:24,630 1202 00:38:24,630 --> 00:38:26,630 1203 00:38:26,630 --> 00:38:28,550 1204 00:38:28,550 --> 00:38:30,790 1205 00:38:30,790 --> 00:38:33,510 1206 00:38:33,510 --> 00:38:36,150 1207 00:38:36,150 --> 00:38:36,160 1208 00:38:36,160 --> 00:38:37,750 1209 00:38:37,750 --> 00:38:39,349 1210 00:38:39,349 --> 00:38:40,790 1211 00:38:40,790 --> 00:38:40,800 1212 00:38:40,800 --> 00:38:47,750 1213 00:38:47,750 --> 00:38:49,589 1214 00:38:49,589 --> 00:38:51,510 1215 00:38:51,510 --> 00:38:53,030 1216 00:38:53,030 --> 00:38:55,990 1217 00:38:55,990 --> 00:38:57,510 1218 00:38:57,510 --> 00:38:57,520 1219 00:38:57,520 --> 00:38:58,829 1220 00:38:58,829 --> 00:39:02,310 1221 00:39:02,310 --> 00:39:04,230 1222 00:39:04,230 --> 00:39:06,950 1223 00:39:06,950 --> 00:39:12,829 1224 00:39:12,829 --> 00:39:12,839 1225 00:39:12,839 --> 00:39:14,470 1226 00:39:14,470 --> 00:39:16,230 1227 00:39:16,230 --> 00:39:18,870 1228 00:39:18,870 --> 00:39:21,430 1229 00:39:21,430 --> 00:39:23,190 1230 00:39:23,190 --> 00:39:25,910 1231 00:39:25,910 --> 00:39:26,870 1232 00:39:26,870 --> 00:39:28,710 1233 00:39:28,710 --> 00:39:31,270 1234 00:39:31,270 --> 00:39:32,950 1235 00:39:32,950 --> 00:39:35,510 1236 00:39:35,510 --> 00:39:36,950 1237 00:39:36,950 --> 00:39:38,470 1238 00:39:38,470 --> 00:39:40,230 1239 00:39:40,230 --> 00:39:43,750 1240 00:39:43,750 --> 00:39:45,829 1241 00:39:45,829 --> 00:39:47,750 1242 00:39:47,750 --> 00:39:49,829 1243 00:39:49,829 --> 00:39:51,829 1244 00:39:51,829 --> 00:39:54,230 1245 00:39:54,230 --> 00:39:56,550 1246 00:39:56,550 --> 00:39:58,550 1247 00:39:58,550 --> 00:40:00,550 1248 00:40:00,550 --> 00:40:02,630 1249 00:40:02,630 --> 00:40:07,030 1250 00:40:07,030 --> 00:40:09,030 1251 00:40:09,030 --> 00:40:10,550 1252 00:40:10,550 --> 00:40:14,309 1253 00:40:14,309 --> 00:40:15,589 1254 00:40:15,589 --> 00:40:17,750 1255 00:40:17,750 --> 00:40:18,790 1256 00:40:18,790 --> 00:40:18,800 1257 00:40:18,800 --> 00:40:21,589 1258 00:40:21,589 --> 00:40:23,109 1259 00:40:23,109 --> 00:40:23,119 1260 00:40:23,119 --> 00:40:24,710 1261 00:40:24,710 --> 00:40:27,670 1262 00:40:27,670 --> 00:40:29,829 1263 00:40:29,829 --> 00:40:31,990 1264 00:40:31,990 --> 00:40:33,030 1265 00:40:33,030 --> 00:40:35,109 1266 00:40:35,109 --> 00:40:36,790 1267 00:40:36,790 --> 00:40:38,390 1268 00:40:38,390 --> 00:40:41,670 1269 00:40:41,670 --> 00:40:43,910 1270 00:40:43,910 --> 00:40:47,030 1271 00:40:47,030 --> 00:40:51,030 1272 00:40:51,030 --> 00:40:52,790 1273 00:40:52,790 --> 00:40:54,550 1274 00:40:54,550 --> 00:40:55,910 1275 00:40:55,910 --> 00:40:55,920 1276 00:40:55,920 --> 00:40:57,430 1277 00:40:57,430 --> 00:40:59,910 1278 00:40:59,910 --> 00:41:02,309 1279 00:41:02,309 --> 00:41:04,150 1280 00:41:04,150 --> 00:41:06,790 1281 00:41:06,790 --> 00:41:09,030 1282 00:41:09,030 --> 00:41:10,870 1283 00:41:10,870 --> 00:41:13,510 1284 00:41:13,510 --> 00:41:16,150 1285 00:41:16,150 --> 00:41:17,990 1286 00:41:17,990 --> 00:41:19,510 1287 00:41:19,510 --> 00:41:21,670 1288 00:41:21,670 --> 00:41:23,829 1289 00:41:23,829 --> 00:41:25,750 1290 00:41:25,750 --> 00:41:27,349 1291 00:41:27,349 --> 00:41:30,390 1292 00:41:30,390 --> 00:41:33,270 1293 00:41:33,270 --> 00:41:35,829 1294 00:41:35,829 --> 00:41:37,510 1295 00:41:37,510 --> 00:41:37,520 1296 00:41:37,520 --> 00:41:38,710 1297 00:41:38,710 --> 00:41:41,430 1298 00:41:41,430 --> 00:41:41,440 1299 00:41:41,440 --> 00:41:43,109 1300 00:41:43,109 --> 00:41:44,870 1301 00:41:44,870 --> 00:41:44,880 1302 00:41:44,880 --> 00:41:45,750 1303 00:41:45,750 --> 00:41:47,270 1304 00:41:47,270 --> 00:41:49,510 1305 00:41:49,510 --> 00:41:51,349 1306 00:41:51,349 --> 00:41:53,109 1307 00:41:53,109 --> 00:41:53,119 1308 00:41:53,119 --> 00:41:54,550 1309 00:41:54,550 --> 00:41:54,560 1310 00:41:54,560 --> 00:41:55,990 1311 00:41:55,990 --> 00:41:57,829 1312 00:41:57,829 --> 00:42:00,230 1313 00:42:00,230 --> 00:42:03,190 1314 00:42:03,190 --> 00:42:03,200 1315 00:42:03,200 --> 00:42:04,309 1316 00:42:04,309 --> 00:42:04,319 1317 00:42:04,319 --> 00:42:06,630 1318 00:42:06,630 --> 00:42:08,230 1319 00:42:08,230 --> 00:42:10,510 1320 00:42:10,510 --> 00:42:13,270 1321 00:42:13,270 --> 00:42:14,790 1322 00:42:14,790 --> 00:42:16,390 1323 00:42:16,390 --> 00:42:18,870 1324 00:42:18,870 --> 00:42:21,190 1325 00:42:21,190 --> 00:42:22,069 1326 00:42:22,069 --> 00:42:25,750 1327 00:42:25,750 --> 00:42:25,760 1328 00:42:25,760 --> 00:42:27,030 1329 00:42:27,030 --> 00:42:28,630 1330 00:42:28,630 --> 00:42:30,069 1331 00:42:30,069 --> 00:42:32,230 1332 00:42:32,230 --> 00:42:34,390 1333 00:42:34,390 --> 00:42:35,829 1334 00:42:35,829 --> 00:42:37,829 1335 00:42:37,829 --> 00:42:40,630 1336 00:42:40,630 --> 00:42:41,750 1337 00:42:41,750 --> 00:42:45,109 1338 00:42:45,109 --> 00:42:47,670 1339 00:42:47,670 --> 00:42:49,510 1340 00:42:49,510 --> 00:42:51,750 1341 00:42:51,750 --> 00:42:53,430 1342 00:42:53,430 --> 00:42:56,069 1343 00:42:56,069 --> 00:42:57,510 1344 00:42:57,510 --> 00:42:58,470 1345 00:42:58,470 --> 00:43:00,309 1346 00:43:00,309 --> 00:43:04,309 1347 00:43:04,309 --> 00:43:05,990 1348 00:43:05,990 --> 00:43:06,000 1349 00:43:06,000 --> 00:43:07,270 1350 00:43:07,270 --> 00:43:10,230 1351 00:43:10,230 --> 00:43:12,630 1352 00:43:12,630 --> 00:43:14,550 1353 00:43:14,550 --> 00:43:17,030 1354 00:43:17,030 --> 00:43:19,190 1355 00:43:19,190 --> 00:43:21,670 1356 00:43:21,670 --> 00:43:21,680 1357 00:43:21,680 --> 00:43:22,710 1358 00:43:22,710 --> 00:43:24,710 1359 00:43:24,710 --> 00:43:24,720 1360 00:43:24,720 --> 00:43:25,910 1361 00:43:25,910 --> 00:43:27,750 1362 00:43:27,750 --> 00:43:27,760 1363 00:43:27,760 --> 00:43:29,030 1364 00:43:29,030 --> 00:43:31,589 1365 00:43:31,589 --> 00:43:33,510 1366 00:43:33,510 --> 00:43:35,910 1367 00:43:35,910 --> 00:43:37,750 1368 00:43:37,750 --> 00:43:40,230 1369 00:43:40,230 --> 00:43:42,950 1370 00:43:42,950 --> 00:43:45,030 1371 00:43:45,030 --> 00:43:47,190 1372 00:43:47,190 --> 00:43:47,200 1373 00:43:47,200 --> 00:43:48,470 1374 00:43:48,470 --> 00:43:51,270 1375 00:43:51,270 --> 00:43:53,270 1376 00:43:53,270 --> 00:43:55,510 1377 00:43:55,510 --> 00:43:57,190 1378 00:43:57,190 --> 00:43:57,200 1379 00:43:57,200 --> 00:43:58,309 1380 00:43:58,309 --> 00:43:58,319 1381 00:43:58,319 --> 00:43:59,910 1382 00:43:59,910 --> 00:44:01,750 1383 00:44:01,750 --> 00:44:03,589 1384 00:44:03,589 --> 00:44:05,349 1385 00:44:05,349 --> 00:44:08,630 1386 00:44:08,630 --> 00:44:08,640 1387 00:44:08,640 --> 00:44:09,750 1388 00:44:09,750 --> 00:44:12,150 1389 00:44:12,150 --> 00:44:12,160 1390 00:44:12,160 --> 00:44:14,630 1391 00:44:14,630 --> 00:44:17,750 1392 00:44:17,750 --> 00:44:17,760 1393 00:44:17,760 --> 00:44:19,109 1394 00:44:19,109 --> 00:44:20,870 1395 00:44:20,870 --> 00:44:24,230 1396 00:44:24,230 --> 00:44:26,950 1397 00:44:26,950 --> 00:44:28,550 1398 00:44:28,550 --> 00:44:31,270 1399 00:44:31,270 --> 00:44:33,829 1400 00:44:33,829 --> 00:44:37,270 1401 00:44:37,270 --> 00:44:37,280 1402 00:44:37,280 --> 00:44:38,950 1403 00:44:38,950 --> 00:44:41,270 1404 00:44:41,270 --> 00:44:41,280 1405 00:44:41,280 --> 00:44:43,430 1406 00:44:43,430 --> 00:44:43,440 1407 00:44:43,440 --> 00:44:44,390 1408 00:44:44,390 --> 00:44:46,309 1409 00:44:46,309 --> 00:44:50,870 1410 00:44:50,870 --> 00:44:52,069 1411 00:44:52,069 --> 00:44:55,349 1412 00:44:55,349 --> 00:44:57,349 1413 00:44:57,349 --> 00:44:59,910 1414 00:44:59,910 --> 00:44:59,920 1415 00:44:59,920 --> 00:45:00,950 1416 00:45:00,950 --> 00:45:04,870 1417 00:45:04,870 --> 00:45:04,880 1418 00:45:04,880 --> 00:45:06,309 1419 00:45:06,309 --> 00:45:07,520 1420 00:45:07,520 --> 00:45:07,530 1421 00:45:07,530 --> 00:45:09,910 1422 00:45:09,910 --> 00:45:11,829 1423 00:45:11,829 --> 00:45:13,109 1424 00:45:13,109 --> 00:45:14,950 1425 00:45:14,950 --> 00:45:18,950 1426 00:45:18,950 --> 00:45:21,510 1427 00:45:21,510 --> 00:45:23,910 1428 00:45:23,910 --> 00:45:25,829 1429 00:45:25,829 --> 00:45:27,030 1430 00:45:27,030 --> 00:45:29,829 1431 00:45:29,829 --> 00:45:29,839 1432 00:45:29,839 --> 00:45:31,750 1433 00:45:31,750 --> 00:45:31,760 1434 00:45:31,760 --> 00:45:32,390 1435 00:45:32,390 --> 00:45:34,550 1436 00:45:34,550 --> 00:45:36,790 1437 00:45:36,790 --> 00:45:38,870 1438 00:45:38,870 --> 00:45:41,750 1439 00:45:41,750 --> 00:45:41,760 1440 00:45:41,760 --> 00:45:44,069 1441 00:45:44,069 --> 00:45:44,079 1442 00:45:44,079 --> 00:45:45,030 1443 00:45:45,030 --> 00:45:46,550 1444 00:45:46,550 --> 00:45:48,470 1445 00:45:48,470 --> 00:45:50,960 1446 00:45:50,960 --> 00:45:50,970 1447 00:45:50,970 --> 00:45:52,950 1448 00:45:52,950 --> 00:45:52,960 1449 00:45:52,960 --> 00:45:54,069 1450 00:45:54,069 --> 00:45:55,829 1451 00:45:55,829 --> 00:45:57,270 1452 00:45:57,270 --> 00:45:58,710 1453 00:45:58,710 --> 00:46:01,430 1454 00:46:01,430 --> 00:46:01,440 1455 00:46:01,440 --> 00:46:03,670 1456 00:46:03,670 --> 00:46:05,270 1457 00:46:05,270 --> 00:46:07,910 1458 00:46:07,910 --> 00:46:10,630 1459 00:46:10,630 --> 00:46:12,550 1460 00:46:12,550 --> 00:46:14,870 1461 00:46:14,870 --> 00:46:18,150 1462 00:46:18,150 --> 00:46:18,160 1463 00:46:18,160 --> 00:46:22,160 1464 00:46:22,160 --> 00:46:22,170 1465 00:46:22,170 --> 00:46:26,230 1466 00:46:26,230 --> 00:46:28,230 1467 00:46:28,230 --> 00:46:30,630 1468 00:46:30,630 --> 00:46:33,510 1469 00:46:33,510 --> 00:46:34,550 1470 00:46:34,550 --> 00:46:36,550 1471 00:46:36,550 --> 00:46:37,990 1472 00:46:37,990 --> 00:46:38,000 1473 00:46:38,000 --> 00:46:38,790 1474 00:46:38,790 --> 00:46:38,800 1475 00:46:38,800 --> 00:46:40,309 1476 00:46:40,309 --> 00:46:42,950 1477 00:46:42,950 --> 00:46:42,960 1478 00:46:42,960 --> 00:46:43,829 1479 00:46:43,829 --> 00:46:45,589 1480 00:46:45,589 --> 00:46:47,510 1481 00:46:47,510 --> 00:46:48,950 1482 00:46:48,950 --> 00:46:51,430 1483 00:46:51,430 --> 00:46:53,750 1484 00:46:53,750 --> 00:46:56,950 1485 00:46:56,950 --> 00:46:59,430 1486 00:46:59,430 --> 00:47:01,349 1487 00:47:01,349 --> 00:47:03,030 1488 00:47:03,030 --> 00:47:04,950 1489 00:47:04,950 --> 00:47:06,309 1490 00:47:06,309 --> 00:47:08,470 1491 00:47:08,470 --> 00:47:09,670 1492 00:47:09,670 --> 00:47:12,550 1493 00:47:12,550 --> 00:47:14,069 1494 00:47:14,069 --> 00:47:16,550 1495 00:47:16,550 --> 00:47:19,109 1496 00:47:19,109 --> 00:47:21,270 1497 00:47:21,270 --> 00:47:23,030 1498 00:47:23,030 --> 00:47:24,390 1499 00:47:24,390 --> 00:47:26,390 1500 00:47:26,390 --> 00:47:29,589 1501 00:47:29,589 --> 00:47:31,750 1502 00:47:31,750 --> 00:47:33,750 1503 00:47:33,750 --> 00:47:35,990 1504 00:47:35,990 --> 00:47:37,589 1505 00:47:37,589 --> 00:47:38,549 1506 00:47:38,549 --> 00:47:40,230 1507 00:47:40,230 --> 00:47:42,870 1508 00:47:42,870 --> 00:47:44,390 1509 00:47:44,390 --> 00:47:47,750 1510 00:47:47,750 --> 00:47:47,760 1511 00:47:47,760 --> 00:47:49,030 1512 00:47:49,030 --> 00:47:51,430 1513 00:47:51,430 --> 00:47:53,990 1514 00:47:53,990 --> 00:47:56,150 1515 00:47:56,150 --> 00:47:57,510 1516 00:47:57,510 --> 00:47:59,270 1517 00:47:59,270 --> 00:48:01,190 1518 00:48:01,190 --> 00:48:02,710 1519 00:48:02,710 --> 00:48:04,549 1520 00:48:04,549 --> 00:48:07,349 1521 00:48:07,349 --> 00:48:08,710 1522 00:48:08,710 --> 00:48:11,589 1523 00:48:11,589 --> 00:48:14,069 1524 00:48:14,069 --> 00:48:16,309 1525 00:48:16,309 --> 00:48:16,319 1526 00:48:16,319 --> 00:48:17,750 1527 00:48:17,750 --> 00:48:17,760 1528 00:48:17,760 --> 00:48:19,589 1529 00:48:19,589 --> 00:48:22,069 1530 00:48:22,069 --> 00:48:23,270 1531 00:48:23,270 --> 00:48:26,549 1532 00:48:26,549 --> 00:48:29,190 1533 00:48:29,190 --> 00:48:31,030 1534 00:48:31,030 --> 00:48:32,069 1535 00:48:32,069 --> 00:48:34,790 1536 00:48:34,790 --> 00:48:35,990 1537 00:48:35,990 --> 00:48:37,990 1538 00:48:37,990 --> 00:48:41,030 1539 00:48:41,030 --> 00:48:42,710 1540 00:48:42,710 --> 00:48:42,720 1541 00:48:42,720 --> 00:48:43,829 1542 00:48:43,829 --> 00:48:45,109 1543 00:48:45,109 --> 00:48:46,630 1544 00:48:46,630 --> 00:48:46,640 1545 00:48:46,640 --> 00:48:49,109 1546 00:48:49,109 --> 00:48:49,119 1547 00:48:49,119 --> 00:48:53,270 1548 00:48:53,270 --> 00:48:55,510 1549 00:48:55,510 --> 00:48:58,390 1550 00:48:58,390 --> 00:49:00,630 1551 00:49:00,630 --> 00:49:03,109 1552 00:49:03,109 --> 00:49:03,119 1553 00:49:03,119 --> 00:49:04,470 1554 00:49:04,470 --> 00:49:06,150 1555 00:49:06,150 --> 00:49:08,309 1556 00:49:08,309 --> 00:49:10,150 1557 00:49:10,150 --> 00:49:12,710 1558 00:49:12,710 --> 00:49:14,870 1559 00:49:14,870 --> 00:49:16,870 1560 00:49:16,870 --> 00:49:19,510 1561 00:49:19,510 --> 00:49:20,870 1562 00:49:20,870 --> 00:49:22,630 1563 00:49:22,630 --> 00:49:24,230 1564 00:49:24,230 --> 00:49:26,230 1565 00:49:26,230 --> 00:49:27,829 1566 00:49:27,829 --> 00:49:32,230 1567 00:49:32,230 --> 00:49:34,470 1568 00:49:34,470 --> 00:49:39,670 1569 00:49:39,670 --> 00:49:41,990 1570 00:49:41,990 --> 00:49:43,270 1571 00:49:43,270 --> 00:49:45,349 1572 00:49:45,349 --> 00:49:48,950 1573 00:49:48,950 --> 00:49:49,829 1574 00:49:49,829 --> 00:49:51,349 1575 00:49:51,349 --> 00:49:51,359 1576 00:49:51,359 --> 00:49:53,030 1577 00:49:53,030 --> 00:49:55,670 1578 00:49:55,670 --> 00:49:57,349 1579 00:49:57,349 --> 00:49:58,790 1580 00:49:58,790 --> 00:50:00,950 1581 00:50:00,950 --> 00:50:02,309 1582 00:50:02,309 --> 00:50:03,910 1583 00:50:03,910 --> 00:50:05,910 1584 00:50:05,910 --> 00:50:07,109 1585 00:50:07,109 --> 00:50:09,750 1586 00:50:09,750 --> 00:50:11,670 1587 00:50:11,670 --> 00:50:11,680 1588 00:50:11,680 --> 00:50:12,549 1589 00:50:12,549 --> 00:50:15,829 1590 00:50:15,829 --> 00:50:18,230 1591 00:50:18,230 --> 00:50:22,150 1592 00:50:22,150 --> 00:50:25,829 1593 00:50:25,829 --> 00:50:27,750 1594 00:50:27,750 --> 00:50:27,760 1595 00:50:27,760 --> 00:50:28,630 1596 00:50:28,630 --> 00:50:31,190 1597 00:50:31,190 --> 00:50:31,200 1598 00:50:31,200 --> 00:50:32,150 1599 00:50:32,150 --> 00:50:34,950 1600 00:50:34,950 --> 00:50:37,430 1601 00:50:37,430 --> 00:50:39,349 1602 00:50:39,349 --> 00:50:41,589 1603 00:50:41,589 --> 00:50:44,549 1604 00:50:44,549 --> 00:50:45,990 1605 00:50:45,990 --> 00:50:47,750 1606 00:50:47,750 --> 00:50:50,390 1607 00:50:50,390 --> 00:50:51,670 1608 00:50:51,670 --> 00:50:53,589 1609 00:50:53,589 --> 00:50:56,390 1610 00:50:56,390 --> 00:50:58,549 1611 00:50:58,549 --> 00:51:00,390 1612 00:51:00,390 --> 00:51:02,390 1613 00:51:02,390 --> 00:51:05,270 1614 00:51:05,270 --> 00:51:08,390 1615 00:51:08,390 --> 00:51:08,400 1616 00:51:08,400 --> 00:51:09,270 1617 00:51:09,270 --> 00:51:11,750 1618 00:51:11,750 --> 00:51:11,760 1619 00:51:11,760 --> 00:51:12,870 1620 00:51:12,870 --> 00:51:12,880 1621 00:51:12,880 --> 00:51:14,549 1622 00:51:14,549 --> 00:51:15,910 1623 00:51:15,910 --> 00:51:18,069 1624 00:51:18,069 --> 00:51:20,790 1625 00:51:20,790 --> 00:51:22,950 1626 00:51:22,950 --> 00:51:25,349 1627 00:51:25,349 --> 00:51:27,270 1628 00:51:27,270 --> 00:51:27,280 1629 00:51:27,280 --> 00:51:28,549 1630 00:51:28,549 --> 00:51:30,309 1631 00:51:30,309 --> 00:51:30,319 1632 00:51:30,319 --> 00:51:31,910 1633 00:51:31,910 --> 00:51:34,870 1634 00:51:34,870 --> 00:51:36,710 1635 00:51:36,710 --> 00:51:40,710 1636 00:51:40,710 --> 00:51:42,230 1637 00:51:42,230 --> 00:51:44,710 1638 00:51:44,710 --> 00:51:48,829 1639 00:51:48,829 --> 00:51:54,470 1640 00:51:54,470 --> 00:51:56,790 1641 00:51:56,790 --> 00:51:59,430 1642 00:51:59,430 --> 00:52:01,750 1643 00:52:01,750 --> 00:52:01,760 1644 00:52:01,760 --> 00:52:04,549 1645 00:52:04,549 --> 00:52:05,829 1646 00:52:05,829 --> 00:52:08,870 1647 00:52:08,870 --> 00:52:10,390 1648 00:52:10,390 --> 00:52:10,400 1649 00:52:10,400 --> 00:52:11,430 1650 00:52:11,430 --> 00:52:11,440 1651 00:52:11,440 --> 00:52:12,549 1652 00:52:12,549 --> 00:52:15,030 1653 00:52:15,030 --> 00:52:18,069 1654 00:52:18,069 --> 00:52:20,630 1655 00:52:20,630 --> 00:52:23,270 1656 00:52:23,270 --> 00:52:25,589 1657 00:52:25,589 --> 00:52:27,910 1658 00:52:27,910 --> 00:52:30,230 1659 00:52:30,230 --> 00:52:32,390 1660 00:52:32,390 --> 00:52:35,910 1661 00:52:35,910 --> 00:52:39,349 1662 00:52:39,349 --> 00:52:41,510 1663 00:52:41,510 --> 00:52:46,470 1664 00:52:46,470 --> 00:52:49,270 1665 00:52:49,270 --> 00:52:51,589 1666 00:52:51,589 --> 00:52:55,109 1667 00:52:55,109 --> 00:52:56,790 1668 00:52:56,790 --> 00:52:59,190 1669 00:52:59,190 --> 00:53:01,910 1670 00:53:01,910 --> 00:53:03,349 1671 00:53:03,349 --> 00:53:06,309 1672 00:53:06,309 --> 00:53:08,470 1673 00:53:08,470 --> 00:53:09,670 1674 00:53:09,670 --> 00:53:12,390 1675 00:53:12,390 --> 00:53:14,549 1676 00:53:14,549 --> 00:53:17,990 1677 00:53:17,990 --> 00:53:19,349 1678 00:53:19,349 --> 00:53:19,359 1679 00:53:19,359 --> 00:53:20,309 1680 00:53:20,309 --> 00:53:22,710 1681 00:53:22,710 --> 00:53:25,109 1682 00:53:25,109 --> 00:53:27,270 1683 00:53:27,270 --> 00:53:29,190 1684 00:53:29,190 --> 00:53:31,510 1685 00:53:31,510 --> 00:53:34,390 1686 00:53:34,390 --> 00:53:39,910 1687 00:53:39,910 --> 00:53:42,470 1688 00:53:42,470 --> 00:53:43,910 1689 00:53:43,910 --> 00:53:46,390 1690 00:53:46,390 --> 00:53:47,510 1691 00:53:47,510 --> 00:53:49,829 1692 00:53:49,829 --> 00:53:49,839 1693 00:53:49,839 --> 00:53:50,710 1694 00:53:50,710 --> 00:53:53,109 1695 00:53:53,109 --> 00:53:55,349 1696 00:53:55,349 --> 00:53:57,589 1697 00:53:57,589 --> 00:53:59,990 1698 00:53:59,990 --> 00:54:03,030 1699 00:54:03,030 --> 00:54:03,040 1700 00:54:03,040 --> 00:54:04,790 1701 00:54:04,790 --> 00:54:07,349 1702 00:54:07,349 --> 00:54:07,359 1703 00:54:07,359 --> 00:54:08,630 1704 00:54:08,630 --> 00:54:10,630 1705 00:54:10,630 --> 00:54:12,549 1706 00:54:12,549 --> 00:54:14,710 1707 00:54:14,710 --> 00:54:16,150 1708 00:54:16,150 --> 00:54:19,030 1709 00:54:19,030 --> 00:54:20,630 1710 00:54:20,630 --> 00:54:22,390 1711 00:54:22,390 --> 00:54:24,870 1712 00:54:24,870 --> 00:54:26,870 1713 00:54:26,870 --> 00:54:28,950 1714 00:54:28,950 --> 00:54:30,390 1715 00:54:30,390 --> 00:54:32,950 1716 00:54:32,950 --> 00:54:35,270 1717 00:54:35,270 --> 00:54:35,280 1718 00:54:35,280 --> 00:54:36,069 1719 00:54:36,069 --> 00:54:36,079 1720 00:54:36,079 --> 00:54:37,670 1721 00:54:37,670 --> 00:54:37,680 1722 00:54:37,680 --> 00:54:38,470 1723 00:54:38,470 --> 00:54:40,549 1724 00:54:40,549 --> 00:54:42,710 1725 00:54:42,710 --> 00:54:42,720 1726 00:54:42,720 --> 00:54:43,750 1727 00:54:43,750 --> 00:54:45,670 1728 00:54:45,670 --> 00:54:47,109 1729 00:54:47,109 --> 00:54:48,710 1730 00:54:48,710 --> 00:54:51,430 1731 00:54:51,430 --> 00:54:51,440 1732 00:54:51,440 --> 00:54:53,349 1733 00:54:53,349 --> 00:54:55,430 1734 00:54:55,430 --> 00:54:57,190 1735 00:54:57,190 --> 00:55:01,829 1736 00:55:01,829 --> 00:55:03,910 1737 00:55:03,910 --> 00:55:06,309 1738 00:55:06,309 --> 00:55:08,789 1739 00:55:08,789 --> 00:55:11,349 1740 00:55:11,349 --> 00:55:11,359 1741 00:55:11,359 --> 00:55:13,270 1742 00:55:13,270 --> 00:55:14,549 1743 00:55:14,549 --> 00:55:16,309 1744 00:55:16,309 --> 00:55:18,950 1745 00:55:18,950 --> 00:55:23,430 1746 00:55:23,430 --> 00:55:25,589 1747 00:55:25,589 --> 00:55:25,599 1748 00:55:25,599 --> 00:55:27,430 1749 00:55:27,430 --> 00:55:29,910 1750 00:55:29,910 --> 00:55:31,030 1751 00:55:31,030 --> 00:55:32,710 1752 00:55:32,710 --> 00:55:34,870 1753 00:55:34,870 --> 00:55:39,349 1754 00:55:39,349 --> 00:55:41,990 1755 00:55:41,990 --> 00:55:43,310 1756 00:55:43,310 --> 00:55:43,320 1757 00:55:43,320 --> 00:55:45,750 1758 00:55:45,750 --> 00:55:47,910 1759 00:55:47,910 --> 00:55:49,430 1760 00:55:49,430 --> 00:55:51,750 1761 00:55:51,750 --> 00:55:51,760 1762 00:55:51,760 --> 00:55:54,789 1763 00:55:54,789 --> 00:55:56,710 1764 00:55:56,710 --> 00:55:59,349 1765 00:55:59,349 --> 00:56:01,349 1766 00:56:01,349 --> 00:56:03,109 1767 00:56:03,109 --> 00:56:03,119 1768 00:56:03,119 --> 00:56:04,150 1769 00:56:04,150 --> 00:56:05,750 1770 00:56:05,750 --> 00:56:09,109 1771 00:56:09,109 --> 00:56:09,119 1772 00:56:09,119 --> 00:56:09,910 1773 00:56:09,910 --> 00:56:11,910 1774 00:56:11,910 --> 00:56:14,549 1775 00:56:14,549 --> 00:56:17,510 1776 00:56:17,510 --> 00:56:19,829 1777 00:56:19,829 --> 00:56:21,510 1778 00:56:21,510 --> 00:56:24,870 1779 00:56:24,870 --> 00:56:27,750 1780 00:56:27,750 --> 00:56:29,349 1781 00:56:29,349 --> 00:56:31,430 1782 00:56:31,430 --> 00:56:33,030 1783 00:56:33,030 --> 00:56:35,670 1784 00:56:35,670 --> 00:56:38,069 1785 00:56:38,069 --> 00:56:38,079 1786 00:56:38,079 --> 00:56:39,349 1787 00:56:39,349 --> 00:56:39,359 1788 00:56:39,359 --> 00:56:40,150 1789 00:56:40,150 --> 00:56:40,160 1790 00:56:40,160 --> 00:56:42,069 1791 00:56:42,069 --> 00:56:42,079 1792 00:56:42,079 --> 00:56:43,430 1793 00:56:43,430 --> 00:56:44,789 1794 00:56:44,789 --> 00:56:44,799 1795 00:56:44,799 --> 00:56:51,349 1796 00:56:51,349 --> 00:56:52,549 1797 00:56:52,549 --> 00:56:54,230 1798 00:56:54,230 --> 00:56:57,190 1799 00:56:57,190 --> 00:57:00,069 1800 00:57:00,069 --> 00:57:03,510 1801 00:57:03,510 --> 00:57:03,520 1802 00:57:03,520 --> 00:57:04,630 1803 00:57:04,630 --> 00:57:05,990 1804 00:57:05,990 --> 00:57:06,000 1805 00:57:06,000 --> 00:57:07,510 1806 00:57:07,510 --> 00:57:10,309 1807 00:57:10,309 --> 00:57:12,069 1808 00:57:12,069 --> 00:57:13,750 1809 00:57:13,750 --> 00:57:15,990 1810 00:57:15,990 --> 00:57:16,950 1811 00:57:16,950 --> 00:57:18,630 1812 00:57:18,630 --> 00:57:19,750 1813 00:57:19,750 --> 00:57:21,430 1814 00:57:21,430 --> 00:57:21,440 1815 00:57:21,440 --> 00:57:22,710 1816 00:57:22,710 --> 00:57:22,720 1817 00:57:22,720 --> 00:57:24,150 1818 00:57:24,150 --> 00:57:25,750 1819 00:57:25,750 --> 00:57:26,950 1820 00:57:26,950 --> 00:57:29,349 1821 00:57:29,349 --> 00:57:29,359 1822 00:57:29,359 --> 00:57:31,030 1823 00:57:31,030 --> 00:57:35,750 1824 00:57:35,750 --> 00:57:38,630 1825 00:57:38,630 --> 00:57:41,430 1826 00:57:41,430 --> 00:57:41,440 1827 00:57:41,440 --> 00:57:44,230 1828 00:57:44,230 --> 00:57:45,750 1829 00:57:45,750 --> 00:57:48,950 1830 00:57:48,950 --> 00:57:48,960 1831 00:57:48,960 --> 00:57:50,630 1832 00:57:50,630 --> 00:57:52,870 1833 00:57:52,870 --> 00:57:55,430 1834 00:57:55,430 --> 00:57:58,230 1835 00:57:58,230 --> 00:58:00,710 1836 00:58:00,710 --> 00:58:02,789 1837 00:58:02,789 --> 00:58:02,799 1838 00:58:02,799 --> 00:58:04,470 1839 00:58:04,470 --> 00:58:07,190 1840 00:58:07,190 --> 00:58:09,670 1841 00:58:09,670 --> 00:58:11,190 1842 00:58:11,190 --> 00:58:13,190 1843 00:58:13,190 --> 00:58:16,549 1844 00:58:16,549 --> 00:58:18,870 1845 00:58:18,870 --> 00:58:21,349 1846 00:58:21,349 --> 00:58:23,589 1847 00:58:23,589 --> 00:58:26,309 1848 00:58:26,309 --> 00:58:26,319 1849 00:58:26,319 --> 00:58:27,670 1850 00:58:27,670 --> 00:58:31,750 1851 00:58:31,750 --> 00:58:34,230 1852 00:58:34,230 --> 00:58:37,510 1853 00:58:37,510 --> 00:58:39,589 1854 00:58:39,589 --> 00:58:42,710 1855 00:58:42,710 --> 00:58:44,870 1856 00:58:44,870 --> 00:58:47,589 1857 00:58:47,589 --> 00:58:47,599 1858 00:58:47,599 --> 00:58:48,950 1859 00:58:48,950 --> 00:58:48,960 1860 00:58:48,960 --> 00:58:49,750 1861 00:58:49,750 --> 00:58:54,069 1862 00:58:54,069 --> 00:58:57,349 1863 00:58:57,349 --> 00:58:58,950 1864 00:58:58,950 --> 00:59:00,630 1865 00:59:00,630 --> 00:59:02,309 1866 00:59:02,309 --> 00:59:05,430 1867 00:59:05,430 --> 00:59:09,190 1868 00:59:09,190 --> 00:59:12,870 1869 00:59:12,870 --> 00:59:12,880 1870 00:59:12,880 --> 00:59:15,829 1871 00:59:15,829 --> 00:59:17,829 1872 00:59:17,829 --> 00:59:19,430 1873 00:59:19,430 --> 00:59:21,750 1874 00:59:21,750 --> 00:59:24,069 1875 00:59:24,069 --> 00:59:25,990 1876 00:59:25,990 --> 00:59:28,670 1877 00:59:28,670 --> 00:59:31,510 1878 00:59:31,510 --> 00:59:33,589 1879 00:59:33,589 --> 00:59:35,510 1880 00:59:35,510 --> 00:59:36,950 1881 00:59:36,950 --> 00:59:36,960 1882 00:59:36,960 --> 00:59:38,069 1883 00:59:38,069 --> 00:59:39,990 1884 00:59:39,990 --> 00:59:42,710 1885 00:59:42,710 --> 00:59:44,870 1886 00:59:44,870 --> 00:59:46,470 1887 00:59:46,470 --> 00:59:48,150 1888 00:59:48,150 --> 00:59:51,109 1889 00:59:51,109 --> 00:59:53,270 1890 00:59:53,270 --> 00:59:54,549 1891 00:59:54,549 --> 00:59:54,559 1892 00:59:54,559 --> 00:59:55,349 1893 00:59:55,349 --> 00:59:56,630 1894 00:59:56,630 --> 00:59:59,109 1895 00:59:59,109 --> 01:00:01,430 1896 01:00:01,430 --> 01:00:02,710 1897 01:00:02,710 --> 01:00:06,390 1898 01:00:06,390 --> 01:00:07,750 1899 01:00:07,750 --> 01:00:07,760 1900 01:00:07,760 --> 01:00:08,470 1901 01:00:08,470 --> 01:00:09,670 1902 01:00:09,670 --> 01:00:11,829 1903 01:00:11,829 --> 01:00:15,190 1904 01:00:15,190 --> 01:00:16,710 1905 01:00:16,710 --> 01:00:18,710 1906 01:00:18,710 --> 01:00:20,309 1907 01:00:20,309 --> 01:00:20,319 1908 01:00:20,319 --> 01:00:21,430 1909 01:00:21,430 --> 01:00:23,910 1910 01:00:23,910 --> 01:00:23,920 1911 01:00:23,920 --> 01:00:25,510 1912 01:00:25,510 --> 01:00:27,670 1913 01:00:27,670 --> 01:00:29,270 1914 01:00:29,270 --> 01:00:31,270 1915 01:00:31,270 --> 01:00:31,280 1916 01:00:31,280 --> 01:00:32,309 1917 01:00:32,309 --> 01:00:35,030 1918 01:00:35,030 --> 01:00:36,789 1919 01:00:36,789 --> 01:00:38,390 1920 01:00:38,390 --> 01:00:40,789 1921 01:00:40,789 --> 01:00:43,910 1922 01:00:43,910 --> 01:00:45,670 1923 01:00:45,670 --> 01:00:45,680 1924 01:00:45,680 --> 01:00:46,870 1925 01:00:46,870 --> 01:00:48,309 1926 01:00:48,309 --> 01:00:48,319 1927 01:00:48,319 --> 01:00:49,190 1928 01:00:49,190 --> 01:00:50,549 1929 01:00:50,549 --> 01:00:50,559 1930 01:00:50,559 --> 01:00:51,430 1931 01:00:51,430 --> 01:00:54,470 1932 01:00:54,470 --> 01:00:58,230 1933 01:00:58,230 --> 01:01:01,349 1934 01:01:01,349 --> 01:01:02,870 1935 01:01:02,870 --> 01:01:05,829 1936 01:01:05,829 --> 01:01:08,069 1937 01:01:08,069 --> 01:01:09,510 1938 01:01:09,510 --> 01:01:11,190 1939 01:01:11,190 --> 01:01:13,190 1940 01:01:13,190 --> 01:01:16,150 1941 01:01:16,150 --> 01:01:19,190 1942 01:01:19,190 --> 01:01:19,200 1943 01:01:19,200 --> 01:01:20,069 1944 01:01:20,069 --> 01:01:21,589 1945 01:01:21,589 --> 01:01:24,230 1946 01:01:24,230 --> 01:01:26,630 1947 01:01:26,630 --> 01:01:29,109 1948 01:01:29,109 --> 01:01:31,750 1949 01:01:31,750 --> 01:01:31,760 1950 01:01:31,760 --> 01:01:33,670 1951 01:01:33,670 --> 01:01:35,349 1952 01:01:35,349 --> 01:01:35,359 1953 01:01:35,359 --> 01:01:36,309 1954 01:01:36,309 --> 01:01:39,190 1955 01:01:39,190 --> 01:01:42,069 1956 01:01:42,069 --> 01:01:45,190 1957 01:01:45,190 --> 01:01:45,200 1958 01:01:45,200 --> 01:01:46,710 1959 01:01:46,710 --> 01:01:48,789 1960 01:01:48,789 --> 01:01:50,789 1961 01:01:50,789 --> 01:01:52,870 1962 01:01:52,870 --> 01:01:55,190 1963 01:01:55,190 --> 01:01:57,510 1964 01:01:57,510 --> 01:01:59,349 1965 01:01:59,349 --> 01:02:00,870 1966 01:02:00,870 --> 01:02:02,470 1967 01:02:02,470 --> 01:02:02,480 1968 01:02:02,480 --> 01:02:03,050 1969 01:02:03,050 --> 01:02:03,060 1970 01:02:03,060 --> 01:02:05,109 1971 01:02:05,109 --> 01:02:07,349 1972 01:02:07,349 --> 01:02:08,870 1973 01:02:08,870 --> 01:02:08,880 1974 01:02:08,880 --> 01:02:09,990 1975 01:02:09,990 --> 01:02:10,000 1976 01:02:10,000 --> 01:02:11,029 1977 01:02:11,029 --> 01:02:11,039 1978 01:02:11,039 --> 01:02:12,470 1979 01:02:12,470 --> 01:02:15,029 1980 01:02:15,029 --> 01:02:18,870 1981 01:02:18,870 --> 01:02:21,190 1982 01:02:21,190 --> 01:02:21,200 1983 01:02:21,200 --> 01:02:22,309 1984 01:02:22,309 --> 01:02:24,870 1985 01:02:24,870 --> 01:02:26,390 1986 01:02:26,390 --> 01:02:28,710 1987 01:02:28,710 --> 01:02:30,549 1988 01:02:30,549 --> 01:02:33,190 1989 01:02:33,190 --> 01:02:35,750 1990 01:02:35,750 --> 01:02:38,069 1991 01:02:38,069 --> 01:02:39,349 1992 01:02:39,349 --> 01:02:41,750 1993 01:02:41,750 --> 01:02:43,349 1994 01:02:43,349 --> 01:02:43,359 1995 01:02:43,359 --> 01:02:44,150 1996 01:02:44,150 --> 01:02:45,589 1997 01:02:45,589 --> 01:02:47,270 1998 01:02:47,270 --> 01:02:48,710 1999 01:02:48,710 --> 01:02:51,270 2000 01:02:51,270 --> 01:02:54,230 2001 01:02:54,230 --> 01:02:54,240 2002 01:02:54,240 --> 01:02:55,510 2003 01:02:55,510 --> 01:02:57,029 2004 01:02:57,029 --> 01:03:01,109 2005 01:03:01,109 --> 01:03:03,670 2006 01:03:03,670 --> 01:03:07,270 2007 01:03:07,270 --> 01:03:10,470 2008 01:03:10,470 --> 01:03:12,309 2009 01:03:12,309 --> 01:03:13,910 2010 01:03:13,910 --> 01:03:16,069 2011 01:03:16,069 --> 01:03:19,670 2012 01:03:19,670 --> 01:03:21,750 2013 01:03:21,750 --> 01:03:24,710 2014 01:03:24,710 --> 01:03:26,870 2015 01:03:26,870 --> 01:03:28,950 2016 01:03:28,950 --> 01:03:30,630 2017 01:03:30,630 --> 01:03:33,750 2018 01:03:33,750 --> 01:03:35,750 2019 01:03:35,750 --> 01:03:38,630 2020 01:03:38,630 --> 01:03:41,990 2021 01:03:41,990 --> 01:03:44,630 2022 01:03:44,630 --> 01:03:45,510 2023 01:03:45,510 --> 01:03:51,349 2024 01:03:51,349 --> 01:03:51,359 2025 01:03:51,359 --> 01:03:52,390 2026 01:03:52,390 --> 01:03:54,150 2027 01:03:54,150 --> 01:03:56,069 2028 01:03:56,069 --> 01:03:57,430 2029 01:03:57,430 --> 01:03:59,190 2030 01:03:59,190 --> 01:04:01,349 2031 01:04:01,349 --> 01:04:05,750 2032 01:04:05,750 --> 01:04:05,760 2033 01:04:05,760 --> 01:04:06,870 2034 01:04:06,870 --> 01:04:08,150 2035 01:04:08,150 --> 01:04:10,829 2036 01:04:10,829 --> 01:04:13,029 2037 01:04:13,029 --> 01:04:14,789 2038 01:04:14,789 --> 01:04:15,990 2039 01:04:15,990 --> 01:04:17,990 2040 01:04:17,990 --> 01:04:18,870 2041 01:04:18,870 --> 01:04:21,109 2042 01:04:21,109 --> 01:04:22,789 2043 01:04:22,789 --> 01:04:24,549 2044 01:04:24,549 --> 01:04:26,230 2045 01:04:26,230 --> 01:04:28,549 2046 01:04:28,549 --> 01:04:30,390 2047 01:04:30,390 --> 01:04:32,390 2048 01:04:32,390 --> 01:04:35,349 2049 01:04:35,349 --> 01:04:39,109 2050 01:04:39,109 --> 01:04:41,349 2051 01:04:41,349 --> 01:04:42,710 2052 01:04:42,710 --> 01:04:44,630 2053 01:04:44,630 --> 01:04:46,549 2054 01:04:46,549 --> 01:04:46,559 2055 01:04:46,559 --> 01:04:47,510 2056 01:04:47,510 --> 01:04:49,589 2057 01:04:49,589 --> 01:04:49,599 2058 01:04:49,599 --> 01:04:50,549 2059 01:04:50,549 --> 01:04:53,990 2060 01:04:53,990 --> 01:04:56,230 2061 01:04:56,230 --> 01:04:58,150 2062 01:04:58,150 --> 01:05:01,109 2063 01:05:01,109 --> 01:05:03,430 2064 01:05:03,430 --> 01:05:05,750 2065 01:05:05,750 --> 01:05:07,510 2066 01:05:07,510 --> 01:05:07,520 2067 01:05:07,520 --> 01:05:09,510 2068 01:05:09,510 --> 01:05:11,829 2069 01:05:11,829 --> 01:05:13,029 2070 01:05:13,029 --> 01:05:13,039 2071 01:05:13,039 --> 01:05:14,789 2072 01:05:14,789 --> 01:05:16,950 2073 01:05:16,950 --> 01:05:19,270 2074 01:05:19,270 --> 01:05:21,270 2075 01:05:21,270 --> 01:05:23,589 2076 01:05:23,589 --> 01:05:25,430 2077 01:05:25,430 --> 01:05:27,029 2078 01:05:27,029 --> 01:05:28,549 2079 01:05:28,549 --> 01:05:29,510 2080 01:05:29,510 --> 01:05:29,520 2081 01:05:29,520 --> 01:05:30,870 2082 01:05:30,870 --> 01:05:33,109 2083 01:05:33,109 --> 01:05:34,630 2084 01:05:34,630 --> 01:05:38,390 2085 01:05:38,390 --> 01:05:41,190 2086 01:05:41,190 --> 01:05:43,109 2087 01:05:43,109 --> 01:05:44,789 2088 01:05:44,789 --> 01:05:47,349 2089 01:05:47,349 --> 01:05:47,359 2090 01:05:47,359 --> 01:05:48,309 2091 01:05:48,309 --> 01:05:51,270 2092 01:05:51,270 --> 01:05:53,190 2093 01:05:53,190 --> 01:05:55,190 2094 01:05:55,190 --> 01:05:56,870 2095 01:05:56,870 --> 01:06:00,309 2096 01:06:00,309 --> 01:06:02,630 2097 01:06:02,630 --> 01:06:04,390 2098 01:06:04,390 --> 01:06:07,829 2099 01:06:07,829 --> 01:06:10,950 2100 01:06:10,950 --> 01:06:12,870 2101 01:06:12,870 --> 01:06:14,950 2102 01:06:14,950 --> 01:06:16,870 2103 01:06:16,870 --> 01:06:19,829 2104 01:06:19,829 --> 01:06:19,839 2105 01:06:19,839 --> 01:06:20,870 2106 01:06:20,870 --> 01:06:20,880 2107 01:06:20,880 --> 01:06:23,029 2108 01:06:23,029 --> 01:06:24,710 2109 01:06:24,710 --> 01:06:24,720 2110 01:06:24,720 --> 01:06:25,990 2111 01:06:25,990 --> 01:06:26,000 2112 01:06:26,000 --> 01:06:26,950 2113 01:06:26,950 --> 01:06:28,630 2114 01:06:28,630 --> 01:06:31,510 2115 01:06:31,510 --> 01:06:33,430 2116 01:06:33,430 --> 01:06:36,470 2117 01:06:36,470 --> 01:06:39,589 2118 01:06:39,589 --> 01:06:40,710 2119 01:06:40,710 --> 01:06:40,720 2120 01:06:40,720 --> 01:06:41,829 2121 01:06:41,829 --> 01:06:45,190 2122 01:06:45,190 --> 01:06:49,349 2123 01:06:49,349 --> 01:06:49,359 2124 01:06:49,359 --> 01:06:50,789 2125 01:06:50,789 --> 01:06:55,990 2126 01:06:55,990 --> 01:06:57,829 2127 01:06:57,829 --> 01:06:57,839 2128 01:06:57,839 --> 01:06:58,630 2129 01:06:58,630 --> 01:07:00,630 2130 01:07:00,630 --> 01:07:02,630 2131 01:07:02,630 --> 01:07:03,910 2132 01:07:03,910 --> 01:07:05,589 2133 01:07:05,589 --> 01:07:08,470 2134 01:07:08,470 --> 01:07:10,150 2135 01:07:10,150 --> 01:07:12,829 2136 01:07:12,829 --> 01:07:15,910 2137 01:07:15,910 --> 01:07:19,349 2138 01:07:19,349 --> 01:07:20,870 2139 01:07:20,870 --> 01:07:24,549 2140 01:07:24,549 --> 01:07:26,150 2141 01:07:26,150 --> 01:07:29,430 2142 01:07:29,430 --> 01:07:34,150 2143 01:07:34,150 --> 01:07:36,710 2144 01:07:36,710 --> 01:07:38,309 2145 01:07:38,309 --> 01:07:40,789 2146 01:07:40,789 --> 01:07:43,430 2147 01:07:43,430 --> 01:07:50,549 2148 01:07:50,549 --> 01:07:53,750 2149 01:07:53,750 --> 01:07:53,760 2150 01:07:53,760 --> 01:07:55,510 2151 01:07:55,510 --> 01:07:57,829 2152 01:07:57,829 --> 01:07:57,839 2153 01:07:57,839 --> 01:07:58,950 2154 01:07:58,950 --> 01:08:00,630 2155 01:08:00,630 --> 01:08:03,510 2156 01:08:03,510 --> 01:08:04,870 2157 01:08:04,870 --> 01:08:07,750 2158 01:08:07,750 --> 01:08:07,760 2159 01:08:07,760 --> 01:08:09,029 2160 01:08:09,029 --> 01:08:11,430 2161 01:08:11,430 --> 01:08:13,349 2162 01:08:13,349 --> 01:08:15,829 2163 01:08:15,829 --> 01:08:18,110 2164 01:08:18,110 --> 01:08:18,120 2165 01:08:18,120 --> 01:08:19,749 2166 01:08:19,749 --> 01:08:19,759 2167 01:08:19,759 --> 01:08:20,630 2168 01:08:20,630 --> 01:08:20,640 2169 01:08:20,640 --> 01:08:21,910 2170 01:08:21,910 --> 01:08:24,390 2171 01:08:24,390 --> 01:08:24,400 2172 01:08:24,400 --> 01:08:25,829 2173 01:08:25,829 --> 01:08:25,839 2174 01:08:25,839 --> 01:08:28,789 2175 01:08:28,789 --> 01:08:28,799 2176 01:08:28,799 --> 01:08:31,829 2177 01:08:31,829 --> 01:08:32,830 2178 01:08:32,830 --> 01:08:32,840 2179 01:08:32,840 --> 01:08:34,470 2180 01:08:34,470 --> 01:08:36,789 2181 01:08:36,789 --> 01:08:39,269 2182 01:08:39,269 --> 01:08:41,669 2183 01:08:41,669 --> 01:08:43,749 2184 01:08:43,749 --> 01:08:46,229 2185 01:08:46,229 --> 01:08:47,669 2186 01:08:47,669 --> 01:08:50,550 2187 01:08:50,550 --> 01:08:53,110 2188 01:08:53,110 --> 01:08:53,120 2189 01:08:53,120 --> 01:08:54,470 2190 01:08:54,470 --> 01:08:56,709 2191 01:08:56,709 --> 01:08:59,269 2192 01:08:59,269 --> 01:09:01,030 2193 01:09:01,030 --> 01:09:03,110 2194 01:09:03,110 --> 01:09:05,749 2195 01:09:05,749 --> 01:09:07,990 2196 01:09:07,990 --> 01:09:08,000 2197 01:09:08,000 --> 01:09:09,349 2198 01:09:09,349 --> 01:09:12,149 2199 01:09:12,149 --> 01:09:15,110 2200 01:09:15,110 --> 01:09:17,590 2201 01:09:17,590 --> 01:09:18,870 2202 01:09:18,870 --> 01:09:20,870 2203 01:09:20,870 --> 01:09:22,630 2204 01:09:22,630 --> 01:09:24,229 2205 01:09:24,229 --> 01:09:27,510 2206 01:09:27,510 --> 01:09:29,269 2207 01:09:29,269 --> 01:09:31,829 2208 01:09:31,829 --> 01:09:33,269 2209 01:09:33,269 --> 01:09:35,189 2210 01:09:35,189 --> 01:09:37,910 2211 01:09:37,910 --> 01:09:40,070 2212 01:09:40,070 --> 01:09:41,349 2213 01:09:41,349 --> 01:09:44,550 2214 01:09:44,550 --> 01:09:47,349 2215 01:09:47,349 --> 01:09:48,630 2216 01:09:48,630 --> 01:09:50,950 2217 01:09:50,950 --> 01:09:52,870 2218 01:09:52,870 --> 01:09:52,880 2219 01:09:52,880 --> 01:09:54,390 2220 01:09:54,390 --> 01:09:57,990 2221 01:09:57,990 --> 01:09:58,000 2222 01:09:58,000 --> 01:10:00,229 2223 01:10:00,229 --> 01:10:00,239 2224 01:10:00,239 --> 01:10:01,110 2225 01:10:01,110 --> 01:10:04,709 2226 01:10:04,709 --> 01:10:06,149 2227 01:10:06,149 --> 01:10:08,390 2228 01:10:08,390 --> 01:10:10,470 2229 01:10:10,470 --> 01:10:12,390 2230 01:10:12,390 --> 01:10:12,400 2231 01:10:12,400 --> 01:10:13,350 2232 01:10:13,350 --> 01:10:13,360 2233 01:10:13,360 --> 01:10:15,110 2234 01:10:15,110 --> 01:10:17,990 2235 01:10:17,990 --> 01:10:19,350 2236 01:10:19,350 --> 01:10:21,830 2237 01:10:21,830 --> 01:10:23,750 2238 01:10:23,750 --> 01:10:25,750 2239 01:10:25,750 --> 01:10:28,070 2240 01:10:28,070 --> 01:10:29,750 2241 01:10:29,750 --> 01:10:29,760 2242 01:10:29,760 --> 01:10:32,149 2243 01:10:32,149 --> 01:10:34,470 2244 01:10:34,470 --> 01:10:36,470 2245 01:10:36,470 --> 01:10:40,550 2246 01:10:40,550 --> 01:10:43,990 2247 01:10:43,990 --> 01:10:45,750 2248 01:10:45,750 --> 01:10:49,910 2249 01:10:49,910 --> 01:10:52,630 2250 01:10:52,630 --> 01:10:55,750 2251 01:10:55,750 --> 01:10:57,510 2252 01:10:57,510 --> 01:10:57,520 2253 01:10:57,520 --> 01:10:58,470 2254 01:10:58,470 --> 01:11:00,070 2255 01:11:00,070 --> 01:11:00,080 2256 01:11:00,080 --> 01:11:02,070 2257 01:11:02,070 --> 01:11:05,270 2258 01:11:05,270 --> 01:11:05,280 2259 01:11:05,280 --> 01:11:06,149 2260 01:11:06,149 --> 01:11:09,510 2261 01:11:09,510 --> 01:11:11,590 2262 01:11:11,590 --> 01:11:13,669 2263 01:11:13,669 --> 01:11:15,669 2264 01:11:15,669 --> 01:11:17,990 2265 01:11:17,990 --> 01:11:18,000 2266 01:11:18,000 --> 01:11:18,790 2267 01:11:18,790 --> 01:11:21,110 2268 01:11:21,110 --> 01:11:23,430 2269 01:11:23,430 --> 01:11:23,440 2270 01:11:23,440 --> 01:11:24,470 2271 01:11:24,470 --> 01:11:27,750 2272 01:11:27,750 --> 01:11:30,229 2273 01:11:30,229 --> 01:11:33,189 2274 01:11:33,189 --> 01:11:35,430 2275 01:11:35,430 --> 01:11:37,669 2276 01:11:37,669 --> 01:11:41,189 2277 01:11:41,189 --> 01:11:43,189 2278 01:11:43,189 --> 01:11:46,229 2279 01:11:46,229 --> 01:11:48,070 2280 01:11:48,070 --> 01:11:49,990 2281 01:11:49,990 --> 01:11:50,000 2282 01:11:50,000 --> 01:11:50,790 2283 01:11:50,790 --> 01:11:50,800 2284 01:11:50,800 --> 01:11:52,390 2285 01:11:52,390 --> 01:11:55,750 2286 01:11:55,750 --> 01:11:58,310 2287 01:11:58,310 --> 01:12:01,510 2288 01:12:01,510 --> 01:12:02,390 2289 01:12:02,390 --> 01:12:04,630 2290 01:12:04,630 --> 01:12:06,229 2291 01:12:06,229 --> 01:12:09,110 2292 01:12:09,110 --> 01:12:10,630 2293 01:12:10,630 --> 01:12:12,630 2294 01:12:12,630 --> 01:12:16,070 2295 01:12:16,070 --> 01:12:17,590 2296 01:12:17,590 --> 01:12:17,600 2297 01:12:17,600 --> 01:12:18,870 2298 01:12:18,870 --> 01:12:22,630 2299 01:12:22,630 --> 01:12:23,709 2300 01:12:23,709 --> 01:12:25,510 2301 01:12:25,510 --> 01:12:27,030 2302 01:12:27,030 --> 01:12:30,630 2303 01:12:30,630 --> 01:12:33,350 2304 01:12:33,350 --> 01:12:35,910 2305 01:12:35,910 --> 01:12:37,110 2306 01:12:37,110 --> 01:12:38,630 2307 01:12:38,630 --> 01:12:39,750 2308 01:12:39,750 --> 01:12:41,110 2309 01:12:41,110 --> 01:12:42,870 2310 01:12:42,870 --> 01:12:42,880 2311 01:12:42,880 --> 01:12:45,990 2312 01:12:45,990 --> 01:12:48,630 2313 01:12:48,630 --> 01:12:50,870 2314 01:12:50,870 --> 01:12:52,630 2315 01:12:52,630 --> 01:12:54,390 2316 01:12:54,390 --> 01:12:57,590 2317 01:12:57,590 --> 01:12:59,189 2318 01:12:59,189 --> 01:13:01,350 2319 01:13:01,350 --> 01:13:02,870 2320 01:13:02,870 --> 01:13:04,390 2321 01:13:04,390 --> 01:13:04,400 2322 01:13:04,400 --> 01:13:06,149 2323 01:13:06,149 --> 01:13:08,229 2324 01:13:08,229 --> 01:13:09,910 2325 01:13:09,910 --> 01:13:11,270 2326 01:13:11,270 --> 01:13:12,790 2327 01:13:12,790 --> 01:13:13,990 2328 01:13:13,990 --> 01:13:16,149 2329 01:13:16,149 --> 01:13:18,870 2330 01:13:18,870 --> 01:13:19,990 2331 01:13:19,990 --> 01:13:21,590 2332 01:13:21,590 --> 01:13:22,870 2333 01:13:22,870 --> 01:13:22,880 2334 01:13:22,880 --> 01:13:24,470 2335 01:13:24,470 --> 01:13:27,110 2336 01:13:27,110 --> 01:13:29,350 2337 01:13:29,350 --> 01:13:31,430 2338 01:13:31,430 --> 01:13:35,750 2339 01:13:35,750 --> 01:13:37,669 2340 01:13:37,669 --> 01:13:40,149 2341 01:13:40,149 --> 01:13:42,550 2342 01:13:42,550 --> 01:13:44,070 2343 01:13:44,070 --> 01:13:45,189 2344 01:13:45,189 --> 01:13:47,830 2345 01:13:47,830 --> 01:13:51,189 2346 01:13:51,189 --> 01:13:53,110 2347 01:13:53,110 --> 01:13:55,750 2348 01:13:55,750 --> 01:13:59,030 2349 01:13:59,030 --> 01:14:01,990 2350 01:14:01,990 --> 01:14:03,750 2351 01:14:03,750 --> 01:14:06,470 2352 01:14:06,470 --> 01:14:08,390 2353 01:14:08,390 --> 01:14:11,750 2354 01:14:11,750 --> 01:14:13,430 2355 01:14:13,430 --> 01:14:15,750 2356 01:14:15,750 --> 01:14:18,310 2357 01:14:18,310 --> 01:14:20,390 2358 01:14:20,390 --> 01:14:23,830 2359 01:14:23,830 --> 01:14:26,229 2360 01:14:26,229 --> 01:14:29,030 2361 01:14:29,030 --> 01:14:31,110 2362 01:14:31,110 --> 01:14:32,070 2363 01:14:32,070 --> 01:14:33,830 2364 01:14:33,830 --> 01:14:35,750 2365 01:14:35,750 --> 01:14:37,750 2366 01:14:37,750 --> 01:14:41,270 2367 01:14:41,270 --> 01:14:42,709 2368 01:14:42,709 --> 01:14:45,910 2369 01:14:45,910 --> 01:14:49,189 2370 01:14:49,189 --> 01:14:51,830 2371 01:14:51,830 --> 01:14:54,709 2372 01:14:54,709 --> 01:14:56,390 2373 01:14:56,390 --> 01:14:58,310 2374 01:14:58,310 --> 01:15:00,470 2375 01:15:00,470 --> 01:15:01,990 2376 01:15:01,990 --> 01:15:03,590 2377 01:15:03,590 --> 01:15:05,990 2378 01:15:05,990 --> 01:15:08,550 2379 01:15:08,550 --> 01:15:10,390 2380 01:15:10,390 --> 01:15:12,550 2381 01:15:12,550 --> 01:15:15,189 2382 01:15:15,189 --> 01:15:17,430 2383 01:15:17,430 --> 01:15:21,430 2384 01:15:21,430 --> 01:15:23,350 2385 01:15:23,350 --> 01:15:27,110 2386 01:15:27,110 --> 01:15:29,030 2387 01:15:29,030 --> 01:15:32,229 2388 01:15:32,229 --> 01:15:34,790 2389 01:15:34,790 --> 01:15:37,189 2390 01:15:37,189 --> 01:15:37,199 2391 01:15:37,199 --> 01:15:38,870 2392 01:15:38,870 --> 01:15:38,880 2393 01:15:38,880 --> 01:15:40,070 2394 01:15:40,070 --> 01:15:41,910 2395 01:15:41,910 --> 01:15:44,709 2396 01:15:44,709 --> 01:15:47,430 2397 01:15:47,430 --> 01:15:49,350 2398 01:15:49,350 --> 01:15:52,790 2399 01:15:52,790 --> 01:15:52,800 2400 01:15:52,800 --> 01:15:53,669 2401 01:15:53,669 --> 01:15:56,229 2402 01:15:56,229 --> 01:15:58,310 2403 01:15:58,310 --> 01:15:59,910 2404 01:15:59,910 --> 01:15:59,920 2405 01:15:59,920 --> 01:16:01,189 2406 01:16:01,189 --> 01:16:02,950 2407 01:16:02,950 --> 01:16:04,070 2408 01:16:04,070 --> 01:16:06,470 2409 01:16:06,470 --> 01:16:10,070 2410 01:16:10,070 --> 01:16:12,470 2411 01:16:12,470 --> 01:16:14,709 2412 01:16:14,709 --> 01:16:17,830 2413 01:16:17,830 --> 01:16:19,189 2414 01:16:19,189 --> 01:16:22,149 2415 01:16:22,149 --> 01:16:24,390 2416 01:16:24,390 --> 01:16:27,910 2417 01:16:27,910 --> 01:16:27,920 2418 01:16:27,920 --> 01:16:29,750 2419 01:16:29,750 --> 01:16:31,270 2420 01:16:31,270 --> 01:16:34,390 2421 01:16:34,390 --> 01:16:36,390 2422 01:16:36,390 --> 01:16:37,990 2423 01:16:37,990 --> 01:16:39,590 2424 01:16:39,590 --> 01:16:40,709 2425 01:16:40,709 --> 01:16:42,550 2426 01:16:42,550 --> 01:16:43,910 2427 01:16:43,910 --> 01:16:47,270 2428 01:16:47,270 --> 01:16:49,669 2429 01:16:49,669 --> 01:16:52,390 2430 01:16:52,390 --> 01:16:54,149 2431 01:16:54,149 --> 01:16:56,390 2432 01:16:56,390 --> 01:16:57,669 2433 01:16:57,669 --> 01:17:02,950 2434 01:17:02,950 --> 01:17:04,470 2435 01:17:04,470 --> 01:17:06,550 2436 01:17:06,550 --> 01:17:08,470 2437 01:17:08,470 --> 01:17:11,990 2438 01:17:11,990 --> 01:17:14,229 2439 01:17:14,229 --> 01:17:17,030 2440 01:17:17,030 --> 01:17:19,350 2441 01:17:19,350 --> 01:17:19,360 2442 01:17:19,360 --> 01:17:20,790 2443 01:17:20,790 --> 01:17:22,709 2444 01:17:22,709 --> 01:17:23,830 2445 01:17:23,830 --> 01:17:28,070 2446 01:17:28,070 --> 01:17:31,110 2447 01:17:31,110 --> 01:17:34,229 2448 01:17:34,229 --> 01:17:34,239 2449 01:17:34,239 --> 01:17:40,870 2450 01:17:40,870 --> 01:17:40,880 2451 01:17:40,880 --> 01:17:42,149 2452 01:17:42,149 --> 01:17:42,159 2453 01:17:42,159 --> 01:17:44,470 2454 01:17:44,470 --> 01:17:46,950 2455 01:17:46,950 --> 01:17:48,950 2456 01:17:48,950 --> 01:17:51,430 2457 01:17:51,430 --> 01:17:55,990 2458 01:17:55,990 --> 01:17:56,000 2459 01:17:56,000 --> 01:17:57,189 2460 01:17:57,189 --> 01:17:59,189 2461 01:17:59,189 --> 01:18:01,590 2462 01:18:01,590 --> 01:18:03,750 2463 01:18:03,750 --> 01:18:06,390 2464 01:18:06,390 --> 01:18:07,750 2465 01:18:07,750 --> 01:18:10,950 2466 01:18:10,950 --> 01:18:13,750 2467 01:18:13,750 --> 01:18:13,760 2468 01:18:13,760 --> 01:18:14,870 2469 01:18:14,870 --> 01:18:14,880 2470 01:18:14,880 --> 01:18:17,910 2471 01:18:17,910 --> 01:18:20,709 2472 01:18:20,709 --> 01:18:22,950 2473 01:18:22,950 --> 01:18:22,960 2474 01:18:22,960 --> 01:18:24,229 2475 01:18:24,229 --> 01:18:25,990 2476 01:18:25,990 --> 01:18:26,000 2477 01:18:26,000 --> 01:18:27,110 2478 01:18:27,110 --> 01:18:30,470 2479 01:18:30,470 --> 01:18:33,430 2480 01:18:33,430 --> 01:18:36,630 2481 01:18:36,630 --> 01:18:38,950 2482 01:18:38,950 --> 01:18:40,950 2483 01:18:40,950 --> 01:18:43,270 2484 01:18:43,270 --> 01:18:44,470 2485 01:18:44,470 --> 01:18:45,990 2486 01:18:45,990 --> 01:18:47,270 2487 01:18:47,270 --> 01:18:49,270 2488 01:18:49,270 --> 01:18:49,280 2489 01:18:49,280 --> 01:18:50,550 2490 01:18:50,550 --> 01:18:55,910 2491 01:18:55,910 --> 01:18:58,630 2492 01:18:58,630 --> 01:19:00,550 2493 01:19:00,550 --> 01:19:02,630 2494 01:19:02,630 --> 01:19:04,229 2495 01:19:04,229 --> 01:19:07,830 2496 01:19:07,830 --> 01:19:11,510 2497 01:19:11,510 --> 01:19:14,310 2498 01:19:14,310 --> 01:19:16,390 2499 01:19:16,390 --> 01:19:19,510 2500 01:19:19,510 --> 01:19:20,950 2501 01:19:20,950 --> 01:19:23,189 2502 01:19:23,189 --> 01:19:24,950 2503 01:19:24,950 --> 01:19:26,390 2504 01:19:26,390 --> 01:19:29,270 2505 01:19:29,270 --> 01:19:31,030 2506 01:19:31,030 --> 01:19:32,790 2507 01:19:32,790 --> 01:19:34,310 2508 01:19:34,310 --> 01:19:35,990 2509 01:19:35,990 --> 01:19:37,270 2510 01:19:37,270 --> 01:19:38,950 2511 01:19:38,950 --> 01:19:41,110 2512 01:19:41,110 --> 01:19:42,470 2513 01:19:42,470 --> 01:19:43,910 2514 01:19:43,910 --> 01:19:45,030 2515 01:19:45,030 --> 01:19:46,630 2516 01:19:46,630 --> 01:19:48,390 2517 01:19:48,390 --> 01:19:51,270 2518 01:19:51,270 --> 01:19:52,790 2519 01:19:52,790 --> 01:20:05,510 2520 01:20:05,510 --> 01:20:05,520 2521 01:20:05,520 --> 01:20:07,600