Во время экзамена Reycloer встретил интересную задачу, но он не смог сразу придумать решение. Время истекает! Пожалуйста, помогите ему.
Изначально вам дан массив \(a\), состоящий из \(n \ge 2\) целых чисел, и вы хотите заменить все элементы в нём на \(0\).
За одну операцию вы выбираете два индекса \(l\) и \(r\) (\(1\le l\le r\le n\)) и делаете следующее:
- Пусть \(s=a_l\oplus a_{l+1}\oplus \ldots \oplus a_r\), где \(\oplus\) обозначает побитовое исключающее ИЛИ;
- Затем, для всех \(l\le i\le r\), замените \(a_i\) на \(s\).
Вы можете использовать указанную выше операцию в любом порядке не более \(8\) раз в общей сложности.
Найдите такую последовательность операций, что после выполнения операций в этом порядке, все элементы в \(a\) станут равными \(0\). Можно доказать, что решение всегда существует.
Выходные данные
Для каждого набора входных данных в первой строке выведите одно целое число \(k\) (\(0\le k\le 8\)) — количество операций, которые вы используете.
Затем выведите \(k\) строк, в \(i\)-й строке выведите два целых числа \(l_i\) и \(r_i\) (\(1\le l_i\le r_i\le n\)), обозначающие, что вы выбираете \(l_i\) и \(r_i\) в \(i\)-й операции.
Обратите внимание, что вам не нужно минимизировать \(k\). Если существует несколько решений, вы можете вывести любое из них.
Примечание
В первом наборе входных данных, так как \(1\oplus2\oplus3\oplus0=0\), после выполнения операции на отрезке \([1,4]\), все элементы в массиве станут равными \(0\).
Во втором наборе входных данных после первой операции массив станет равным \([3,1,4,15,15,15,15,6]\), после второй операции массив станет равным \([0,0,0,0,0,0,0,0]\).
В третьем наборе входных данных:
| Операция | \(a\) до | | \(a\) после |
| \(1\) | \([\underline{1,5},4,1,4,7]\) | \(\rightarrow\) | \([4,4,4,1,4,7]\) |
| \(2\) | \([4,4,\underline{4,1},4,7]\) | \(\rightarrow\) | \([4,4,5,5,4,7]\) |
| \(3\) | \([4,4,5,5,\underline{4,7}]\) | \(\rightarrow\) | \([4,4,5,5,3,3]\) |
| \(4\) | \([\underline{4,4,5},5,3,3]\) | \(\rightarrow\) | \([5,5,5,5,3,3]\) |
| \(5\) | \([5,5,5,\underline{5,3,3}]\) | \(\rightarrow\) | \([5,5,5,5,5,5]\) |
| \(6\) | \([\underline{5,5,5,5,5,5}]\) | \(\rightarrow\) | \([0,0,0,0,0,0]\) |
В четвертом наборе входных данных исходный массив содержит только \(0\), поэтому нам не нужно выполнять никаких операций с ним.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4
1 2 3 0
8
3 1 4 1 5 9 2 6
6
1 5 4 1 4 7
5
0 0 0 0 0
7
1 1 9 9 0 1 8
3
100 100 0
|
1
1 4
2
4 7
1 8
6
1 2
3 4
5 6
1 3
4 6
1 6
0
4
1 2
6 7
3 4
6 7
1
1 2
|