Массив \(b\) из \(m\) положительных целых чисел называется хорошим, если для всех пар \(i\) и \(j\) (\(1 \leq i,j \leq m\)), значение \(\max(b_i,b_j)\) делится на \(\min(b_i,b_j)\).
Вам дан массив \(a\) из \(n\) положительных целых чисел. Вы можете выполнять следующую операцию:
- Выберите индекс \(i\) (\(1 \leq i \leq n\)) и целое число \(x\) (\(0 \leq x \leq a_i\)), затем добавьте \(x\) к \(a_i\). Другими словами, \(a_i := a_i+x\).
- После этой операции должно выполняться \(a_i \leq 10^{18}\).
Постройте последовательность из не более чем \(n\) операций, после которой массив \(a\) будет хорошим. Можно показать, что в ограничениях задачи такая последовательность операций всегда существует.
Выходные данные
Для каждого набора входных данных сначала выведите целое число \(p\) (\(0 \leq p \leq n\)) — количество операций в вашем решении.
Для каждой из следующих \(p\) строк, выведите два целых числа через пробел — \(i\) и \(x\).
Вам не нужно минимизировать число операций. Можно показать, что решение всегда существует.
Примечание
В первом примере массив \(a\) становится после операций равным \([5,5,5,5]\). Легко видеть, что \([5,5,5,5]\) — хороший.
Во втором примере массив \(a\) изначально хороший.
В третьем примере массив \(a\) становится после операций равным \([10,5,350,5,10]\), что является хорошим массивом.
В четвертом примере после выполнения операций массив \(a\) становится равным \([60,10,20]\), что является хорошим массивом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
2 3 5 5
2
4 8
5
3 4 343 5 6
3
31 5 17
|
4
1 2
1 1
2 2
3 0
0
5
1 3
1 4
2 1
5 4
3 7
3
1 29
2 5
3 3
|