IOI University is a bleak competitive society where students are referred to by their exam rankings rather than their names. There are $N$ students at the university, and for each $0 \le i \le N - 1$, student $i$ is the student who ranked $i+1$ in the midterm exam.

To prepare for the final exam, the students formed their own mentoring groups. Each mentoring group can be represented by two integers $0 \le L \le R \le N - 1$, meaning that all students except those with numbers between $L$ and $R$ inclusive belong to this group.

One morning, an email was sent to all students at IOI University stating, "There is at least one mentoring group." Let this be the morning of Day 1. From the evening of Day $d \ge 1$, the following situation unfolds:

• If a student deduces after the morning of Day $d$ that there exists a mentoring group that excludes them, the student feels unfair and files a complaint before the end of the evening of Day $d$. Once a complaint is filed, all mentoring group activities are terminated before the morning of Day $d+1$.
• If no student deduces that there exists a mentoring group that excludes them, no complaint is filed, and mentoring group activities continue on the morning of Day $d+1$. Through this, all students gain the common knowledge that "no one filed a complaint on Day $d$."

Other than this, students do not share information with each other in any way. That is, they only know the mentoring groups they belong to, the members of each such group, and whether a complaint has been filed. Students always deduce propositions that can be inferred from the information they possess, and they do not deduce propositions that could be false based on their information.

You are an outsider who is close to all students at IOI University and know all mentoring groups and their members. Given information about all $M$ mentoring groups, write a program that finds the day $k$ on which a complaint is filed and the numbers of the students who file a complaint on day $k$. If no complaint is ever filed, return $-1$.

Note that all information about the mentoring groups, such as the number of groups $M$, the members of each group, the constraints of the problem and subtasks, and the fact that all groups are of the form excluding students in a specific range, is known only to you as an outsider, and is completely unknown to each student.

Implementation Details

You must implement the following function:

pair<int, vector<int> > complaint(int N, vector<int> L, vector<int> R)

• $L, R$: Integer arrays of size $M$. For all $0 \le i \le M - 1$, the $i$-th mentoring group consists only of students whose numbers are less than $L[i]$ or greater than $R[i]$.
• This function must return a pair consisting of an integer $k$ and an integer array $V$ of size at most $N$. $k$ is the day the complaint is filed, and $V$ must contain the numbers of the students who file a complaint on day $k$ in increasing order. If no complaint is ever filed, $k$ should be $-1$ and $V$ should be an empty array.

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $1 \le N \le 250\,000$
• $1 \le M \le 250\,000$
• For all $0 \le i \le M - 1$, $0 \le L[i] \le R[i] \le N - 1$

Subtasks

1. (12 points) $N, M \le 10$
2. (6 points) For all $0 \le i \le M - 1$, $L[i] = R[i]$.
3. (15 points) $N, M \le 2\,500$.
4. (10 points) For all $0 \le i, j \le M - 1$, the intervals $[L[i], R[i]]$ and $[L[j], R[j]]$ are either disjoint or one contains the other.
   • That is, if $L[i] < L[j]$, then $R[i] < L[j]$ or $R[j] \le R[i]$ holds.
5. (18 points) For all $0 \le i \le M - 2$, $L[i] < L[i + 1]$ and $R[i] < R[i + 1]$ hold.
6. (39 points) No additional constraints.

Examples

Input 1

6 3
1 4
2 5
3 3

Output 1

1
3

Note

Input 2

10 4
1 4
4 7
8 9
2 6

Output 2

2
4 8 9

Note

Input 3

5 1
0 4

Output 3

1
0 1 2 3 4

Note

Sample grader

The sample grader receives input in the following format:

• Line 1: $N \ M$
• Line $2 + i$ ($0 \le i \le M - 1$): $L[i] \ R[i]$

The sample grader outputs the following:

• Line 1: The value $k$ returned by the complaint function.
• Line 2: The elements of the array $V$ returned by the complaint function, separated by spaces.

Note that the sample grader may differ from the grader used in actual grading.