Ethos OA Question

Anonymous User
91
Sep 03, 2026
Sep 03, 2026

Recoverable Elements from Range-Sum Queries

You are given an array A of N unknown integers, where 1 ≤ N ≤ 10^5.

You are given Q queries. Each query consists of two integers L and R and provides the sum of all elements from index L to R.

Using all the given queries, determine which individual elements of the array can be uniquely determined.

An element A[i] is recoverable if its value can be calculated uniquely from the given queries.

Input

The first line contains two integers:

N Q

The next Q lines contain two integers:

L R

representing a range-sum query.

Output

Print all indices i whose values can be uniquely determined.

If no element can be uniquely determined, print -1.

Constraints

  • 1 ≤ N ≤ 10^5
  • 1 ≤ Q ≤ 10^5
  • 1 ≤ L ≤ R ≤ N

Sample Input

3 2
1 3
1 2

Sample Output

3

Input:
3 2
1 3
1 2

Output:
3

Input:
5 3
1 3
3 5
1 5

Output:
1 2 3 4 5

Input:
5 2
1 2
4 5

Output:
-1

Input:
6 3
1 3
1 4
2 4

Output:
2 3 4

Input:
7 4
1 3
2 5
5 7
1 7

Output:
1 2 3 4 5 6 7

Comments (0)