Sufiks ağacı növbədə

Verilmiş s sırası əvvəlcə boşdur. Sizə əməliyyatlar ardıcıllığı təqdim olunur. Hər bir əməliyyat iki növdən birinə aiddir:

1. s sırasının sonuna bir simvol əlavə edin, bu zaman sıranın uzunluğu 1 vahid artır;

2. s sırasının ilk simvolunu silin, bu zaman sıranın uzunluğu 1 vahid azalır.

Hər bir əməliyyatdan sonra həmin anda s sırasındakı fərqli alt sıranın sayını çıxışa verməlisiniz.

Giriş verilənləri

Birinci sətirdə tam ədəd q (1 ≤ q ≤ 10^4) — əməliyyatların sayı verilib. Növbəti q sətirdə əməliyyatlar verilib. Birinci növ əməliyyat "+ c" formatında verilir, burada c — latın əlifbasının kiçik hərfidir. İkinci növ əməliyyat "-" formatında verilir.

Çıxış verilənləri

q sətir çıxış verin, hər bir əməliyyatdan sonra s sırasındakı fərqli alt sıranın sayını.

Nümunələr