Algorithm


A. Points in Segments
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a set of n segments on the axis Ox��, each segment has integer endpoints between 11 and m inclusive. Segments may intersect, overlap or even coincide with each other. Each segment is characterized by two integers li�� and ri�� (1lirim1≤��≤��≤�) — coordinates of the left and of the right endpoints.

Consider all integer points between 11 and m inclusive. Your task is to print all such points that don't belong to any segment. The point x belongs to the segment [l;r][�;�] if and only if lxr�≤�≤�.

Input

The first line of the input contains two integers n and m (1n,m1001≤�,�≤100) — the number of segments and the upper bound for coordinates.

The next n lines contain two integers each li�� and ri�� (1lirim1≤��≤��≤�) — the endpoints of the i-th segment. Segments may intersect, overlap or even coincide with each other. Note, it is possible that li=ri��=��, i.e. a segment can degenerate to a point.

Output

In the first line print one integer k — the number of points that don't belong to any segment.

In the second line print exactly k integers in any order — the points that don't belong to any segment. All points you print should be distinct.

If there are no such points at all, print a single integer 00 in the first line and either leave the second line empty or do not print it at all.

Examples
input
Copy
3 5
2 2
1 2
5 5
output
Copy
2
3 4
input
Copy
1 7
1 7
output
Copy
0

Note

In the first example the point 11 belongs to the second segment, the point 22 belongs to the first and the second segments and the point 55 belongs to the third segment. The points 33 and 44 do not belong to any segment.

In the second example all the points from 11 to 77 belong to the first segment.

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e2 + 1;
int n, m, a[N], b[N];
vector<int> sol;

int main() {
  scanf("%d %d", &n, &m);
  for(int i = 0; i < n; ++i)
    scanf("%d %d", a + i, b + i);

  for(int i = 1; i <= m; ++i) {
    bool ok = true;
    for(int j = 0; j < n; ++j) {
      if(i >= a[j] && i <= b[j]) {
        ok = false;
        break;
      }
    }
    if(ok)
      sol.push_back(i);
  }

  printf("%d\n", int(sol.size()));
  for(int i = 0; i < sol.size(); ++i)
    printf("%d ", sol[i]);
  puts("");

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3 5
2 2
1 2
5 5

Output

x
+
cmd
2
3 4
Advertisements

Demonstration


Codeforces Solution-A. Points in Segments-Solution in C, C++, Java, Python,Points in Segments,Codeforces Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+