손수 만든 선물

Adam은 Bob에게 줄 선물로 목걸이를 손수 만들고 있다. 목걸이는 구슬 $n$개로 이루어지며, 구슬에는 왼쪽에서 오른쪽으로 $0$부터 $n-1$까지 번호가 붙어 있다. 각 구슬의 색은 빨간색 또는 파란색 중 하나다. Bob은 Adam에게 목걸이에 대한 요구 사항 $r$개를 보냈다. $i$번째 요구 사항($0 \leq i \lt r$)은 위치 $a[i]$부터 $b[i]$까지의 구슬이 서로 다른 색 $x[i]$가지를 가져야 한다는 것이다.

Bob의 요구 사항을 모두 만족하는 구슬 배치를 하나 찾거나, 불가능하다면 불가능함을 판별하라.

• $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$에 대해)