Скорость
Знакомы ли вы с игрой Speed? Это популярная карточная игра, в которой два игрока соревнуются, кто быстрее сможет переместить свои карты на столы.
Для игры в Speed два игрока садятся друг напротив друга. У каждого из них есть своя колода и ряд карт, а между ними расположены два стола для стопок: один слева и один справа. В рядке может быть не более четырех карт. Игра продолжается по следующим простым правилам:
Игрок может переместить карту из своего рядка на стопку, только если ранг перемещаемой карты соседствует с рангом карты на вершине стопки. Например, A и 2, 4 и 3 являются соседями. В этой игре A и K также считаются соседями.
Игрок может взять карту из своей колоды и положить её на свободное место в рядке.
Если оба игрока пытаются переместить карты на один и тот же стол одновременно, только более быстрый игрок может положить карту на стол. Другой игрок должен вернуть свою карту в рядок, так как она больше не является соседом верхней карты стопки.
Сначала каждый игрок берет четыре карты из своей колоды и кладет их лицом вверх в рядок. Если карт недостаточно, чтобы заполнить рядок, берутся все доступные карты. Игра начинается с того, что каждый игрок берет еще одну карту из колоды и одновременно кладет её на столы справа. Если колода пуста, игрок может переместить любую карту из своего рядка на стол. Затем они продолжают выполнять действия согласно описанным выше правилам, пока оба не зайдут в тупик, то есть не смогут перемещать карты. Каждый раз, когда происходит тупик, они начинают заново, каждый берет карту (или перемещает карту из своего рядка) и кладет её на правый стол, независимо от её значения. Игрок, который первым избавится от всех своих карт, выигрывает игру.
Мистер Джеймс А. Геймс настолько увлечен этой простой игрой, что решил создать роботов, которые в неё играют. Он только что завершил проектирование роботов и их программ, но не уверен в их работоспособности из-за сложности дизайна. Поэтому он попросил вас, своего друга, написать программу, которая симулирует игру роботов. Алгоритм для роботов разработан следующим образом:
Робот берет карты в порядке их раздачи.
Каждому роботу всегда дается одна или несколько карт.
В реальной игре Speed игроки сначала сортируют карты по мастям, чтобы легко определить, кто положил карту. Этот шаг пропускается в симуляции.
Игра использует только один набор карт, разделенный на две части. В двух колодах, данных роботам, может быть не более одной карты с одинаковым лицом.
В качестве подготовки каждый робот берет четыре карты и кладет их в рядок справа налево.
Если в его колоде недостаточно карт, берутся все карты из колоды.
После завершения этого шага оба робота синхронизируются и начинают игру, одновременно кладя первые карты на столы.
Если в колоде остаются карты, робот берет верхнюю и кладет её на правый стол. В противном случае робот берет крайнюю правую карту из своего рядка.
Затем два робота продолжают двигаться в соответствии с основным правилом игры, описанным выше, пока ни один из них больше не сможет перемещать карты.
Когда робот берет карту из своего рядка, он берет карту (если возможно) из колоды, чтобы заполнить пустую позицию после того, как карта была положена на стол.
Перемещение карт занимает некоторое время. Когда робот завершает укладку карты на стол, в то время как другой робот перемещается, чтобы положить карту на тот же стол, робот в движении должен немедленно отказаться от действия и вернуть карту в её исходное положение.
Робот может начать перемещение, чтобы положить карту на стопку в тот же момент, когда соседняя карта помещается на вершину стопки.
Если два робота пытаются положить карты на один и тот же стол в одно и то же время, только робот, перемещающий карту влево, может успешно положить карту из-за настроек позиции.
Когда у робота есть несколько кандидатов в его рядке, он предпочитает карты, которые можно разместить на правом столе, тем, которые нельзя. В случае, если остаются несколько вариантов, робот предпочитает более слабую карту.
Когда наступает тупиковая ситуация, роботы начинают заново, каждый кладет карту на стол, затем продолжают двигаться снова в соответствии с вышеописанным алгоритмом.
Когда один из роботов исчерпал карты, т.е. переместил все разданные карты, игра заканчивается.
Робот, который исчерпал карты, выигрывает игру.
Когда оба робота исчерпали карты одновременно, робот, который переместил более сильную карту в последнем ходе, выигрывает.
Сила карт определяется их рангами, затем мастями. Ранги сильны в следующем порядке: A > K > Q > J > X (10) > 9 > ··· > 3 > 2. Масти сильны в следующем порядке: S (пики) > H (червы) > D (бубны) > C (трефы). Другими словами, SA самая сильная, а C2 самая слабая. Роботам требуется следующее количество времени для выполнения каждого действия:
300 миллисекунд, чтобы взять карту в рядок,
500 миллисекунд, чтобы переместить карту на правый стол,
700 миллисекунд, чтобы переместить карту на левый стол, и
500 миллисекунд, чтобы вернуть карту в её исходное положение.
Отмена действия всегда занимает постоянное время 500 мс, независимо от прогресса отменяемого действия. Это время отсчитывается с момента, когда действие прерывается, а не с начала действия. Вы можете предположить, что эти роботы хорошо синхронизированы, т.е. между ними нет расхождения в часах. Например, предположим, что Роботу A дана колода "S3 S5 S8 S9 S2", а Роботу B дана колода "H7 H3 H4", тогда игра будет выглядеть, как описано ниже. Обратите внимание, что в описании "стол A" (соответственно "стол B") обозначает правый стол для Робота A (соответственно Робота B).
Робот A берет четыре карты S3, S5, S8 и S9 в свой рядок справа налево. Робот B берет все три карты H7, H3 и H4.
Затем два робота синхронизируются для начала игры. Пусть этот момент будет 0 мс.
В тот же момент Робот A начинает перемещать S2 на стол A из колоды, а Робот B начинает перемещать H7 на стол B из рядка.
На 500 мс оба робота завершают перемещение карт. Затем Робот A начинает перемещать S3 на стол A (что требует 500 мс), а Робот B начинает перемещать H3 также на стол A (что требует 700 мс).
На 1000 мс Робот A завершает укладку S3 на стол A. Робот B прерывает своё движение и начинает возвращать H3 в рядок (что требует 500 мс). В то же время Робот A начинает перемещать S8 на стол B (что требует 700 мс).
На 1500 мс Робот B завершает возвращение H3 и начинает перемещать H4 на стол A (что требует 700 мс).
На 1700 мс Робот A завершает укладку S8 и начинает перемещать S9 на стол B.
На 2200 мс Робот B завершает укладку H4 и начинает перемещать H3 на стол A.
На 2400 мс Робот A завершает укладку S9 и начинает перемещать S5 на стол A.
На 2900 мс оба робота завершают укладку карт на стол A. Поскольку Робот B перемещает карту на стол слева от него, Робот B завершает укладку H3. Робот A прерывается.
Теперь Робот B завершил перемещение всех разданных карт, поэтому Робот B выигрывает эту игру.
Входные данные
Входные данные состоят из нескольких наборов данных, каждый из которых описывается четырьмя строками. Первая строка каждого набора данных содержит целое число N_A, которое указывает количество карт, раздаваемых как колода Роботу A. Следующая строка содержит последовательность карт длиной N_A. Затем следует число N_B и последовательность карт длиной N_B для Робота B, указанные таким же образом. В последовательности карт спецификации карт разделены одним пробелом между ними. Каждая спецификация карты представляет собой строку из 2 символов. Первый символ — один из 'S' (пики), 'H' (червы), 'D' (бубны) или 'C' (трефы) и указывает масть. Второй — один из 'A', 'K', 'Q', 'J', 'X' (для 10) или цифра от '9' до '2', и указывает ранг. Поскольку эта игра играется только с одним набором карт, в каждом наборе данных не может быть более одной карты с одинаковым лицом. Конец ввода обозначается одной строкой, содержащей ноль.
Выходные данные
Для каждого набора данных выведите результат игры в одной строке. Выведите "A wins.", если Робот A выигрывает, или выведите "B wins.", если Робот B выигрывает. Никакие лишние символы в выводе не допускаются.