Теперь очередь Айхана и Рауля играть с лампочками. Рауль расположил в ряд лампочек, пронумерованных целыми числами от до . Первоначально некоторые из этих ламп горят, а некоторые выключены. Сегмент последовательных лампочек считается красивым, если все лампочки в этом сегменте включены. Как мы знаем, количество всех возможных сегментов лампы равно . Некоторые могут быть хорошими изначально.
Рауль сначала спрашивает Айхана, сколько красивых сегментов в последовательности лампочек в исходном состоянии. Затем, чтобы досадить Айхану, он раз либо выключает, либо включает все лампы в определенном диапазоне и каждый раз спрашивает Айхана сколько сегментов становились красивыми до текущего момента. Айхан устал отвечать на бесконечные вопросы Рауля. Помогите ему в этом задании.
В первой строке дается два целых числа и . В следующей строке дается строка , состоящая из символов и . означает, что -я лампа изначально выключена, а означает, что она включена.
В каждой из следующих строк дается по три целых числа и .
Если , Рауль выключает все лампы, включенные в интервале . Если , то он включает все лампы, выключенные в этом интервале.
В первой строке выведите количество сегментов, которые изначально были хорошими, а в следующих строках — количество сегментов, которые становились красивыми до текущего момента после выполнения соответствующего запроса.
Данная задача состоит из -и подзадач. Баллы за подзадачу начисляются только в случае успешного прохождения всех тестов, связанных с этой подзадачой.
( баллов): ;
( баллов): ;
( баллов): ;
( баллов): ;
( баллов): нет дополнительных ограничений;