Идеальная пара
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

В мире Барби важно, чтобы любая пара Барби-Кен была идеальна, ведь нет ничего прекрасней идеального. Но не всем везет в поиске партнера, поэтому был создан «Клуб Поиска Идеального Партнера».

Для того что бы облегчить поиск партнера, каждый впервые пришедший должен был пройти опрос, а после, в зависимости от ответов, каждой Барби и каждому Кену выдавалась строка, означающая его тип. Она так же размещалась на специальной доске в здании клуба, где любой желающий мог подойти и присмотреть себе подходящего партнера.

К несчастью, никто не хотел переводить специальные строки в более понятные характеристики, поэтому партнеров стали выбирать так: брали строчку Барби и склеивали ее со строчкой Кена, и если получившаяся строчка оказывалась палиндромом, то пара считалась идеальной, ведь не существует строки идеальнее палиндрома.

В скором времени для того, чтобы собирать статистику по возможным идеальным парам, решили после каждого обновления доски выводить, сколько идеальных пар может быть создано из анкет, закрепленных на доске. Доска представляет из себя два поля: поле со строками Кенов и поле со строками Барби. Изначально на доске нет ни одной строки. И каждый раз, когда кто-то проходит тест, после его окончания результат закрепляется на доску. Также иногда кто-то из участников клуба может найти себе партнера (из клуба или снаружи), после чего его строку снимают с доски.

Для каждого изменения доски выведите, сколько идеальных пар можно составить из текущего набора строк.

Входные данные

В первой строке ввода дано целое число $$$t$$$ — количество изменений доски ($$$1 \le t \le 10^{6}$$$).

Изменения задаются следующим образом:

Гарантируется, что суммарная длина строк по всем запросам первого и третьего типа (новая строка) не превосходит $$$5 \cdot 10^6$$$.

Выходные данные

После каждого изменения доски выведите, сколько идеальных пар можно составить из текущих строк.

Пример

Входные данные
6
1 + ken
2 + nek
1 + barbie
2 + ibrab
1 - ken
1 - barbie
Выходные данные
0
1
1
2
1
0