셔플

$1$부터 $n$까지 번호가 적힌 카드 $n$장이 있다. 처음에는 맨 위가 번호 $1$인 카드, 위에서 두 번째가 번호 $2$인 카드, …, 맨 아래가 번호 $n$인 카드가 되도록 차례로 쌓아 카드 더미를 만든다.

이 카드 더미에 대해 다음과 같은 「셔플$(x, y)$」연산을 수행하여 카드를 재배열한다. 여기서 $x, y$는 $1 \le x < y < n$을 만족하는 정수이다.

• 셔플$(x, y)$
  • $n$장의 카드를 맨 위에서부터 $x$번째까지의 카드로 이루어진 더미 $A$, $x+1$번째부터 $y$번째까지의 카드로 이루어진 더미 $B$, $y+1$번째부터 $n$번째까지의 카드로 이루어진 더미 $C$의 세 더미로 나눈다. 그런 다음 더미 $A$ 위에 더미 $B$를 얹고, 다시 그 위에 더미 $C$를 얹는다.

예를 들어 순서대로 놓인 $9$장의 카드에 「셔플$(3, 5)$」을 수행하면, 카드에 적힌 번호는 위에서부터 차례로 $6, 7, 8, 9, 4, 5, 1, 2, 3$이 된다.

처음 상태에서 $m$번의 셔플 「셔플$(x_1, y_1)$」, 「셔플$(x_2, y_2)$」, …, 「셔플$(x_m, y_m)$」을 순서대로 수행한 뒤의 카드 더미에서, 위에서부터 세어 $p$번째부터 $q$번째까지의 카드 중 번호가 $r$ 이하인 카드가 몇 장 포함되어 있는지 구하는 프로그램을 작성하라.

입력은 $m+3$개의 줄로 이루어진다.

• $1$번째 줄: 카드의 장수 $n$ ($3 \le n \le 10^9$).
• $2$번째 줄: 셔플 횟수 $m$ ($1 \le m \le 5000$).
• $3$번째 줄: 정수 $p, q, r$ ($1 \le p \le q \le n$, $1 \le r \le n$).
• $i+3$번째 줄 ($1 \le i \le m$): 공백으로 구분된 두 정수 $x_i, y_i$ ($1 \le x_i < y_i < n$).

$m$번의 셔플 후의 카드 더미에서, 위에서부터 세어 $p$번째부터 $q$번째까지의 카드 중 번호가 $r$ 이하인 카드의 장수를 출력하라.

$9$장의 더미에 「셔플$(3, 5)$」을 수행하면 카드는 위에서부터 $6, 7, 8, 9, 4, 5, 1, 2, 3$이 된다. 위에서 $3$번째부터 $7$번째까지 중 번호가 $4$ 이하인 카드는 번호 $4$와 번호 $1$의 $2$장이다.

$12$장의 더미에 「셔플$(3, 8)$」, 「셔플$(2, 5)$」, 「셔플$(6, 10)$」을 차례로 수행하면 카드는 위에서부터 $9, 10, 3, 11, 12, 4, 5, 6, 7, 8, 1, 2$가 된다. 위에서 $3$번째부터 $8$번째까지 중 번호가 $5$ 이하인 카드는 $3$장이다.