\(1\)부터 \(n\)까지 번호가 적힌 카드가 \(n\)장 있다. 맨 위가 번호 \(1\), 위에서 2번째가 번호 \(2\), \(\ldots\), 맨 아래가 번호 \(n\)이 되도록 쌓아 카드 더미를 만든다. 이 더미에 「셔플\((x, y)\)」라는 조작을 하여 카드를 다시 쌓는다. \(x\), \(y\)는 \(1 \le x \lt y \lt 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\)이 된다. 처음 더미에서 셔플\((x_1, y_1)\), \(\ldots\), 셔플\((x_m, y_m)\)을 차례로 한 뒤, 위에서 \(p\)장째부터 \(q\)장째까지 가운데 번호가 \(r\) 이하인 카드가 몇 장인지 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(n\)
\(m\)
\(p\) \(q\) \(r\)
\(x_1\) \(y_1\)
\(\vdots\)
\(x_m\) \(y_m\)
- 첫째 줄에 카드 장수 \(n\)이 주어진다.
- 둘째 줄에 셔플 횟수 \(m\)이 주어진다.
- 셋째 줄에 정수 \(p\), \(q\), \(r\)이 공백 하나로 구분되어 주어진다.
- 다음 \(m\)줄에 \(x_i\), \(y_i\)가 공백 하나로 구분되어 주어진다.
- \(3 \le n \le 10^9\)
- \(1 \le m \le 5000\)
- \(1 \le p \le q \le n\)
- \(1 \le r \le n\)
- \(1 \le x_i \lt y_i \lt n\)
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에, \(m\)번 셔플한 뒤 위에서 \(p\)장째부터 \(q\)장째까지 가운데 번호가 \(r\) 이하인 카드의 장수를 출력한다.
셔플\((3, 5)\) 뒤 카드는 위에부터 \(6, 7, 8, 9, 4, 5, 1, 2, 3\)이다. 위에서 3장째부터 7장째에 번호가 \(4\) 이하인 카드는 \(4\)와 \(1\)의 2장이다.