Для вектора \(\vec{v} = (x, y)\), определим длину \(|v| = \sqrt{x^2 + y^2}\).
Аллен немного перебрал в баре, который находится в начале координат. Существуют \(n\) векторов \(\vec{v_1}, \vec{v_2}, \cdots, \vec{v_n}\). Аллен сделает \(n\) шагов. Так как Аллен дезориентирован, на \(i\)-м шаге он либо сделает шаг на вектор \(\vec{v_i}\), либо на вектор \(-\vec{v_i}\). Другими словами, если его позиция сейчас равна \(p = (x, y)\), то он окажется либо в \(p + \vec{v_i}\), либо в \(p - \vec{v_i}\).
Аллен не хочет уйти далеко от дома (он также находится в баре). Помогите ему найти последовательность шагов (последовательность знаков векторов) такую, чтобы его финальная позиция \(p\) удовлетворяла ограничению \(|p| \le 1.5 \cdot 10^6\).
Выходные данные
Выведите единственною строку, содержащую \(n\) целых чисел \(c_1, c_2, \cdots, c_n\), каждое из которых равно либо \(1\), либо \(-1\). Ваше решение будет зачтено, если финальная позиция \(p = \sum_{i = 1}^n c_i \vec{v_i}\) удовлетворяет \(|p| \le 1.5 \cdot 10^6\).
Можно показать, что решение всегда существует при данных ограничениях.