Cyclist Race

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has been invited to be a judge for a cycling race.
You may think about cyclists in the race as points on a line. All the cyclists start at the same point with an initial speed of zero. All of them move in the same direction. Some cyclists may force their cycles to speed up. The change of speed takes place immediately. The rest of the time, they move with a constant speed. There are N cyclists in total, numbered from 1 to N.
In order to award points to the participants, Chef wants to know how far the cyclists have reached at certain points of time.
Corresponding to the above two, there will be two types of queries.
 Change the speed of cyclist i at some time.
 Ask for the position of the race leader at some time.
There are Q queries. Each query of first type is described by the type of the query (1), the time Time, the cyclist number cyclist, and the new speed NewSpeed. Each query of second type is described by the type of the query (2), and the time Time.
Initial speed of all the cyclists is 0.
Input
The first line of input contains two spaceseparated integers, N and Q.
Next Q lines contain queries, one per line. Each line constists of several spaceseparated integers. First integer is Type, it is either 1 or 2 denoting the type of the query. If the type of the query is 1, then three integers follow: Time, cyclist and NewSpeed. If the type of the query is 2, then one integer follows: Time. All the queries are sorted by time, e.g., value Time of the next query is greater or equeal than value Time for current query.
Output
Output integers A_{1}, A_{2}, … , A_{R} each in a separate line. Here A_{i} is the answer for the i^{th} query of type 2 in the current test case and R is the total number of queries of this type in the test case.
Constraints
 1 ≤ N ≤ 50000
 1 ≤ Q ≤ 10^{5}
 0 ≤ Time ≤ 10^{9}
 1 ≤ NewSpeed ≤ 10^{9}
 1 ≤ cyclist ≤ N
 The speed of any cyclist cannot decrease.
Subtasks
 Subtask #1 [25 points]: N ≤ 5000 and Q ≤ 10000
 Subtask #2 [75 points]: No additional constraints
Example
Input: 5 14 1 1 1 2 1 1 2 5 1 2 3 4 1 2 4 7 2 3 2 4 1 5 5 4 2 5 2 6 1 7 5 8 2 7 2 8 2 9 2 10 Output: 10 15 21 28 35 42 49 56
Author:  cenadar 
Tester:  antoniuk1 
Editorial  http://discuss.codechef.com/problems/CYCLRACE 
Tags  cenadar, convexhull, jan16, med 
Date Added:  19092015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions