추측 게임

재현이는 두 정수 리스트 $a_1, \dots, a_N$ 과 $b_1, \dots, b_M$ 을 가지고 있다. 제프리는 이 수들을 알고 싶지만, 재현이는 값을 직접 알려 주지 않는다. 그래서 제프리는 "$a_i + b_j$ 는 얼마나 큰가?" 형태의 질문을 여러 번 던진다. 그런데 재현이는 정확한 값조차 말하지 않고, "적어도 $c$ 이다" (즉 $a_i + b_j \ge c$) 또는 "많아야 $c$ 이다" (즉 $a_i + b_j \le c$) 라고만 답한다. 모든 답을 모은 뒤에도 제프리는 아무리 애를 써도 모순 없는 수들을 복원하지 못하고, 재현이가 몇몇 답에서 거짓말을 한 것은 아닌지 의심하기 시작한다. 재현이의 답들이 주어질 때, 모든 답과 일치하는 정수 리스트가 존재하는지, 아니면 재현이가 반드시 거짓말을 했다고 증명되는지 판별하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 양의 정수 $N$, $M$, $Q$ 가 적힌 줄로 시작하며, 각각 두 리스트의 길이와 제프리가 던진 질문의 개수를 뜻한다. 이 값들은 $2 \le N + M \le 1000$ 과 $1 \le Q \le 10000$ 을 만족한다. 이어지는 $Q$ 개의 줄은 각각 i j <= c 또는 i j >= c 형태이며, 전자는 $a_i + b_j \le c$ 를, 후자는 $a_i + b_j \ge c$ 를 나타낸다. 여기서 $-1000 \le c \le 1000$ 이다. 입력의 끝은 0 0 0 한 줄로 표시되며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄을 출력한다. 재현이의 모든 답과 일치하는 정수 $a_1, \dots, a_N$ 과 $b_1, \dots, b_M$ 이 존재하면 Possible 을, 답들이 모순임(즉 재현이가 반드시 거짓말을 했음)을 증명할 수 있으면 Impossible 을 출력한다.