e-olymp
Задачи

Covid-19

Covid-19

З метою запобігання поширенню захворювання на коронавірус було вирішено виявити контактних осіб і відправити їх на самоізоляцію.

Контактними особами вважаються ті, хто знаходився поруч із особами, які захворіли на коронавірус не менше 5 хвилин.

Особам, які не є контактними, але знаходилися поруч із контактними не менше 5 хвилин запропоновано зробити тести на коронавірус.

Визначте список осіб, які потрібно відправити на самоізоляцію та список осіб, яким потрібно зробити тест на коронавірус.

Вхідні дані.

У першому рядку задано загальну кількість осіб N (3N1000).

Другий рядок містить число M – кількість осіб, хворих на коронавірус, та їх список Ci (1iM).

У третьому рядку розміщене число K – кількість контактів осіб.

Далі наступні К рядків описують інформацію про контакти – три цілих числа (два з них – номери осіб, третє число – кількість хвилин, які вони контактували).

Вихідні дані.

У першому рядку в порядку зростання виведіть через один пробіл номери контактних осіб (яких потрібно відправити на самоізоляцію), другому рядку у порядку зростання – номери осіб, яким потрібно зробити тест на коронавірус.

Пояснення

Z10.png

Відповідно до вхідних даних особа 4 є хворою на коронавірус

Оскільки особа 4 контактувала з особою 3 не менше 5 хвилин (6 хвилин), то 3 є контактною особою і підлягає самоізоляції

Особи 2 і 5 контактували з особою 3 не менше 5 хвилин (7 та 6 хвилин відповідно), тому вони підлягають тестуванню на коронавірус

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
5
1 4
4
1 2 3
2 3 7
3 5 6
3 4 6
Выходные данные #1
3
2 5