수제 선물 (gift)

Adam은 Bob에게 선물하기 위해 수제 목걸이를 만들고 있다. 목걸이는 왼쪽부터 오른쪽까지 $0$에서 $n-1$까지 번호가 매겨진 $n$개의 구슬로 이루어진다. 각 구슬의 색은 빨간색 또는 파란색 중 하나이다. Bob은 Adam에게 목걸이에 대한 $r$개의 요구 사항 목록을 보냈다. $i$번째 요구 사항($0 \leq i < r$)은 위치 $a[i]$부터 $b[i]$까지의 구슬에 서로 다른 색이 $x[i]$개 있어야 한다는 뜻이다.

Adam이 Bob의 모든 요구 사항을 만족하는 구슬 배치를 찾도록 돕거나, 그러한 배치가 불가능한지 판별하라.

구현 세부사항

다음 프로시저를 구현해야 한다.

int construct(int n, int r, int[] a, int[] b, int[] x)

• $n$: 구슬의 개수.
• $r$: 요구 사항의 개수.
• $a$: 길이가 $r$인 배열로, 각 요구 사항의 시작 위치.
• $b$: 길이가 $r$인 배열로, 각 요구 사항의 끝 위치.
• $x$: 길이가 $r$인 배열로, 각 요구 사항에서 서로 다른 색의 개수.
• 이 프로시저는 정확히 한 번 호출된다.
• 배치를 만들 수 있다면, 이 프로시저는 배치를 보고하기 위해 craft를 정확히 한 번 호출한 뒤 $1$을 반환해야 한다.
• 그렇지 않다면, 이 프로시저는 craft를 한 번도 호출하지 않고 $0$을 반환해야 한다.

프로그램은 배치를 보고하기 위해 다음 프로시저를 호출해야 한다.

void craft(string s)

• $s$: 길이가 $n$인 문자열. $i$번째 구슬이 빨간색이면 $s[i]$는 'R'이고, 파란색이면 'B'이다.

예제

예제 1

다음 호출을 살펴보자.

construct(4, 2, [0, 2], [2, 3], [1, 2])

이는 총 $4$개의 구슬과 다음과 같은 $2$개의 요구 사항이 있다는 뜻이다.

• 위치 $0$부터 $2$까지에는 서로 다른 색이 $1$개 있어야 한다.
• 위치 $2$부터 $3$까지에는 서로 다른 색이 $2$개 있어야 한다.

구슬 $0$부터 $2$까지를 빨간색으로 칠하고 구슬 $3$을 파란색으로 칠하면 이를 만족할 수 있다.

따라서 construct 프로시저는 다음 호출을 해야 한다.

• craft("RRRB")

그런 다음 $1$을 반환해야 한다.

이 경우 요구 사항을 만족하는 배치는 여러 개이며, 그중 어느 것이든 정답으로 인정된다.

예제 2

다음 호출을 살펴보자.

construct(3, 3, [0, 1, 0], [1, 2, 2], [1, 1, 2])

이는 총 $3$개의 구슬과 다음과 같은 $3$개의 요구 사항이 있다는 뜻이다.

• 위치 $0$부터 $1$까지에는 서로 다른 색이 $1$개 있어야 한다.
• 위치 $1$부터 $2$까지에는 서로 다른 색이 $1$개 있어야 한다.
• 위치 $0$부터 $2$까지에는 서로 다른 색이 $2$개 있어야 한다.

이 경우 모든 요구 사항을 만족하는 구슬 배치는 존재하지 않는다.

따라서 construct 프로시저는 craft를 한 번도 호출하지 않고 $0$을 반환해야 한다.

제약 조건

• $1 \leq n, r \leq 500\,000$
• $0 \leq a[i] \leq b[i] \leq n-1$ (모든 $0 \leq i \leq n-1$에 대해)
• $1 \leq x[i] \leq 2$ (모든 $0 \leq i \leq n-1$에 대해)

서브태스크

1. (10점) $x[i] = 1$ (모든 $0 \leq i \leq n-1$에 대해)
2. (15점) $x[i] = 2$ (모든 $0 \leq i \leq n-1$에 대해)
3. (20점) $1 \leq n, r \leq 18$
4. (25점) $1 \leq n, r \leq 2000$
5. (30점) 추가 제약 조건이 없다.

샘플 그레이더는 다음 형식으로 입력을 읽는다.

• $1$번째 줄: $n\;\;r$
• $2 + i$번째 줄($0 \leq i \leq r - 1$): $a[i]\;\;b[i]\;\;x[i]$

샘플 그레이더는 다음 형식으로 답을 출력한다.

• $1$번째 줄: construct의 반환값.
• $2$번째 줄: $s$
• construct의 반환값이 $0$이면 $s$는 출력되지 않는다.