Informatica Online Judge

  카드섞기 [0241 / 00F1]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 26   Total Tried : 51


The Champion of this Problem (C++) : gs18115 - ms / 3424byte
My Best Submission (C++) : N/A

[]

Background

1부터 n까지 번호가 적힌 n장의 카드가 있다. 우선 가장 위에 있는 카드가 1번이고 위에서 부터 2번째 있는 카드가 2번, ... ,제일 아래 있는 카드가 n번카드가 되도록 카드 더미를 만든다.



카드 더미에 대해서 셔플(x,y)라고 불리는 조작을 하면 카드의 배열이 변한다. (x, y는 1 <= x < y < n인 정수)
- 셔플(x,y)
n장의 카드를 맨 위로부터 x번째 까지를 더미 A, x+1번째 부터 y번째 카드까지를 더미 B, y+1번째부터 n번째카드 까지를 더미C로 하는 3개의 더미로 나뉜다.
그리고, 더미 A위에 더미 B를 쌓고, 그 위에 더미C를 쌓는다.

예를 들면, 순서대로 쌓여 있는 9장의 카드에 대해서 셔플(3,5)를 행하면, 9장의 카드에 적힌 번호는 위에서부터 6,7,8,9,4,5,1,2,3이 된다.



최초의 더미로 부터 m회 셔플(셔플(x1,y1), 셔플(x2,y2), ... , 셔플(xm,ym))을 순서대로 행한 후 카드 더미에 대해서 위에서 부터 p장째 부터 q장째 카드들 중에 번호가 r이하인 카드가 몇장 있는지를 구하는 프로그램을 작성하시오.

Input

입력은 첫째 줄에는 카드의 매수 n(3<=1,000,000,000(10^9))이 있고, 둘째 줄에는 셔플의 횟수를 나타내는 m(5,000이하의 자연수)이 주어진다.
셋째 줄에는 p, q, r이 주어진다. (1 <= p <= q <= n, 1 <= r <= n) 다음 줄 부터 m줄에 걸쳐서 x, y(1 <= x < y <= n)정수가 공백으로 구분되어 입력된다.

Output

m회 셔플한 후 카드의 더미에서 p부터 q사이에 r이하의 카드가 몇장 있는지를 출력하시오.

IO Example

입출력예시1>
입력
9
1
3 7 4
3 5

출력
2


입출력예시2>
입력
12
3
3 8 5
3 8
2 5
6 10

출력
3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]