Гра "Вгадайка"
Джехюн має два списки цілих чисел: a_1, ..., a_N та b_1, ..., b_M. Джеффрі хоче дізнатися, які це числа, але Джейхюн не хоче розкривати їх напряму. Тому Джеффрі ставить Джейхюну запитання у формі "Яке значення a_i+b_j?" Джейхюн не дає точної відповіді; натомість він каже або "Це принаймні c," або "Це не більше c." (Так, Джейхюн просто не хоче ділитися своїми числами з будь-якої причини.) Отримавши відповіді Джейхюна, Джеффрі намагається вгадати числа, але не може їх зрозуміти, як би не старався. Він починає підозрювати, що Джейхюн міг збрехати, відповідаючи на деякі запитання. Напишіть програму, щоб допомогти Джеффрі.
Вхідні дані
Вхід складається з кількох тестових випадків. Кожен тестовий випадок починається з рядка, що містить три додатні цілі числа N, M та Q, які позначають довжини списків Джейхюна та кількість запитань, які задав Джеффрі. Ці числа задовольняють умови 2 ≤ N + M ≤ 1000 та 1 ≤ Q ≤ 10000. Кожен з наступних Q рядків має форму i j <= c або i j >= c. Перше представляє a_i + b_j ≤ c, а друге представляє a_i + b_j ≥ c. Гарантується, що −1000 ≤ c ≤ 1000. Вхід завершується рядком з N = M = Q = 0.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить "Possible", якщо існують цілі числа a_1, ..., a_N та b_1, ..., b_M, які узгоджуються з відповідями Джейхюна, або "Impossible", якщо можна довести, що Джейхюн точно збрехав (лапки додані для ясності).