Addımlar
Sasha və Vasya çeçitka rəqsi ilə məşğul olmağa başladılar. Bu rəqs ayaqları yerə vurmaqla icra edilir. Onlar bu rəqsi tez öyrəndikləri üçün xoreoqrafiyada eksperimentlər etməyə qərar verdilər.
Çeçitkanın xoreoqrafiyası L və R hərflərindən ibarət ardıcıllıqla təsvir edilir. Burada L sol ayaqla, R isə sağ ayaqla vurmanı ifadə edir. Sasha başa düşdü ki, rəqsin ən maraqlı hissəsi ardıcıl olaraq eyni ayağın istifadə edilmədiyi hissədir. O, xoreoqrafiyanın dəyərini ardıcıl olaraq eyni simvolların olmadığı ən uzun ardıcıllıq kimi müəyyənləşdirdi.
Gözəl bir rəqs yaratmaq çətin bir prosesdir və optimal variant tapılana qədər bir çox kiçik dəyişikliklər tələb olunur. Buna görə Vasya hər bir dəyişiklikdən sonra xoreoqrafiyanın dəyərini bilmək istəyir. Dəyişiklik, müəyyən bir mövqedə L-in R ilə (və ya əksinə) əvəz olunmasıdır.
Başlanğıcda ardıcıllıq yalnız L hərflərindən ibarətdir.
Giriş məlumatları
Birinci sətirdə xoreoqrafiyanın uzunluğu n (1 ≤ n ≤ 200000) və dəyişikliklərin sayı q (1 ≤ q ≤ 200000) olmaqla iki tam ədəd verilir. Növbəti q sətirdə hər biri dəyişiklik baş verən mövqeni müəyyən edən bir ədəd var.
Çıxış məlumatları
Hər bir dəyişiklikdən sonra xoreoqrafiyanın dəyərini göstərən q ədəd çıxış etməlisiniz, hər biri ayrıca sətirdə.