Бинарная строка — это строка, состоящая из символов 0 и/или 1. Назовем бинарную строку чередующейся, если в ней нет двух одинаковых соседних символов. Например, строки 0, 1, 101, 0101 — чередующиеся.

Для бинарной строки определим чередующуюся $$$k$$$-раскраску следующим образом:

• для каждого символа строки выбирается цвет от $$$1$$$ до $$$k$$$;
• для каждого цвета, если выписать все символы строки, покрашенные в этот цвет, в том порядке, в котором они идут в строке, мы получим чередующуюся строку.

Например, для строки 100111 существует чередующаяся $$$3$$$-раскраска: покрасим символы $$$2$$$ и $$$6$$$ в цвет $$$1$$$, символы $$$1$$$, $$$3$$$, и $$$4$$$ в цвет $$$2$$$, а символ $$$5$$$ — в цвет $$$3$$$. Тогда для каждого из трех цветов строка, состоящая только из символов этого цвета, будет чередующаяся (для цвета $$$1$$$ это 01, для цвета $$$2$$$ — 101, для цвета $$$3$$$ — 1).

Вам дана бинарная строка $$$s$$$. Вам нужно обрабатывать запросы двух типов:

• $$$1$$$ $$$i$$$ — заменить символ $$$s_i$$$ на противоположный (0 на 1, 1 на 0);
• $$$2$$$ $$$l$$$ $$$r$$$ — посчитать минимальное $$$k$$$ такое, что для строки $$$s_l s_{l+1} s_{l+2} \dots s_r$$$ существует чередующаяся $$$k$$$-раскраска.