RCB - Richest_Beggar


Akash has recently joined a new company and on his first day at office his colleague Mr. Goyal (who is always ready to mock him :XD) gave him an interesting problem to solve.

Assume N beggars, numbered from 1 to N are standing outside a temple. It is given that 'k' people visit the temple on that particular day.

Every person who comes out of the temple selects some beggars from 'l' to 'r' and gives each beggar from 'l' to 'r' 1$ each.

The task is to find out the beggar (or beggars) who gets the maximum amount of money at the end of the day.

Akash does not want to get insulted on the first day, so he has asked you to help him.

Input

The first line of input contains an integer N denoting the number of beggars.

The second line contains an integer 'k' denoting the number of people who visit the temple.

Each of the next k lines contains two integers 'l' and 'r'.

Output

The first line of output contains the maximum amount of money a beggar gets.

The next line consists the beggars who get the maximum amount of money at the end of the day.

Constraints

1 <= N <= 2 * 100000

1 <= k <= 100000

1 <= l, r <= 100000

Example

Input:
6
3
1 3
2 4
5 6

Output:
2
2 3

hide comments
robosapien: 2020-07-17 00:06:16

easy problem. stupid mistake costed me 3 WAs :/

sapjv: 2019-09-17 16:09:55

Very Easy, Use Difference Array !

Vipul Srivastava: 2019-08-30 16:46:29

@suraj please rejudge all the submissions, so if your intention is that n^2 code doesn't get AC then it will be fulfilled

Last edit: 2019-08-30 16:46:43
suraj1611: 2019-08-30 16:44:06

@Vipul : The test cases have been modified! Thanks for pointing it out!

cynder: 2019-08-29 21:07:22

Elegant solution in O(n) :D

Vipul Srivastava: 2019-08-29 12:42:47

Square time complexity gets accepted here.... @ suraj was it the intention or the test cases are weak?

suraj1611: 2019-08-27 20:20:42

Rectified! Sorry! @Vipul

Vipul Srivastava: 2019-08-27 09:02:24

Submit button?


Added by:suraj1611
Date:2019-08-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All