Kassandra is participating in the Arena Olympics of Sparta. In order to win the arena fight, she has to knockout all the other $$$N$$$ fighters.
Being a computer scientist, she wanted to do it while preserving her energy as much as possible, so she wants to win the fight without being noticed by any of the other fighters. To be more exact, she knows the position of each other fighter in the arena, the angle of the center of his field of view, and the range of his field of view.
If she knocks a fighter out while she's in the field of view of another fighter, she will be noticed and she would have to fight everyone face on. So she wonders if there exists an order of fighters to knockout such that no one notices her during the whole process.
Print any permutation such that if she knocks-out the fighters in this order, she won't be noticed. Or print $$$-1$$$ if there exists no such permutation.
Note that Kassandra can move freely while not knocking someone out to get to the position of any other fighter.
The first line of the input will contain an integer $$$N$$$ $$$(1 \le N \le 3000)$$$.
Each of the following lines will contain 4 integers each: $$$x_i$$$, $$$y_i$$$, $$$a_i$$$, $$$r_i$$$ $$$(-10^{6} \le x_i, y_i \le 10^{6}, 0 \le a_i \le 359, 0 \le r_i \le 89)$$$ - the $$$x$$$ coordinate, $$$y$$$ coordinate, the angle of the center of the field of view, and the range of the field of view of the $$$i_{th}$$$ fighter respectively. No two fighters share the same position.
If there exists such a permutation, print the order of the ids of the $$$N$$$ participants on a single line separated by a space. Otherwise, print $$$-1$$$.
4 -2 1 35 25 -3 -2 35 25 0 -3 110 25 2 1 245 25
2 4 3 1
2 -3 -3 45 45 3 3 225 45
-1
The field of view ranges from the angle $$$a-r$$$ to the angle $$$a+r$$$.
Below is the illustration of the first case:
