{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/JAN16/mandarin/CYCLRACE.pdf\"\u003eMandarin Chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/JAN16/russian/CYCLRACE.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/JAN16/vietnamese/CYCLRACE.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\r\n\r\n\r\n\u003cp\u003eChef has been invited to be a judge for a cycling race.\u003c/p\u003e\r\n\u003cp\u003eYou 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 \u003cb\u003eN\u003c/b\u003e cyclists in total, numbered from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eN\u003c/b\u003e.\u003c/p\u003e\r\n\u003cp\u003eIn order to award points to the participants, Chef wants to know how far the cyclists have reached at certain points of time.\u003c/p\u003e\r\n\u003cp\u003eCorresponding to the above two, there will be two types of queries.\u003c/p\u003e\r\n\u003col\u003e\r\n\u003cli\u003eChange the speed of cyclist \u003cb\u003ei\u003c/b\u003e at some time.\u003c/li\u003e\r\n\u003cli\u003eAsk for the position of the race leader at some time.\u003c/li\u003e\r\n\u003c/ol\u003e\r\n\u003cp\u003eThere are \u003cb\u003eQ\u003c/b\u003e queries. Each query of first type is described by the type of the query (1), the time \u003cb\u003eTime\u003c/b\u003e, the cyclist number \u003cb\u003ecyclist\u003c/b\u003e, and the new speed \u003cb\u003eNewSpeed\u003c/b\u003e. Each query of second type is described by the type of the query (2), and the time \u003cb\u003eTime\u003c/b\u003e.\u003c/p\u003e\r\n\u003cp\u003eInitial speed of all the cyclists is 0.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of input contains two space-separated integers, \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eQ\u003c/b\u003e.\u003c/p\u003e\r\n\u003cp\u003eNext \u003cb\u003eQ\u003c/b\u003e lines contain queries, one per line. Each line constists of several space-separated integers. First integer is \u003cb\u003eType\u003c/b\u003e, it is either \u003cb\u003e1\u003c/b\u003e or \u003cb\u003e2\u003c/b\u003e denoting the type of the query. If the type of the query is \u003cb\u003e1\u003c/b\u003e, then three integers follow: \u003cb\u003eTime\u003c/b\u003e, \u003cb\u003ecyclist\u003c/b\u003e and \u003cb\u003eNewSpeed\u003c/b\u003e. If the type of the query is \u003cb\u003e2\u003c/b\u003e, then one integer follows: \u003cb\u003eTime\u003c/b\u003e. All the queries are sorted by time, e.g., value \u003cb\u003eTime\u003c/b\u003e of the next query is greater or equeal than value \u003cb\u003eTime\u003c/b\u003e for current query.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eOutput integers \u003cb\u003eA\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eA\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, … , \u003cb\u003eA\u003csub\u003eR\u003c/sub\u003e\u003c/b\u003e each in a separate line. Here \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e is the answer for the \u003cb\u003ei\u003c/b\u003e\u003csup\u003eth\u003c/sup\u003e query of type \u003cb\u003e2\u003c/b\u003e in the current test case and \u003cb\u003eR\u003c/b\u003e is the total number of queries of this type in the test case.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e50000\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eQ\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e0\u003c/b\u003e ≤ \u003cb\u003eTime\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eNewSpeed\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003ecyclist\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eThe speed of any cyclist cannot decrease.\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eSubtasks\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003eSubtask #1 [25 points]: N ≤ 5000 and Q ≤ 10000\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eSubtask #2 [75 points]: No additional constraints\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 14\r\n1 1 1 2\r\n1 1 2 5\r\n1 2 3 4\r\n1 2 4 7\r\n2 3\r\n2 4\r\n1 5 5 4\r\n2 5\r\n2 6\r\n1 7 5 8\r\n2 7\r\n2 8\r\n2 9\r\n2 10\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n15\r\n21\r\n28\r\n35\r\n42\r\n49\r\n56\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}