종이 띠

면접 대비

시간 제한6초메모리 제한1024 MB

요약

검은 띠 위에 색 띠를 순서대로 붙이며 위에 붙은 띠가 아래를 가릴 때, 마지막에 보이는 각 구간의 색과 길이를 출력하고 같은 색이 붙어 있으면 하나로 합칩니다.

난이도: 보통10점 중 4점
유형: 구현, 배열, 시뮬레이션, 정렬
정답자: 아직 제출이 없습니다

문제

잭은 길이가 $L$ cm인 검은색 종이 띠를 하나 가지고 있다. 그는 이 검은 띠 위에 색깔이 있는 종이 띠들을 붙여 나간다. 새로 붙이는 띠는 항상 검은 띠 위에 딱 맞게 올라간다고 가정한다. 모든 띠의 폭(너비)은 서로 같다. 새로 붙인 띠는 그 아래에 있던 색을 가린다.

마지막에 겉으로 보이는 각 구간의 색과 길이를 구하여라.

입력

첫째 줄에 검은 띠의 길이 $L$ 과 색 띠의 개수 $N$ 이 주어진다. 이어지는 $N$ 개의 줄에는 각 색 띠를 나타내는 세 정수가 주어진다: 색 번호 $K$ ( $1 \le K \le 100$ ), 검은 띠의 시작점으로부터 그 색 띠의 시작 위치까지의 거리 $A$ , 그리고 끝 위치까지의 거리 $B$ ( $0 \le A < B \le L$ )이다. 검은색의 색 번호는 $0$ 이다. 맨 처음의 띠만 검은색이고, 나머지는 모두 색이 있는 띠이다. 색 띠들은 입력에 주어진 순서대로 위에 붙여진다.

출력

원래 검은 띠의 시작부터 끝까지 순서대로, 최종 결과에서 각 색이 차지하는 구간의 색 번호와 길이를 출력한다. 서로 맞닿아 있는 같은 색 구간은 하나의 구간으로 합쳐서 출력한다. 각 줄에 색 번호와 길이를 공백 하나로 구분하여 출력한다.

힌트

예제5

예제 1

입력

예상 출력

예제 2
입력
```
10 0
```
예상 출력
```
0 10
```
예제 3
입력
```
10 1
4 3 7
```
예상 출력
```
0 3
4 4
0 3
```
예제 4
입력
```
10 2
1 0 6
2 4 10
```
예상 출력
```
1 4
2 6
```

예제 5

입력

예상 출력