Игра в Угадайку
Джэхён имеет два списка целых чисел: 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", если можно доказать, что Джэхён определенно солгал (кавычки добавлены для ясности).