Кто-то порубил кур доктора Агоса. В ярости он обращается к единственному, что всё ещё приносит ему утешение: OLED-экрану. Сегодня он хочет, чтобы экран был почти полностью чёрным.

Экран состоит из одной строки из $$$n$$$ пикселей. Его рисунок задаётся бинарной строкой $$$s$$$; $$$s_i = 0$$$ означает, что $$$i$$$-й пиксель тёмный, а $$$s_i = 1$$$ — что он горит.

Доктор Агос называет непрерывный отрезок пикселей раздражающим, если при чтении слева направо как двоичного целого числа его значение делится на $$$3$$$. Более формально, отрезок от позиции $$$l$$$ до позиции $$$r$$$ ($$$1 \le l \le r \le n$$$) имеет значение $$$$$$ \sum_{i=l}^{r} s_i \cdot 2^{r-i}. $$$$$$ Ведущие нули разрешены. Отрезок, состоящий только из тёмных пикселей, имеет значение $$$0$$$, которое также делится на $$$3$$$.

Пусть $$$f(s)$$$ — количество раздражающих отрезков. Отрезки с разными парами концов $$$(l,r)$$$ учитываются отдельно, даже если рисунки их пикселей совпадают.

Доктор Агос хочет получить рисунок с не более чем тремя горящими пикселями, который минимизирует $$$f(s)$$$ среди всех бинарных строк длины $$$n$$$, в том числе строк с более чем тремя единицами. Помогите ему построить такой рисунок.

Можно доказать, что ответ всегда существует.