시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 89 12 9 10.588%

문제

요즘 한국에는 스타트업 열풍이 불고 있다. 상근이는 스타트업에게 사무실을 빌려주는 스타트업을 시작했다. 사무실은 총 N개가 있다. 가장 왼쪽에 있는 사무실은 1번, 가장 오른쪽은 N번이며, 그 사이 사무실은 순서대로 번호가 매겨져 있다. 

처음에 사무실은 모두 비어있다. 사무실에 회사가 입주할 때, 회사는 상근이에게 다음과 같은 네 가지 정보를 알려주어야 한다.

  • T: 입주일 (상근이가 스타트업을 시작한 날이 1일이다)
  • K: 사무실 번호
  • Z: 하루 수익 (회사가 손해를 보고있다면 음수일 수도 있다)
  • S: 입주일 당시에 그 회사가 가지고 있는 금액

만약 입주하려고 하는 사무실 K에 이미 회사가 있다면, K에 있던 회사는 짐을 싸서 사무실을 비워야 한다. 또, 입주하는 날은 하루종일 이사를 해야 하기 때문에, 일을 하지 않아서 수익을 올리지 않는다.

놀랍게도 이 사무실에 입주한 회사는 매일 매일 Z만큼 수익을 올리며, 이 금액은 늘어나지도, 줄어들지도 않는다.

가끔 상근이는 가장 부유한 회사가 어디인지 알아본다. 항상 연속으로 붙어있는 사무실을 조사하며, 다음과 같이 나타낼 수 있다.

  • T: 조사하는 날 (상근이가 스타트업을 시작한 날이 1일)
  • A와 B: A번 사무실부터 B번까지 조사

상근이는 항상 입주한 회사의 모든 업무가 끝난 다음에 조사를 한다. (사무실에서 밤 8시가 넘었는데 일을 할 수 없다) 따라서, 각 회사가 하루에 버는 수익은 항상 입주할 때 보고한 금액이다.

이벤트의 정보가 주어졌을 때, 조사에 대한 답을 구하는 프로그램을 작성하시오. 회사가 입주하는 정보와 상근이가 조사하는 정보를 합쳐서 이벤트라고 한다.

입력

첫째 줄에 사무실의 개수 N과 이벤트의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)

다음 M개 줄에는 이벤트의 정보가 주어진다. 회사의 입주는 "1 T K Z S"와 같이 주어지며, 상근이의 조사는 "2 T A B"로 주어진다.

모든 이벤트는 일어난 순서대로 주어진며, 하루에 일어나는 이벤트는 최대 한 개 이다. 따라서, T가 항상 증가하는 순서로 주어진다. 마지막 이벤트가 일어난 날은 106보다 작으며, Z와 S의 절대값도 106보다 작다.

출력

상근이의 질문에 대한 답(주어진 구간에 포함 되는 가장 부유한 회사가 가지고 있는 금액)을 한 줄에 하나씩 출력한다. 만약, 그 구간에 있는 회사가 하나도 없다면, "nema"를 출력한다.

예제 입력

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

예제 출력

12
17

힌트

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #2 6번