Андрей, Федя и Леша — очень изобретательные ребята. В очередной раз они придумали игру для двоих игроков со строками.

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

Андрей и Леша решили сыграть в эту игру k раз. Причем, игрок, проигравший в i-й игре, делает первый ход в (i + 1)-й игре. Ребята решили, что победителем по сумме всех игр будет считаться тот, кто победил в последней (k-й) игре. Андрей и Леша уже начали играть, а Федя в это время решил посчитать: кто будет победителем, если оба игрока будут играть оптимально. Помогите ему.