Вам дано целое число $$$n$$$.

Вы должны найти список пар $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, ..., $$$(x_q, y_q)$$$ ($$$1 \leq x_i, y_i \leq n$$$) который удовлетворяет следующему условию.

Рассмотрим некоторую функцию $$$f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$$$ (мы определяем $$$\mathbb{N}$$$ как множество положительных целых чисел). Другими словами, $$$f$$$ это функция, возвращающая положительное целое число по паре положительных целых чисел.

Давайте рассмотрим массив $$$a_1, a_2, \ldots, a_n$$$, где изначально $$$a_i = i$$$.

Вы сделаете $$$q$$$ операций, в $$$i$$$-й из них вы сделаете:

1. присвоите $$$t = f(a_{x_i}, a_{y_i})$$$ ($$$t$$$ это временная переменная, она используется только для следующих двух присвоений);
2. присвоите $$$a_{x_i} = t$$$;
3. присвоите $$$a_{y_i} = t$$$.

Другими словами, вам нужно одновременно заменить $$$a_{x_i}$$$ и $$$a_{y_i}$$$ на $$$f(a_{x_i}, a_{y_i})$$$. Обратите внимание, что в течение процесса значение $$$f(p, q)$$$ всегда одинаково для заданных положительных целых чисел $$$p$$$ и $$$q$$$.

В конце должно быть не больше двух различных чисел в массиве $$$a$$$.

Это должно быть выполнено для любой функции $$$f$$$.

Найдите любой возможный список пар. Количество пар должно не превосходить $$$5 \cdot 10^5$$$.