Chasing Chmyaaax#11696
You have defeated the evil Chmyaaax and the cats are free now. Unfortunately, he managed to escape to the "Link-Cut" planet system. Will you be able to find him there?..
You have learned that the evil Chmyaaax has escaped to the Link-Cut system, and you have set out to pursue him. Unfortunately, after his defeat, he managed to do one little dirty trick: he broke your fuel tank, and now it's empty. Now you have only one means of transportation left: Gravitational maneuvers!
The space where the events take place can be represented as a -plane. Initially, you are at position (s_x, s_y). There are meteors in the space, each determined by its location (mx_i, my_i). Since your ship was built by Lucy, gravitational maneuvers work non-standardly. Specifically, you can choose two meteors and mirror your position relative to the middle of the path between them. There is an infinite vertical line at = coordinate that separates our Solar system from the Link-Cut system. To enter the Link-Cut system your -coordinate needs to be at least .
Formally, let (x_i, y_i) be the position of the -th meteor and let (s_x, s_y) be your initial position. Then each maneuver can be described by a pair of indices and :
If your current position is (px,py), then it will become (\frac{mx_i+mx_j}{2}-(px - \frac{mx_i+mx_j}{2}),\frac{my_i+my_j}{2}-(py - \frac{my_i+my_j}{2})).
Here is the example of how maneuver works:
Maneuver from point P_{old} to point P_{new} relative to the middle of the way between meteors m_1 and m_2
Now Lucy is preparing the ship for maneuvers and she needs to know the minimum number of maneuvers required for you to enter the Link-Cut system. Help her with this challenging task or determine it is impossible.
The first line contains two integers and (2 \le n \le 2 \cdot 10^5, 0 \le r \le 10^{15}) — the number of meteors and the -coordinate, from which the Link-Cut system starts off.
The second line contains two integers s_x and s_y (0 \le s_x, s_y \le 10^{15}) — your initial position.
Each of the next lines contains a pair of integers mx_i and my_i (0 \le mx_i, my_i \le 10^{15}) — the location of the -th meteor.
Please note that some positions (including yours) can be the same.
In the only line, you need to output the minimum number of maneuvers required for you to enter the Link-Cut system. If it is impossible to reach it, output «Chmyaaaax has escaped».
Example
Example 1
Example 2
The first example is shown in the picture in the statement: P_{old}(0; 0) is your initial point and P_{new}(7; 4) is your new point after performing one maneuver relative to the middle of the way between the only two meteors. 7 \ge r = 6, which means that you will enter the Link-Cut system after this operation. And initially your -coordinate is , which is less than r = 6, thus the answer cannot be .
( points): mx_1, my_1, mx_2, my_2 \ge r;
( points): r, mx_i, my_i \le 10^5;
( points): r, mx_i, my_i \le 10^8;
( points): no additional constraints.