시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
4.0 초 32 MB 2 1 (50%) 1
문제
작은나라에 신마을이 생겨났다. 평소처럼, 밀코는 최고 세금 책임자의 자리를 맡았다. 그의 임무는 마을에 있는 다른 회사들의 모두 적절한 회계를 보장하는 것이다. 메인스트리트에 N개의 비지니스 사무실이, 왼쪽에서 오른쪽으로 1에서 N번까지 번호가 붙어있다. 모든 사무실은 처음에는 비어있다; 어떤시간에, 회사가 이 사무실들중 하나로 옮겨온다. 매 시간마다, 밀코는 몇개의 사무실들을 지나며 단하나의 회사만 회계검사를 하게 되는데, 이 사무실들 내에 현재 가장 부유한 회사이다. 회사의 이동은 다음 네개의 정수로 표현된다: * T - 이동날짜, 마을이 생긴날로부터의 (생긴날은 1이다) * K - 사무실 번호 * Z - 매일 얻는 소득 (돈을 잃는 경우 음수가 될 수 있다.) * S - 이동날짜에 있는 회사 통장에 있는 잔액 만약 K번 사무실에 이미 다른 회사가 있다면, 그 회사는 다른곳으로 옮겨가게 되고 새 회사가 들어오게 된다. 새 회사는 옮겨오는 날짜까지 사업(또는 수익을 얻음)을 하지 않는다. 밀코의 회계검사 이동은 다음 세개의 정수로 표현된다: * T - 회계검사날, 마을이 생긴날로부터 * A와 B - 밀코가 A번 사무실과 B번사무실 사이를 지나가게 된다. 밀코는 그 날이 끝나기 직전에만 일하기 때문에, 밀코가 이동하는 시점에는 이미 모든 회사가 업무를 마치고 그 날의 수익을 얻은 이후이다. 밀코를 도와 각 이동마다 그 사이에 있는 사무실에 들어온 회사들 중 가장 부유한 회사가 무엇인지 찾는 프로그램을 작성하여라.
입력
첫번째 줄에는 두 양의 정수, N (1<=N<=100 000)과 M(1<=M<=300 000)이 주어지는데, 이는 사무실의 갯수와 사건의 갯수이다. 각 M개의 줄에 걸쳐서 하나의 사건이 주어지는데, 형식은 "1 T K Z S" (회사가 이동해옴) 또는 "2 T A B" (밀코가 회계검사)이다. 모든 사건은 발생한 순서대로 주어지며, 하루에는 최대 하나의 사건만 일어난다. (즉, T는 언제나 엄격하게 증가한다.) 마지막 사건 발생일은 106보다 작으며, 모든 Z와 S의 절대값은 106을 넘지 않는다.
출력
각 밀코의 회계검사에 대해 한줄에 밀코가 검사하는 회사의 계좌 잔고를 출력하거나, 또는 아무런 회사도없을 경우 "nema"(큰따옴표 없이)를 출력한다.
힌트
입력예제1 ``` 2 4 1 1 1 2 4 1 2 2 3 2 2 5 1 2 2 7 1 2 ``` 출력예제1 ``` 12 17 ``` 입력예제2 ``` 3 6 1 1 1 4 -2 1 2 2 2 6 2 3 3 1 2 4 3 1 1 5 3 -6 20 2 6 2 3 ``` 출력예제2 ``` 8 10 14 ``` 입력예제3 ``` 5 9 1 1 5 4 -5 2 2 3 5 1 3 4 6 9 2 4 1 2 1 6 2 2 3 2 8 2 1 1 9 4 0 17 2 10 5 5 2 11 1 4 ``` 출력예제3 ``` -1 nema 7 31 17 ```