Никто не застрахован от потери документов. Даже если потерян паспорт, ситуация не является безвыходной. В паспортном столе потребуют подтвердить личность другими документами, заставят подождать несколько недель — и паспорт снова у законного владельца. Но что делать, если паспорт потерялся во время путешествия в далёкой экзотической стране? Выехать нельзя, до консульства не добраться, а языковой барьер только усугубляет проблему.

В миграционной службе одного островного государства фиксируют всех въезжающих туристов. Для идентификации туриста используется последовательность из K полей, в которую записывается составной идентификатор личности туриста в соответствии с предъявленным при въезде документом. Понятие идентификатора личности на острове довольно специфическое — нельзя предугадать, в какое из полей попадут настоящие имя, фамилия, отчество туриста, и будут ли они склеены при вводе или нет. Нельзя даже быть уверенным, что оператор заполнит всё без ошибок и не добавит при вводе что-нибудь от себя! Одно известно точно — все K полей любого идентификатора личности являются непустыми строками, состоящими только из строчных букв латинского алфавита.

Турист, обратившийся в миграционную службу, пытается, добавляя и удаляя буквы в конце полей запроса, найти свой идентификатор личности в базе данных. После каждого изменения запрос выполняется, а система отвечает, сколько идентификаторов личности удовлетворяют текущему запросу. Идентификатор личности считается удовлетворяющим запросу, если каждое из K полей в запросе является префиксом соответствующего поля идентификатора.

Изначально все K полей запроса являются пустыми строками. Турист выполнил Q запросов, изменяя текущий запрос одним из двух способов:

1. <i> + <c> : добавление символа c в конец i-го поля.

2. <i> - : удаление одного символа в конце i-го поля.

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