Трикутники на площині#12950

Трикутники на площині

2 seconds
512 megabytes
Hard

На площині задано 3 \cdot n точок так, що жодні три точки не лежать на одній прямій. Потрібно побудувати трикутників таким чином, щоб виконувались такі умови:

1. Кожна точка є вершиною лише одного трикутника.

2. Для будь-яких двох трикутників площа їхнього перетину дорівнює .

Можна показати, що за обмежень задачі це завжди можливо.

Input

У першому рядку задано одне ціле число — кількість трикутників, які необхідно побудувати.

У наступних 3 \cdot n рядках задано по два цілих числа x_i, y_i — координати точок.

1 \leq n \leq 500,

1 \leq x_i, y_i \leq 10^9.

Всі точки обов’язково попарно різні.

Output

Виведіть рядків, кожен з яких містить три числа — індекси точок, які утворюють відповідний трикутник.

Якщо існує декілька можливих способів утворити трикутників, виведіть будь-який.

Examples

Example

Loading
Loading

Note

Перший приклад.