Залізничне депо#1807

Залізничне депо

1 секунда

64 мегабайти

Дуже легка

Залізничне депо — це складна система залізничних колій, що використовується для зберігання, сортування або навантаження/розвантаження залізничних вагонів. У цій задачі залізничні колії значно простіші, і нас цікавить лише з'єднання двох поїздів в один.

Кожен із двох поїздів складається з декількох залізничних вагонів. Кожен вагон містить один тип товару, який позначається додатним цілим числом до $1000000$ . Два поїзди прибувають справа різними коліями, як показано на діаграмі вище. Щоб з'єднати два поїзди, ви можете взяти вагон із початку будь-якого з поїздів і приєднати його до кінця нового поїзда, що формується ліворуч. Якщо всі вагони з одного поїзда вже перевезено, то залишок вагонів з іншого поїзда переміщується вліво по одному. Усі вагони зрештою мають бути переміщені вліво. Залежно від того, який поїзд обирається на кожному кроці, формуються різні порядки для поїзда, що відправляється ліворуч. Наприклад, порядок $1, 1, 1, 2, 2, 2$ 1,1,1,2,2,2 можна отримати, завжди вибираючи спочатку всі вагони з верхнього поїзда, або $2, 1, 2, 1, 2, 1$ 2,1,2,1,2,1 — по черзі беручи вагони з обох поїздів.

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

Вхідні дані

Вхідні дані складаються з декількох випадків. Перша строка містить два додатних цілих числа $N_{1}$ N_1 $N_{2}$ N_2, що означають кількість вагонів у кожному поїзді (щонайменше $1$ і не більше $1000$ вагонів у кожному поїзді). Друга строка містить $N_{1}$ N_1 додатних цілих чисел (до $1000000$ ), що задають продукти у першому поїзді від початку до кінця. Третя строка містить $N_{2}$ N_2 додатних цілих чисел, що ідентифікують продукти у другому поїзді (у такому ж форматі). Четверта строка містить $N_{1} + N_{2}$ N_1 + N_2 додатних цілих чисел, які представляють бажаний порядок вагонів у поїзді, що відправляється (у такому ж форматі).

Кінець вхідних даних позначається як $N_{1} = N_{2} = 0$ N_1 = N_2 = 0.

Вихідні дані

Для кожного випадку виведіть у окремому рядку possible, якщо бажаний порядок отримати можливо, або not possible — якщо ні.

Приклади

Приклад 1