Бинарной строкой называется строка, каждый символ которой это \(\texttt{0}\) или \(\texttt{1}\). Назовем бинарную строку приличной, если в ней поровну символов \(\texttt{0}\) и \(\texttt{1}\).
Изначально у вас есть бесконечная бинарная строка \(t\), все символы которой равны \(\texttt{0}\). Вам дана последовательность целых чисел \(a\) из \(n\) обновлений, где \(a_i\) означает, что символ на позиции \(a_i\) будет изменен на противоположный (\(\texttt{0} \leftrightarrow \texttt{1}\)). Вам нужно поддерживать и изменять после каждого обновления множество \(S\) непересекающихся отрезков таких, что
- для каждого отрезка \([l,r]\) строка \(t_l \dots t_r\) является приличной бинарной строкой, и
- для каждого индекса \(i\) такого, что \(t_i = \texttt{1}\), существует отрезок \([l,r]\) в \(S\) такой, что \(l \leq i \leq r\).
Вам нужно выводить только отрезки, которые вы удаляете или добавляете в множество \(S\) после каждого обновления. В вашем ответе добавлений и удалений в \(S\) должно быть не более чем \(\mathbf{10^6}\).
Формально, пусть \(S_i\) — множество отрезков после \(i\)-го обновления, где \(S_0 = \varnothing\) (пустое множество). Определим \(X_i\) как множество отрезков, удаленных из множества после \(i\)-го обновления, и \(Y_i\) как множество отрезков, добавленных в множество после \(i\)-го обновления. Тогда для каждого \(1 \leq i \leq n\) выполняется \(S_i = (S_{i - 1} \setminus X_i) \cup Y_i\). Для каждого \(1 \leq i \leq n\) должно выполняться следующее:
- \(\forall a,b \in S_i, (a \neq b) \rightarrow (a \cap b = \varnothing)\);
- \(X_i \subseteq S_{i - 1}\);
- \((S_{i-1} \setminus X_i) \cap Y_i = \varnothing\);
- \(\displaystyle\sum_{i = 1}^n {(|X_i| + |Y_i|)} \leq 10^6\).
Выходные данные
После \(i\)-го обновления сначала одно целое число \(x_i\) — количество отрезков, которое нужно удалить из \(S\) после обновления \(i\).
В каждой из следующих \(x_i\) строк выведите два целых числа \(l\) и \(r\) (\(1 \leq l < r \leq 10^6\)), определяющие отрезок \([l,r]\), который должен быть удален из \(S\). Каждый из этих отрезков должен быть уникальным и содержаться в \(S\).обозначающее
В следующей строке выведите одно целое число \(y_i\) — количество отрезков, которое нужно добавить в \(S\) после обновления \(i\).
В каждой из следующих \(y_i\) строк выведите два целых числа \(l\) и \(r\) (\(1 \leq l < r \leq 10^6\)), определяющие отрезок \([l,r]\), который должен быть добавлен в \(S\). Каждый из этих отрезков должен быть уникальным и не содержаться в \(S\).
Общее количество добавлений и удалений после всех обновлений не должно превосходить \(\mathbf{10^6}\).
После каждого обновления после всех удалений и добавлений все отрезки в \(S\) должны быть непересекающимися и покрывать все единицы.
Можно показать, что ответ всегда существует при данных ограничениях.
Примечание
В примере вывода приведены дополнительные переводы строк для ясности, вам не обязательно их выводить.
После первого обновления множество индексов, в которых \(a_i = 1\), это \(\{1\}\). Отрезок \([1, 2]\) добавлен, поэтому \(S_1 = \{[1, 2]\}\), в нем один \(\texttt{0}\) и одна \(\texttt{1}\).
После второго обновления множество индексов, в которых \(a_i = 1\), это \(\{1, 6\}\). Отрезок \([5, 6]\) добавлен, поэтому \(S_2 = \{[1, 2], [5, 6]\}\), в каждом из них один \(\texttt{0}\) и одна \(\texttt{1}\).
После третьего обновления множество индексов, в которых \(a_i = 1\), это \(\{1, 5, 6\}\). Отрезок \([5, 6]\) удален, а отрезки \([4, 5]\) и \([6, 7]\) добавлены, поэтому \(S_3 = \{[1, 2], [4, 5], [6, 7]\}\), в каждом из них один \(\texttt{0}\) и одна \(\texttt{1}\).
После четвертого обновления множество индексов, в которых \(a_i = 1\), это \(\{1, 6\}\). Отрезок \([4, 5]\) удален, поэтому \(S_4 = \{[1, 2], [6, 7]\}\), в каждом из которых один \(\texttt{0}\) и одна \(\texttt{1}\).
После пятого обновления множество индексов, в которых \(a_i = 1\), это \(\{1\}\). Отрезок \([6, 7]\) удален, поэтому \(S_5 = \{[1, 2]\}\), в этом отрезке один \(\texttt{0}\) и одна \(\texttt{1}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
6
5
5
6
|
0
1
1 2
0
1
5 6
1
5 6
2
6 7
4 5
1
4 5
0
1
6 7
0
|