ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Open Ural SU Championship 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Chinese Hockey 2

Time limit: 1.0 second
Memory limit: 64 MB
Oh, these hockey fans! They attend all the games of their favorite team and don't care about their money or spare time. Often fans of a hockey team from a city of Harbin gather in a small group of several thousand people to visit the next match of their idols.
Harbin fans are well-organized. Each of them has his own ID number that is an integer from 1 to n. All n fans decided to visit the next match, so the fanclub ordered m buses and assigned the fans to buses in such a way, that there would be at least a and at most b fans in each bus. To avoid the mess, the buses were numbered 1 through m, and every fan got a tag with a number of his bus. It is known that fans with larger IDs were assigned to buses with larger numbers.
An emigrant from Vietnam, Li Si Tsyn is not accustomed to the discipline of his comrades yet. When he came to a boarding station, he realized he had forgotten a tag with his bus number at home! Li Si Tsyn asked several friends for their IDs and their bus numbers. He wants to use this information to calculate the number of his bus.


The first line contains space-separated integers n, m, a and b (2 ≤ mn ≤ 105; 1 ≤ abn; manmb). The second line contains an integer r (1 ≤ rn), which is the Li Si Tsyn's ID. The third line contains an integer s (1 ≤ sn − 1), which is the number of fans asked by Li Si Tsyn. The i-th of the next s lines contains space-separated integers ri and fi (1 ≤ rin; 1 ≤ fim), which are the ID of a fan and the number of his bus. All ri are distinct and none of them is equal to r.


If the information received from the fans is inconsistent, output a single word “IMPOSSIBLE”. Otherwise, in the first line you should output the number of options that could be written on the Li Si Tsyn's tag, and in the the second line you should output a space-separated list of these options in ascending order.


16 4 1 16
2 2
4 3
2 3
Problem Author: Alex Samsonov
Problem Source: XV Open USU Championship
To submit the solution for this problem go to the Problem set: 1778. Chinese Hockey 2