{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\r\n\u003ctable class\u003d\"problems\" width\u003d\"100%\"\u003e\u003ctbody\u003e\u003ctr class\u003d\"navigation\"\u003e\r\n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/NKMOU/en/\"\u003eEnglish\u003c/a\u003e\u003c/td\u003e \r\n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/NKMOU/vn/\"\u003eVietnamese\u003c/a\u003e\u003c/td\u003e \r\n\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\r\n\r\n\u003cp\u003eThe Mountain Amusement Park has opened a brand-new simulated roller coaster. The simulated track consists of n \r\n\r\nrails\r\nattached end-to-end with the beginning of the first rail fixed at elevation 0. Byteman, the operator, can reconfigure the\r\ntrack at will by adjusting the elevation change over a number of consecutive rails. The elevation change over other rails is\r\nnot affected. Each time rails are adjusted, the following track is raised or lowered as necessary to connect the track while\r\nmaintaining the start at elevation 0. The figure below illustrates two example track reconfigurations.\u003c/p\u003e\r\n\u003cp\u003eEach ride is initiated by launching the car with sufficient energy to reach height h. That is, the car will continue to\r\ntravel as long as the elevation of the track does not exceed h, and as long as the end of the track is not reached.\u003c/p\u003e\r\n\u003cp\u003eGiven the record for all the day’s rides and track configuration changes, compute for each ride the number of rails\r\ntraversed by the car before it stops.\u003c/p\u003e\r\n\u003cp\u003eInternally, the simulator represents the track as a sequence of n elevation changes, one for each rail. The i-th number\r\nd\u003csub\u003ei\u003c/sub\u003e represents the elevation change (in centimetres) over the i-th rail. Suppose that after traversing i−1 rails the \r\n\r\ncar has\r\nreached an elevation of h centimetres. After traversing i rails the car will have reached an elevation of h+d\u003csub\u003ei\u003c/sub\u003e \r\n\r\ncentimetres.\u003c/p\u003e\r\n\u003cp\u003eInitially the rails are horizontal; that is, d\u003csub\u003ei\u003c/sub\u003e \u003d 0 for all i. Rides and reconfigurations are interleaved \r\n\r\nthroughout the day.\r\nEach reconfiguration is specified by three numbers: a, b and D. The segment to be adjusted consists of rails a through b\r\n(inclusive). The elevation change over each rail in the segment is set to D. That is, d\u003csub\u003ei\u003c/sub\u003e \u003d D for all a ≤ i ≤ b.\u003c/p\u003e\r\n\u003cp\u003eEach ride is specified by one number h — the maximum height that the car can reach.\r\n\r\n\u003c/p\u003e\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of input contains one positive integer n — the number of rails, 1 ≤ n ≤ 1 000 000 000 . The following lines\r\ncontain reconfigurations interleaved with rides, followed by an end marker. Each line contains one of:\u003c/p\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003eReconfiguration — a single letter ‘I’, and integers a, b and D, all separated by single spaces (1 ≤ a ≤ b ≤ n,\r\n−1 000 000 000 ≤ D ≤ 1 000 000 000 ).\u003c/li\u003e\r\n\u003cli\u003eRide — a single letter ‘Q’, and an integer h (0 ≤ h ≤ 1 000 000 000) separated by a single space;\u003c/li\u003e\r\n\u003cli\u003eA single letter ‘E’ — the end marker, indicating the end of the input data.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eYou may assume that at any moment the elevation of any point in the track is in the interval [0 ,1 000 000 000] \r\n\r\ncentimetres.\u003c/p\u003e\r\n\u003cp\u003eThe input contains no more than 100 000 lines.\u003c/p\u003e\r\n\u003cp\u003eIn 50% of test cases n satisfies 1 ≤ n ≤ 20 000 and there are no more than 1 000 lines of input.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eThe i-th line of output should consist of one integer — the number of rails traversed by the car during the i-th ride.\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e4\r\nQ 1\r\nI 1 4 2\r\nQ 3\r\nQ 1\r\nI 2 2 -1\r\nQ 3\r\nE\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n1\r\n0\r\n3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\u003cp\u003e\r\n\u003cimg src\u003d\"CDN_BASE_URL/1e44f06c36e9558dc00cc6765ebd6679?v\u003d1725308980\" width\u003d\"470\" height\u003d\"535\"\u003e\r\n\u003c/p\u003e\r\n\u003cp\u003eViews of the track before and after each reconfiguration. The x axis denotes the rail number. The y axis and the \r\n\r\nnumbers\r\nover points denote elevation. The numbers over segments denote elevation changes.\r\n\u003c/p\u003e\r\n\r\n\n\u003c/div\u003e"}}]}