У вас есть доска и изначально на ней написано только одно нечетное число \(x\). Ваша цель — написать на доске число \(1\).
Вы можете писать новые числа на доску, используя две следующие операции.
- Вы можете взять два числа (не обязательно разные), которые уже написаны на доске, и написать их сумму на доске. Два выбранных вами числа остаются на доске.
- Вы можете взять два числа (не обязательно разные), которые уже написаны на доске, и записать их побитовое исключающее ИЛИ (XOR) на доске. Два выбранных вами числа остаются на доске.
Выполните последовательность операций так, чтобы в конце число
\(1\) находилось на доске.
Выходные данные
В первой строке выведите \(q\) — число выполняемых операций. Затем должны следовать \(q\) строк, каждая из которых описывает одну операцию.
- Операция "сумма" описывается строкой "\(a\) + \(b\)", где \(a, b\) должны быть целыми числами, уже присутствующими на доске.
- Операция "'xor" описывается строкой "\(a\) ^\(b\)", где \(a, b\) должны быть целыми числами, уже присутствующими на доске.
Символ операции (+ или ^) должен быть отделен от \(a, b\) пробелами.Вы можете выполнить не более \(100,000\) операций (т.е. \(q\le 100,000\)), а все числа, записанные на доске, должны быть в диапазоне \([0, 5\cdot10^{18}]\). Можно доказать, что при таких ограничениях требуемая последовательность операций существует. Вы можете вывести любую подходящую последовательность операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
5
3 + 3
3 ^ 6
3 + 5
3 + 6
8 ^ 9
|
|
2
|
123
|
10
123 + 123
123 ^ 246
141 + 123
246 + 123
264 ^ 369
121 + 246
367 ^ 369
30 + 30
60 + 60
120 ^ 121
|