Дан набор из \(n\) (\(n\) всегда равно степени \(2\)) элементов, содержащих все целые числа \(0, 1, 2, \ldots, n-1\) единожды.
Найдите \(\frac{n}{2}\) пар элементов таких, что:
- Каждый элемент набора принадлежит ровно одной паре.
- Сумма по всем парам побитового И элементов пары должна быть в точности равна \(k\). Формально, если \(a_i\) и \(b_i\) — элементы \(i\)-й пары, то должно выполняться \(\)\sum_{i=1}^{n/2}{a_i \& b_i} = k,\(\) где \(\&\) обозначает операцию побитового И.
Если существует несколько решений, найдите любое из них. Если решений не существует, выведите \(-1\).
Выходные данные
Для каждого набора входных данных, если решения не существует, выведите одну строку, содержащую \(-1\).
В противном случае выведите \(\frac{n}{2}\) строк, \(i\)-я их них должна содержать \(a_i\) и \(b_i\) — элементы \(i\)-й пары.
Если существует несколько решений, выведите любое. Порядок пар и элементов в парах не имеет значения.
Примечание
В первом наборе входных данных \((0\&3)+(1\&2) = 0\).
Во втором наборе \((0\&2)+(1\&3) = 1\).
В третьем наборе \((0\&1)+(2\&3) = 2\).
В четвертом наборе решения не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 0
4 1
4 2
4 3
|
0 3
1 2
0 2
1 3
0 1
2 3
-1
|