Железная дорога
Сортировочная станция — это сложная система железнодорожных путей, предназначенная для хранения, сортировки или погрузки/разгрузки железнодорожных вагонов. В этой задаче железнодорожные пути значительно упрощены, и нас интересует только объединение двух поездов в один.
Каждый из двух поездов состоит из нескольких вагонов. Каждый вагон перевозит один тип продукции, обозначенный положительным целым числом, не превышающим 1,000,000. Два поезда прибывают справа по отдельным путям, как показано на диаграмме выше. Чтобы объединить два поезда, мы можем выбрать вагон в начале любого из поездов и прикрепить его к концу формируемого слева поезда. Если все вагоны из одного поезда уже перемещены, то оставшиеся вагоны из другого поезда будут перемещены влево по одному. В итоге все вагоны должны быть перемещены влево. В зависимости от того, какой поезд справа выбирается на каждом шаге, мы получим разные варианты для отправляющегося поезда слева. Например, мы можем получить порядок 1,1,1,2,2,2, всегда выбирая вагоны из верхнего поезда, пока все они не будут перемещены. Мы также можем получить порядок 2,1,2,1,2,1, чередуя выбор вагонов из двух поездов.
Для облегчения дальнейшей обработки на других сортировочных станциях позже в поездке (а также в пункте назначения) начальник станции получил желаемый порядок продукции для отправляющегося поезда. В этой задаче вы должны определить, возможно ли получить желаемый порядок, учитывая порядок продукции для двух поездов, прибывающих на станцию.
Входные данные
Входные данные состоят из нескольких случаев. Первая строка содержит два положительных целых числа N_1 и N_2, которые обозначают количество вагонов в каждом поезде. В каждом поезде имеется как минимум 1 и как максимум 1000 вагонов. Вторая строка содержит N_1 положительных целых чисел (до 1,000,000), обозначающих продукцию на первом поезде от начала до конца. Третья строка содержит N_2 положительных целых чисел, обозначающих продукцию на втором поезде (в том же формате, что и выше). Наконец, четвертая строка содержит N_1+N_2 положительных целых чисел, задающих желаемый порядок для отправляющегося поезда (в том же формате, что и выше).
Конец ввода обозначается N1 = N2 = 0.
Выходные данные
Для каждого случая выведите "possible", если возможно получить желаемый порядок, или "not possible", если это невозможно.