URI Online Judge | 2772


By Gustavo Policarpo, INATEL BR Brazil

Timelimit: 2

André João is a great cultivator of plants of a great city of the interior of the great Brazil. It currently has a nursery with N plants of a very peculiar species that dies when completing T consecutive days without care.

However, André has noticed that many plants have died lately, and suspect that his employee is the reason for this. So he asked his servant to write down what was done in K days so that João could blame your servant for the death of his plants.

Since Andre's plot is very large, he asked you to develop a program that, given the initial amount of plants, how long the species survives, and the intervals your employee took care of each day, tells you the plants that have remained live at the end of this period.

João ensures that all plants were cared for on day 0 and therefore are alive! And the employee ensures that he started working on day 1 and never missed a day of service!


The input consists of several test cases. The first line consists of the integers N, K, T (1 <= N, K, T <= 105). The next K lines will contain two integers l, r (1 <= l <= r <= N) meaning that the employee handled all plants in the interval [l, r] on that day.


For each test case, your program should print an integer representing the number of plants that remained alive at the end of the period, followed by their indices in ascending order. Remember, if a plant ever died, it will never come back to life;

Input Sample Output Sample

10 5 2

1 10

2 9

3 8

2 7

3 6

4 2 1

1 2

3 4

4 1 1

2 3

6 2 3 4 5 6 7


2 2 3