H. Летняя дихотомия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В параллель ZPP Летней Какой-то Школы подали заявки T школьников. Оргкомитет школы может зачислить любое количество из них, но зачислено должно быть не менее t школьников. Зачисленных школьников необходимо разделить на две группы каким-либо образом (возможно, что в одной из групп не окажется школьников!).

Во время смены школьников параллели ZPP будут учить n преподавателей. Из-за особенностей образовательного процесса каждый из преподавателей должен быть приписан к одной из двух групп (возможно, что к какой-то из групп не будет приписан ни один преподаватель!). i-ый из преподавателей согласен работать в группе при условии, что в ней будет не менее li и не более ri школьников (иначе ему будет либо слишком скучно, либо слишком трудно). Кроме этого, некоторые из преподавателей не ладят друг с другом и поэтому не могут работать в одной группе; всего существует m пар конфликтующих преподавателей.

Вам, как завучу Летней Какой-то Школы, досталась нелегкая задача: определить, сколько школьников зачислить в каждую из групп, а также в каких группах будет преподавать каждый из преподавателей.

Входные данные

В первой строке через пробел записано два целых числа t и T (1 ≤ t ≤ T ≤ 109).

Во второй строке через пробел записано два целых числа n и m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105).

В i-ой из следующих n строках через пробел записаны целые числа li и ri (0 ≤ li ≤ ri ≤ 109).

В следующих m строках описаны пары конфликтующих преподавателей. В каждой из этих строк через пробел записано по два целых числа — номера преподавателей в паре. Нумерация преподавателей начинается с единицы. Гарантируется, что никакой преподаватель не конфликтует сам с собой, и каждая пара конфликтующих преподавателей присутствует в списке ровно один раз.

Выходные данные

Если распределение возможно, в первой строке выведите одно слово «POSSIBLE» (без кавычек). Во второй строке выведите через пробел два целых числа n1 и n2 — количество школьников в первой и второй группе соответственно, при этом должно выполняться ограничение t ≤ n1 + n2 ≤ T. В третьей строке выведите n символов, i-ый из которых равен 1 или 2, если i-ый преподаватель будет приписан к первой или второй группе соответственно. Если существует несколько допустимых распределений школьников и преподавателей по группам, разрешается вывести любое из них.

Если искомого распределения не существует, выведите единственное слово «IMPOSSIBLE» (без кавычек).

Примеры
Входные данные
10 20
3 0
3 6
4 9
16 25
Выходные данные
POSSIBLE
4 16
112
Входные данные
1 10
3 3
0 10
0 10
0 10
1 2
1 3
2 3
Выходные данные
IMPOSSIBLE