Treasure Hunt

Have you ever heard about pirates and their treasures? Bytie found an old bottle while walking along the beach in Gdynia. The letter inside gives instructions for finding a hidden treasure, but it is quite hard to decipher. Bytie knows one thing for sure: he must find two special points in the park nearby, and the treasure is at the middle of the path connecting them.

The park has several trails. The forest is very dense, so people can only reach positions on the trails. The trail structure has an interesting property: for any two points on the trails, there is a unique path connecting them. The path may follow multiple trails, but it never visits any point more than once.

Bytie asked his friends to help explore the park. They start the treasure hunt at some point on one of the trails. They explore in phases. In each phase, one friend picks a point that was already explored and walks a number of steps from it along a trail, visiting only points that no friend has reached before.

While they explore, Bytie studies the park's structure closely. From time to time he may guess the two special points that determine the treasure's location. For each guess, he wants the point in the middle of the only path between them. Your task is to find these middle points.

There will be at most 400 000 calls to the functions init, path, and dig, and at most 1 000 000 000 points explored by Bytie's friends.