두 칸 차량의 주차 기록

문제

한 주차장에는 일렬로 놓인 N개의 주차 칸이 있으며, 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 처음에는 모든 칸이 비어 있다. 주차장에는 한 칸을 사용하는 일반 차량과 연속한 두 칸을 사용하는 긴 차량이 들어온다. 관리 장치는 차량 번호 대신 차량이 주차를 시작한 칸을 이용하여 입차와 출차를 기록한다. 장치에 전달된 M개의 요청을 입력 순서대로 하나씩 처리한다. 입차 요청에는 시작 칸 s와 사용할 칸 수 k가 주어진다. k는 1 또는 2다. 이 요청은 s번부터 s+k-1번까지의 칸에 차량 한 대를 주차하려는 뜻이다. 해당 칸이 모두 비어 있으면 입차에 성공하고 그 칸들을 한 차량이 차지한다. 하나라도 이미 다른 차량이 차지하고 있으면 요청은 실패하며, 어떤 칸의 상태도 바뀌지 않는다. 일부 칸만 먼저 차지하거나 다른 빈칸을 찾아서 주차하는 일은 없다. 모든 입차 요청의 칸 범위는 주차장 안에 들어온다. 출차 요청에는 시작 칸 s가 주어진다. 현재 s번 칸에서 주차를 시작한 차량이 있으면 그 차량이 차지한 모든 칸을 비우고 출차에 성공한다. s번 칸이 비어 있거나, 다른 칸에서 시작한 긴 차량의 두 번째 칸이면 출차 요청은 실패한다. 실패한 출차 요청도 주차 상태를 바꾸지 않는다. 출차한 차량이 사용하던 시작 칸은 이후 입차 요청에서 다시 사용할 수 있다. 관리자는 잘못된 요청의 수와 주차 공간이 가장 많이 사용된 순간을 확인하려고 한다. 입차와 출차를 합쳐 실패한 요청의 총수를 구하고, 처음 상태와 각 요청을 처리한 직후의 상태 중에서 차량이 차지한 칸 수의 최댓값을 구한다. 긴 차량 한 대는 점유한 칸 수에 2를 더한다. 모든 요청이 실패하여 끝까지 비어 있다면 최대 점유 칸 수는 0이다.

입력

첫째 줄에 정수 N과 M이 공백으로 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ M ≤ 20,000이다.
다음 M개의 줄에 요청이 하나씩 주어진다.
입차 요청은 1 s k 형식이다. k는 1 또는 2이며, 1 ≤ s ≤ s+k-1 ≤ N이다.
출차 요청은 2 s 형식이다. 1 ≤ s ≤ N이다.
모든 입력 값은 정수다. 현재 상태에서 실패하는 요청도 입력될 수 있다.

출력

실패한 요청의 총수와 최대 점유 칸 수를 공백으로 구분하여 한 줄에 출력한다.

4 7
1 2 2
2 3
1 1 2
1 4 1
2 2
1 1 2
2 4

2 3

1 4
2 1
1 1 1
1 1 1
2 1

2 1

3 2
2 1
2 3

2 0

출처: Devin.KR 자체 제작