Jewel Magic

Mən sehrbazam. Mənim zümrüd və inci sırğam var. Mən sırğaya yeni daşlar əlavə edə və ya köhnə daşları çıxara bilərəm. Hətta sırğanın ardıcıl bir hissəsini tərsinə çevirə bilərəm. İstənilən vaxt, əgər siz iki daşa işarə edib məndən soruşsanız ki, bu iki daşdan başlayan daş sırğalarının ən uzun ümumi prefiksinin (LCP) uzunluğu nədir, mən sizin sualınıza dərhal cavab verə bilərəm. Siz məndən daha yaxşısını edə bilərsinizmi?

Rəsmi olaraq, sizə 0 və 1 simlərindən ibarət bir sırğa veriləcək. Siz dörd növ əməliyyatla məşğul olmalısınız (aşağıdakı təsvirlərdə, L cari sırğanın uzunluğunu göstərir və daş mövqeləri soldan sağa doğru 1 -dən L-ə qədər nömrələnir):

Giriş verilənləri

Bir neçə test halı olacaq. Hər bir test halının ilk sətri bir tam ədəd n və m (1 ≤ n, m ≤ 200,000) ehtiva edir, burada n başlanğıcda olan incilərin sayıdır, m isə əməliyyatların sayıdır. Növbəti sətir uzunluğu n olan bir 01 simini ehtiva edir. Növbəti m sətirin hər biri bir əməliyyatı ehtiva edir. Giriş faylı son-of-file (EOF) ilə tamamlanır. Giriş faylının ölçüsü 5 MB-dan çox deyil.

Çıxış verilənləri

Hər bir tip-4 əməliyyat üçün cavabı çıxarın.

Nümunələr

Qeyd

1 0 1 əməliyyatından sonra sim: 1000100001100 3 7 10 əməliyyatından sonra sim: 1000101000100 2 9 əməliyyatından sonra sim: 100010100100