Duck Tape

You recently discovered Duck Tape™, a new product that claims to hold anything together; even your sanity. Despite the extraordinary potential, you have been using the tape to seal the lids on cardboard boxes. To be completely sealed, every position across the top of a box lid must be covered by at least one piece of Duck Tape. Unfortunately, you live life recklessly – tearing off strips of tape at will and placing them randomly on the box. Given the start and end positions of each piece of tape and the start and end positions of the box lid, write a program that tells you if the pieces of tape will together seal the box lid completely.

The box lid starts at position $S$ and ends at position $E$. Each piece of tape starts at position $s_i$ and ends at position $e_i$. Positions are integers. In total, the number of tape pieces is $N$.

All positions are inclusive, this means that

• If a piece of tape goes from 1 to 4 then the tape covers positions 1, 2, 3, and 4.
• If the box lid goes from -1 to 2 then each position -1, 0, 1, and 2 must be covered by at least one piece of tape.

Input

• The first line contains three integers that we'll call $N$, $S$, and $E$. These are the number of tape pieces, the start position of the box lid, and the end position of the box lid.
• For each $N$ pieces of tape, the start $s_i$ and end $e_i$ positions will appear space separated on a single line.

Output

If the pieces of tape together cover the box lid completely (from $S$ to $E$) then print 1. Otherwise, print 0.

Constraints

• $1 \le N \le 10^5$, there is at least one, and at most $100,000$, pieces of tape.
• $S, E, s_i, e_i \in \mathbb{Z}$, positions are integers.
• $S \le E$, the start position is never greater than the end position for the box lid.
• $s_i \le e_i$, the start position is never greater than the end position for all pieces of tape.
• $-10^9 \le s_i, e_i \le 10^9$, a piece of tape can start and end at a position from negative one billion to positive one billion.
• $-10^9 \le S, E \le 10^9$, the box lid can start and end at a position from negative one billion to positive one billion.

Subtasks

Subtasks give partial points by adding additional constraints.

• Subtask 1 (25%):
  • $N \le 500$, there are at most five hundred pieces of tape.
  • $0 \le S, E, s_i, e_i \le 500$, positions are restricted to non-negative integers no greater than five hundred.
• Subtask 2 (25%):
  • $N \le 500$, there are at most five hundred pieces of tape.
  • $-500 \le S, E, s_i, e_i \le 500$, positions are restricted to integers from negative five hundred up to positive five hundred.
• Subtask 3 (25%): $N \le 500$, there are at most five hundred pieces of tape.
• Subtask 4 (25%): No additional constraints.

Sample Explanations

1. All box lid positions from $S=10$ to $E=15$ are covered by a single piece of tape from $s_1=9$ to $e_1=15$, so output a 1.
2. Position $12$ between $S=10$ and $E=15$ is not covered by any piece of tape, so output 0.
3. All positions between $S=3$ and $E=120$ are covered by at least one piece of tape, so output 1.