바이너리 문자열 토글

모두 0인 이진 문자열에 U번의 구간 뒤집기 연산을 적용한 뒤, U+1개 상태 중 사전순으로 가장 큰 문자열을 출력한다.

보통7누적 합그리디구현면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제4

길이가 $N$ 이고 모든 문자가 0인 바이너리 문자열 $S_0$ 이 있다. 이 문자열에 변경 연산을 $U$ 번 적용한다. $i$ 번째 연산은 $S_{i-1}$ 을 $S_i$ 로 바꾸는 연산이므로, $U$ 번의 연산이 모두 끝나면 문자열은 $S_U$ 가 된다.

$i$ 번째 연산은 두 정수 $L_i$ 와 $R_i$ 로 주어진다. 이 연산은 구간 $[L_i, R_i]$ 에 속하는 모든 문자를 뒤집는다. 즉, 양 끝을 포함한 이 구간 안에서 1은 0이 되고 0은 1이 된다.

연산을 모두 적용하면 문자열 $S_0, S_1, \dots, S_U$ 를 얻는다. 이 $U+1$ 개 문자열 중 사전 순으로 가장 뒤에 오는 것을 구하는 프로그램을 작성하시오.

첫째 줄에 $N$ 과 $U$ 가 주어진다. ( $1 \le N, U \le 100{,}000$ )

둘째 줄부터 $U$ 개 줄에 걸쳐 $L_i$ 와 $R_i$ 가 주어진다. ( $1 \le L_i \le R_i \le N$ )

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

예제 입력에서 문자열은 다음 순서로 바뀐다.