402220: GYM100703 C Aerotaxi

Dragon poured Princess another cup of tea. Princess sighed faintly and asked:

— Do princesses and princes in neighbouring castles have rental agreements too?

— Yes, of course! — Dragon answered, — To tell the truth, princesses are troublesome. So, every progressive dragon would rather lease his castles to a prince. However, the demand for rent of castles is so small now, many dragons have side job as taxi. As aerotaxi, I mean.

As Dragon told, the inhabitants of castles fly on dragons on business quite often. While flying they do not like to cross each other and require no one of their neighbours could see them. And a dispatcher, who schedules flights, has a hard work because of that.

Let us describe a simplified model of flights. Suppose air space is divided into n "air corridors". These air corridors are indexed, each corridor locates in certain height; the smaller the number of a corridor, the higher the corridor is.

Dragon begins his flight taking up any vacant corridor. During the flight, a dragon may descend and he does it step by step. The dispatcher demands dragons to descend only in integer moments of time and by only one corridor down. So, if a dragon flies along the jth air corridor, he can descend down to (j + 1)th air corridor (if (j + 1)th corridor exists). If a dragon occupies some air corridor, he must fly along it for at least one time unit.

Dragon moves at a constant horizontal speed during the whole flight. Time for moving between air corridors is negligible and should be considered zero. Dragon can't stop during the flight.

Dispatcher has a schedule wherein the periods of corridors' occupation are specified. Each period consists of some intervals of form (s, f) (s < f); it is believed that a dragon can occupy air corridor at interval's boundaries s and f, but not in any time strictly between s and f.

Dispatcher gets a request for a flight t time units long from another dragon, and he is to allocate some air corridors for the flight. Dragon's passenger wants to arrive at a destination as soon as possible.

Your task is to compute the time of flight's beginning and the times in which the dragon should descend (if it is necessary).

The first line contains integers n and t (1 ≤ n ≤ 100,  1 ≤ t ≤ 10000) — the number of air corridors and flight time.

Each of next n lines contain an air corridor's occupation periods. The line starts with integer c_j (0 ≤ c_j ≤ 100) — the number of time intervals. After it all the intervals are listed. An interval consists of two space-separated integers s^(j)_k и f^(j)_k (k = 1, 2, ..., c_j). It is guaranteed that 0 ≤ s^(j)₁ < f^(j)₁ < s^(j)₂ < ... < f^(j)_cj ≤ 10⁹.

Dragon (who requests a flight) is ready to begin his flight at any time starting from 0.

In the first line print an integer a — the earliest time a flight can start.

In the second line print two integers h and d — the number of air corridor where the flight starts and the number of descends.

In the third line print d space-separated integers — the times (in chronological order) in which the dragon should descend.

If there are more than one answer, choose any of them.

2 8
2 0 4 10 20
2 5 10 12 15

4
1 1
10 

5 8
2 0 2 5 10
2 0 4 7 10
1 4 6
2 0 3 5 10
2 0 5 8 10

0
3 2
3 5 

4 9
1 5 9
2 0 4 5 8
2 0 4 5 8
2 0 4 9 12

8
2 0

Let us explain the samples.

In the first sample dragon may start the flight at time 4 and occupy air corridor #1. At time 10 he descends to the 2nd air corridor. Flight ends at time 12.

In the second sample dragon may begin flight at time 0 and occupy the 3rd air corridor. At time 3 he descends to the air corridor number 4, at time 5 he descends again — to air corridor number 5.

In the third sample the earliest time of flight start is 8. Indeed, dragon can descend from the first air corridor to the second air corridor at time 4, then he stays in the second air corridor until time 5. At time 5 he descends to the 3rd air corridor, but he cannot stay in this corridor after time 5. At time 8 dragon may begin his flight in the 2nd or in the 3rd air corridor and move in the corridor until the end of the flight.