스마트 홈의 교체 예약

문제

스마트 홈 제어기에 1번부터 N번까지의 장치가 연결되어 있다. 각 장치의 상태는 꺼짐을 뜻하는 0 또는 켜짐을 뜻하는 1이다. 제어기는 장치의 상태를 나중에 바꾸는 예약 명령을 받는다. 한 장치에는 실행을 기다리는 예약을 최대 하나만 유지하며, 새 명령을 받으면 그 장치의 기존 예약을 취소하고 새 명령으로 교체한다. 각 명령은 도착 시각 t, 장치 번호 d, 목표 상태 s, 지연 시간 w로 이루어진다. 명령을 처리하면 먼저 d번 장치에 남아 있는 예약을 취소한다. 그다음 시각 t+w에 d번 장치의 상태를 s로 바꾸는 예약을 만든다. 목표 상태가 현재 상태와 같아도 명령을 똑같이 처리하므로, 기존 예약은 취소된다. 취소된 예약은 원래 실행 시각이 되어도 아무 효과가 없다. 명령의 지연 시간이 0이면 해당 명령을 처리하는 즉시 장치의 상태를 목표 상태로 바꾸며, 실행을 기다리는 예약은 남기지 않는다. 지연 시간이 양수이면 명령을 받은 시점에는 장치의 상태가 바뀌지 않는다. 예약이 실행되면 장치의 상태를 바꾼 뒤 그 예약은 사라진다. 같은 장치의 상태가 여러 번 바뀌어도 각 변경을 순서대로 반영한다. 시각이 같은 예약 실행과 명령 도착이 있다면, 그 시각에 실행될 유효한 예약을 모두 실행한 뒤 도착한 명령을 처리한다. 같은 시각에 도착한 명령들은 입력 순서대로 처리한다. 서로 다른 장치의 예약이 동시에 실행되는 순서는 결과에 영향을 주지 않는다. 입력의 명령 도착 시각은 감소하지 않는다. 마지막 명령을 처리한 뒤에도 남아 있는 예약을 모두 실행한다. 초기 상태와 전체 명령 기록이 주어졌을 때, 더 이상 실행할 예약이 없는 시점의 모든 장치 상태를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 Q가 주어진다. 1≤N≤10,000, 0≤Q≤10,000이다.
둘째 줄에 1번부터 N번 장치의 초기 상태가 공백으로 주어진다. 각 상태는 정수 0 또는 1이다.
다음 Q개 줄에 정수 t,d,s,w가 공백으로 주어진다. 0≤t≤1,000,000,000, 1≤d≤N, s∈{0,1}, 0≤w≤1,000,000,000이다. 명령의 t는 입력 순서대로 감소하지 않는다. 예약 실행 시각 t+w는 2,000,000,000 이하이며, 마지막 명령의 도착 시각을 넘어도 유효하다.

출력

모든 명령을 처리하고 남은 예약까지 모두 실행한 뒤, 1번부터 N번 장치의 상태를 공백으로 구분하여 한 줄에 출력한다. 명령이 없다면 초기 상태를 출력한다.

2 4
0 1
0 1 1 10
3 1 0 2
5 2 0 0
6 1 1 1

1 0

1 3
0
0 1 1 5
5 1 0 0
5 1 1 3

1

3 0
1 0 1

1 0 1

출처: Devin.KR 자체 제작