시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB339735.000%

문제

길이가 N이고 모든 문자가 0인 바이너리 문자열 S0이 있다. 이 문자열에 변경 연산을 총 U번 할 것이고, 변경 연산이 끝난면 다른 문자열로 바뀌게 된다. i번째 연산은 Si-1을 Si로 바꾸는 연산이다. 따라서, U번의 변경 연산이 모두 끝나게 되면 문자열은 SU가 된다.

변경 연산은 (Li, Ri)와 같은 형태이다. 연산은 구간 [Li, Ri] (양 끝도 포함)에 속하는 모든 1을 0으로 바꾸고, 0을 1로 바꾸는 것이다.

모든 연산이 끝나게 되면, S0, S1, ..., SU를 구할 수 있게 된다. 이 U+1개의 바이너리 문자열 중에서 사전 순으로 가장 뒤에 오는 것을 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 N과 U가 주어진다. (1 ≤ N, U ≤ 100,000) 둘째 줄부터 U개의 줄에 Li와 Ri가 주어진다. (1 ≤ Li ≤ Ri ≤ N)

출력

U+1개의 문자열 중에서 사전 순으로 가장 뒤에 오는 것을 첫째 줄에 출력한다.

예제 입력 1

10 10
9 10
6 10
9 10
1 8
3 5
3 3
3 4
3 9
4 8
7 7

예제 출력 1

1111100011

힌트

문자열은 다음과 같이 변하게 된다.

  • S0 = 0000000000
  • S1 = 0000000011
  • S2 = 0000011100
  • S3 = 0000011111
  • S4 = 1111100011
  • S5 = 1100000011
  • S6 = 1110000011
  • S7 = 1101000011
  • S8 = 1110111101
  • S9 = 1111000001
  • S10 = 1111001001

출처