У Боба много мини-фигурок. Ему нравится выставлять некоторые из них на полке над экраном своего компьютера. Боб регулярно заменяет старые фигурки новыми. Постоянно меняющееся украшение действительно доставляет удовольствие. Боб заботится о том, чтобы никогда не добавлять одну и ту же мини-фигурку более одного раза. У Боба есть только мини-фигурок, и через дней он доходит до момента, когда каждая из фигурок была добавлена, а затем убрана с полки (которая, таким образом, пуста).
У Боба очень хорошая память. Он способен запомнить, какие мини-фигурки выставлялись в каждый из прошлых дней. Итак, Боб хочет выполнить небольшое умственное упражнение, чтобы проверить свою память и вычислительные способности. Для этого Боб нумерует свои фигурки числами и выбирает последовательность целых чисел в диапазоне . Затем Боб вычисляет последовательность следующим образом: и где mod — операция по модулю, а — количество фигурок, отображаемых в день , номер которых больше или равен . Результат вычислений Боба — .
Более формально, если — подмножество , соответствующее фигуркам, выставленным на полке в -ый день, то:
пустое множество;
получается из путем вставки и удаления некоторых элементов.
Каждый элемент вставляется и удаляется ровно один раз, поэтому последнее множество также является пустым множеством. Вычисление, которое выполняет Боб, соответствует следующей программе:
Боб просит Вас проверить его расчеты. Для этого он дает Вам числа, которые он использовал при вычислении , а также журнал того, какие фигурки он добавлял или удалял каждый день. Обратите внимание, что мини-фигурка, добавленная в день и убранная в день , присутствует в день . Вы должны сообщить ему число, которое найдете в конце вычислений.
Состоит из строк.
Первая строка содержит целое число .
Строки от до описывают добавленные и удаленные фигурки. Строка содержит разделенные пробелами или , , чтобы указать, что добавляется или удаляется в день . Эта строка может быть пустой. Строка может содержать как , так и именно в этом порядке.
Строки с по описывают последовательность . Строка содержит целое число .
Выведите одно число .
сначала так как и ;
потом так как и ;
и наконец так как и .