В Горном Парке Развлечений открылся новый аттракцион с американскими горками. Трек в аттракционе состоит из n рельсов, соединенных последовательно друг с другом, причем первый рельс начинается на высоте 0. Оператор Байтмэн может изменять конфигурацию трека по своему усмотрению, корректируя наклон некоторых последовательно соединенных рельсов. Наклон остальных рельсов при этом не изменяется. Всякий раз, когда наклон некоторых рельсов изменяется, все следующие за ними рельсы соответственно поднимаются или опускаются. При этом высота начала трека всегда остается равной 0.
На рисунках представлены изменения конфигурации трека в соответствии со входными данными, заданными в примере:
Каждый заезд начинается с того, что кабина запускается из начала трека с энергией, достаточной для достижения высоты h. Иными словами, кабина будет продолжать движение по рельсам, пока ее высота не превысит h или пока она не достигнет конца трека. Вычислите по записям о всех заездах и изменениях конфигураций трека число рельсов, которые были полностью пройдены кабиной в каждом из заездов до ее остановки.
В аттракционе трек описывается последовательностью из n наклонов, по одному для каждого рельса. i -е число d равно разнице высот (в сантиметрах) между концом i -го рельса и его началом. Иными словами, если после прохождения по первым i − 1 рельсам кабина оказывается на высоте h сантиметров, то после прохождения по i рельсам она будет на высоте h + d
i сантиметров. Изначально все рельсы горизонтальны, то есть d
i = 0 для всех i. Заезды и изменения конфигурации происходят в течение дня. Каждое изменение конфигурации описывается тремя числами: a, b
и D. Такое изменение затрагивает рельсы с a -го по b -й (включительно). Наклон каждого из этих рельсов устанавливается равным D. Иными словами, d
i = D для всех a <= i <= b. Каждый заезд задается одним числом h – максимальной высотой, на которую может подняться кабина.
Задание
Напишите программу, которая:
• читает из стандартного ввода последовательность описаний изменений конфигурации трека и заездов,
• для каждого заезда вычисляет количество рельсов, которые пройдены кабиной,
• выводит результаты в стандартный вывод.
Входные данные
Первая строка входных данных содержит одно положительное целое число n – количество рельсов в треке, 1 <= n
<= 1000000000 . Последующие строки содержат описания изменений конфигурации и заездов. Последняя строка входных данных содержит признак окончания. Каждая строка, начиная со второй, может содержать:
• Описание изменения конфигурации трека – один символ ‘I’ и целые числа a , b и D, разделенные одним пробелом (1 <= a <= b <= n , − 1000000000 <= D <= 1000000000).
• Описание заезда – один символ ‘Q’ и целое число h ( 0 <= h <= 1000000000 ), разделенные одним пробелом.
• Один символ “E” – признак окончания входных данных.
Вы можете предполагать, что в каждый момент высота любой точки трека содержится в промежутке [0 , 1000000000] . Входные данные содержат не более 100000 строк.
Выходные данные
i-я строка выходных данных должна содержать единственное целое число – количество рельсов, которые пройдены кабиной в i-м заезде.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
Q 1
I 1 4 2
Q 3
Q 1
I 2 2 -1
Q 3
E
|
4
1
0
3
|