The popular legend says that in the book Geography, written in the first century B.C., the Greek geographer Strabo said that vegetation on the Iberian Peninsula was so dense that a squirrel could cross it from the south to the north jumping from tree to tree without ever touching the ground. Apparently, Strabo never affirmed such a thing in his book and, in fact, nowadays it is believed that the great achievement of the squirrel wasn’t even possible back then. However, let our imagination fly for a while and think that there was in fact a time in which the number of trees in the Peninsula was large enough to make the achievement possible. Considering that today this is not possible anymore, it is clear that at some point in the past a tree was cut down and caused the separation between the north region and the south region, making it impossible for squirrels to jump from branch to branch. To simplify the problem slightly, let’s assume that the territory is a squared region of size N × M in which trees (considered of thickness 0) are placed in positions (x, y). The task of the squirrel is to go from the tree in the position (0, 0) to the one in (N,M). You can assume that there is always a tree in both of them. The squirrel can jump from one tree to another if the distance between the two of them does not exceed K units. The information we have about the territory are the positions of all the trees in the beginning of times. We have to determine the position of the tree that, when cut down, stopped the squirrel from travelling from one part to the other without touching the ground. Input Each test case consists of several lines. The first of them contains N, M, K and n (1 ≤ N,M ≤ 1,000; 1 ≤ K ≤ 10; 1 ≤ n ≤ 100,000), where N, M and K have the meaning described previously and n indicates the number of trees in the territory (without counting the trees in the origin and the destination of the squirrel’s journey, which are always present). After that, there is a line for each of the trees with two integers x, y (the position of the tree). The order in which they are given is the same order followed to cut them down. It is guaranteed that all the positions are inside the territory and that two trees are never placed in the same position. Output For each test case, write a single line with the position of the first tree that made the two corners of the field to be unreachable for the squirrel. If it was never possible for the squirrel to cross the Peninsula from one part to the other, output ‘Never had the chance’. Sample Input 3324 11 22
2/2 20 31 3322 30 03 Sample Output 20 Never had the chance