Có \(n\) lá bài được đánh số từ \(1\) đến \(n\). Ban đầu, các lá bài được xếp thành một chồng theo thứ tự từ trên xuống dưới là \(1,2,\ldots,n\).

Thao tác xáo bài \((x,y)\), với \(1\le x<y<n\), được thực hiện như sau:

1. Chia chồng bài hiện tại thành ba chồng: chồng \(A\) gồm các lá ở vị trí từ \(1\) đến \(x\), chồng \(B\) gồm các lá ở vị trí từ \(x+1\) đến \(y\), và chồng \(C\) gồm các lá ở vị trí từ \(y+1\) đến \(n\). Mọi vị trí đều được đếm từ trên xuống dưới.
2. Đặt chồng \(B\) lên trên chồng \(A\), rồi đặt chồng \(C\) lên trên cùng. Thứ tự các lá trong mỗi chồng con được giữ nguyên. Như vậy, thứ tự ba chồng từ trên xuống dưới trở thành \(C,B,A\).

Chẳng hạn, nếu chồng bài ban đầu có \(9\) lá, sau thao tác xáo bài \((3,5)\), thứ tự các lá từ trên xuống dưới là \(6,7,8,9,4,5,1,2,3\).

Yêu cầu

Thực hiện lần lượt \(m\) thao tác xáo bài \((x_1,y_1),(x_2,y_2),\ldots,(x_m,y_m)\) từ trạng thái ban đầu. Trong chồng bài cuối cùng, hãy đếm số lá có số hiệu không vượt quá \(r\) nằm ở các vị trí từ \(p\) đến \(q\), tính cả hai đầu và đếm từ trên xuống dưới.

Dữ liệu vào

Đọc từ đầu vào chuẩn \(m+3\) dòng:

• Dòng đầu chứa số nguyên \(n\), là số lá bài.
• Dòng thứ hai chứa số nguyên \(m\), là số thao tác xáo bài.
• Dòng thứ ba chứa ba số nguyên \(p\), \(q\), \(r\), cách nhau bởi dấu cách.
• Dòng thứ \(i+3\), với \(1\le i\le m\), chứa hai số nguyên \(x_i\), \(y_i\), cách nhau bởi một dấu cách, mô tả thao tác xáo bài thứ \(i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên, là số lá bài có số hiệu không vượt quá \(r\) nằm ở các vị trí từ \(p\) đến \(q\) sau tất cả các thao tác.

Ràng buộc

• \(3\le n\le10^9\).
• \(1\le m\le5\,000\).
• \(1\le p\le q\le n\).
• \(1\le r\le n\).
• \(1\le x_i<y_i<n\) với mọi \(1\le i\le m\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Ví dụ

9
1
3 7 4
3 5

2

Sau thao tác xáo bài \((3,5)\), thứ tự các lá bài từ trên xuống dưới là \(6,7,8,9,4,5,1,2,3\). Trong các vị trí từ \(3\) đến \(7\), có hai lá có số hiệu không vượt quá \(4\): lá số \(4\) và lá số \(1\).

12
3
3 8 5
3 8
2 5
6 10

3

Sau ba thao tác, thứ tự các lá bài từ trên xuống dưới là \(9,10,3,11,12,4,5,6,7,8,1,2\). Trong các vị trí từ \(3\) đến \(8\), có ba lá có số hiệu không vượt quá \(5\).