12:30PM

시간 제한2초메모리 제한1024 MB

요약
길이가 주어진 두 시간 체계의 이름 붙은 구간들과 두 체계 사이의 대응 시각들이 주어질 때, 각 체계의 구간 순서를 복원하거나 Ambiguous 또는 Inconsistent를 판정한다.
난이도

어려움10점 중 8점

유형
완전 탐색, 구현, 수학, 조합론
정답자
아직 제출이 없습니다

문제

Люди из стран, где обычно для обозначения времени используется 24-часовая система, часто путаются, когда попадают в страну, где используется 12-часовая система (AM и PM). Ведь в этой системе есть несколько относительно нелогичных моментов, например, 12:00PM означает полдень и наступает сразу после 11:59AM. Но еще хуже жителям одной планеты в системы Альдебарана. Они используют особо сложную и неудобную систему обозначения времени.

На этой планете используют две системы обозначения времени. В каждое системе nn-часовой день делится на несколько отрезков различной длины и в каждом отрезке часы отсчитываются независимо.

В система Альде день делится на mm отрезков. Первый отрезок содержит a_1a\_1 часов и обозначается AA, второй отрезок содержит a_2a\_2 часов и обозначается AB, \dots, mm-й отрезок содержит a_ma\_m часов и обозначается A\,где, где \\ --- mm-й символ латинского алфавита.

В система Баран день делится на kk отрезков. Первый отрезок содержит b_1b\_1 часов и обозначается BA, второй отрезок содержит b_2b\_2 часов и обозначается BB, \dots, kk-й отрезок содержит b_kb\_k часов и обозначается B\#, где \# --- kk-й символ латинского алфавита.

Однако есть небольшая проблема. На самом деле все не так просто. В каждой системе день действительно делится на отрезки соответствующей длины, но порядок отрезков в каждом дне не фиксирован. Так, например, в один из дней отрезки в системе Альде могут идти в порядке 3, 2, 1, а отрезки в системе Баран --- в порядке 1, 4, 2, 3 (если в этих системах 3 и 4 отрезка, соответственно).

Однажды к вам в руки попал дневник жителя этой планеты. Он делал отметки о различных интересных моментах времени в обеих временных системах. Так что у вас есть некоторая информация о соответствии времен в различных системах. Можете ли вы выяснить порядок следования отрезков в обеих системах в этот день?

입력

Первая строка входного файла содержит nn --- количество часов в дне на планете (1≤n≤991 \le n \le 99). Вторая строка содержит число mm, после которого следуют числа a_1,a_2,…,a_ma\_1, a\_2, \ldots, a\_m (1≤m≤81 \le m \le 8, 1≤a_i≤n1 \le a\_i \le n, сумма всех a_ia\_i равна nn). Третья строка содержит число kk, после которого следуют числа b_1,b_2,…,b_kb\_1, b\_2, \ldots, b\_k (1≤k≤81 \le k \le 8, 1≤b_i≤n1 \le b\_i \le n, сумма всех b_ib\_i равна nn).

Четвертая строка входного файла содержит ll --- количество известных соотношений между временами в обеих системах (0≤l≤1000 \le l \le 100). Следующие ll строк содержат соотношения. В каждом соотношении времена заданы как XX:YYCC, где XX --- количество часов, YY --- количество минут, а CC означает название отрезка. XX изменяется от 00 до 98 (к счастью, жители планеты используют 00:00AA, 00:01AA, и т.д. для обозначения времени в первом часе отрезка), YY изменяется от 00 до 59, CC изменяется от AA до A\$ или от BA до B#.

출력

Если вы не можете восстановить информацию о порядке следования отрезков в дне в обеих системах из-за неоднозначности, выведите "Ambiguous" во входной файл. Если не существует ни одного способа восстановить порядок следования отрезков, выведите "Inconsistent". В противном случае выведите порядок следования отрезков в каждой из систем, следуя формату, приведенному в примере.

힌트

В первом примере если в системе Альде 14-часовой отрезок был бы первым, то 06:30AA соответствовало бы 06:30BA (или 06:30BB). Так что 10-часовой отрезок идет первым. А значит в системе Баран первым идет отрезок BB.

예제3

  1. 예제 1

    입력
    24
    2 14 10
    2 12 12
    1
    06:30AA=04:30BA
    
    예상 출력
    Alde system: 2 1
    Baran system: 2 1
    
  2. 예제 2

    입력
    24
    2 12 12
    2 12 12
    1
    11:30AA=11:30BB
    
    예상 출력
    Ambiguous
    
  3. 예제 3

    입력
    24
    2 12 12
    2 12 12
    1
    11:30AA=11:31BB
    
    예상 출력
    Inconsistent