Гирлянда в школьном коридоре

В школьном коридоре висит гирлянда из n лампочек в ряд, пронумерованных от 1 до n. Утром все лампочки были выключены.

На переменах кто‑то из ребят устраивал «переключения»: выбирал отрезок лампочек и у каждой на этом отрезке менял состояние на противоположное (выкл ↔ вкл).

Твоя задача — узнать, как будет выглядеть гирлянда после всех таких переключений.

Формат ввода

В первой строке записаны два целых числа n и m — количество лампочек и количество переключений.

Далее идут m строк. В каждой строке два целых числа l и r (1 ≤ l ≤ r ≤ n) — отрезок лампочек, которые переключили в этот раз.

Формат вывода

Выведи строку длины n из символов 0 и 1.

0 означает, что лампочка выключена, 1 — включена. Символы должны идти в порядке лампочек от 1 до n.

Ограничения

• 2 ≤ n ≤ 8000
• 1 ≤ m ≤ 8000
• 1 ≤ l ≤ r ≤ n

Пример

Ввод:

5 3
1 3
2 5
2 2

Вывод:

11011

Ключевое наблюдение: лампочка меняет состояние каждый раз, когда отрезок [l, r] её включает. Значит, важна не «сколько раз», а чётность: если переключений было нечётное число — в итоге 1, если чётное — 0.

Прямо менять все лампочки на каждом отрезке долго: O(n*m). Вместо этого отметим только границы каждого отрезка и потом пройдём слева направо, накапливая текущую чётность.

Приём: разностный массив для XOR.

• Заводим массив diff длины n+2, где diff[i] означает «в позиции i меняется текущая чётность».
• Для каждого отрезка [l, r] делаем две отметки: начать инверсию в l и закончить после r.

Мини-сниппет: diff[l] ^= 1 diff[r+1] ^= 1

• Идём i = 1..n, поддерживаем cur — текущую чётность переключений на позиции i:

cur ^= diff[i]

• Если cur == 1, печатаем 1, иначе 0.

Почему работает: каждая отметка в diff переключает «режим» на отрезке; две отметки для одного [l, r] включают инверсию ровно на этом промежутке.

Сложность: O(n + m) по времени и O(n) по памяти.

Частая ошибка: забыть про позицию r+1 и размер n+2 (иначе выйдете за границы при r = n).