I have a problem with one task.

The main content of this task is that we are given n invervals [a; b] and number k. We have to find the maximum common range of any k intervals and print the indexes of intervals, that have maximum common range, to output.
https://i.stack.imgur.com/6aRxz.png

On the left side is an input - the first 2 numbers are respectively n - number of intervals, and k - number of any intervals having a maximum common range. The next n lines have 2 numbers a and b and they are representing the interval [a; b].

On the right side is and output. The first line contains the range of maximum interval. The next line contain k indexes of intervals that have maximum common range. The indexes are as follows:

3 8 -> index 1

4 12 -> index 2

2 6 -> ...

...

1 ≤ k ≤ n ≤ 1000000

1 ≤ a < b ≤ 10^9

The avaible memory is only 128 MB, so I can't implement interval tree for this task.

The problem is I have no idea how to implement a fast algorithm. Is anyone able to write a fast algorithm for this task?

Sorry for bad English