Task: MOU          Country: BULGARIA
Mountains

Day 1. Source file  mou.*		                Saturday 20-08-2005 Available memory: 256 MB. Maximum running time:  3 s.

	В един увеселителен парк бил построен нов симулатор на стръмни пътища. Симулацията включва n отделни участъка, свързани последователно в краищата си. Началото на първия участък е на височина нула. Операторът Байтман може да променя пистата като задава нова стойност за наклона на няколко последователни участъка. Следващите участъци запазват наклона си, но могат да променят височината си, така че целият път остава непрекъснат. Началото винаги остава на височина нула. На фигурата са показани две последователни промени на пистата.
	По пистата се пуска кола, която може да се издига най-много на височина h. Движението продължава докато височината не надминава h или до края, ако навсякъде височината е по-малка или равна на h.
	По зададена последователност от промени на пистата,  за всяко пускане на колата пресметнете броя на участъците, които ще бъдат изминати.
	Вътрешното представяне на пистата в симулатора е редица от n числа d1, d2, …, dn, където di представлява промяната на височината (в сантиметри) по протежение на  i-тия участък. Да предположим, че след изминаване на  i – 1 участъка колата е достигнала височина k сантиметра. След изминаването на i-тия участък колата ще бъде на височина k + di сантиметра.
	Отначало пистата е хоризонтална, т.е. di  = 0 за всяко i. Промените на пистата и пусканията на колата следват в произволен ред. Всяка промяна на пистата се задава с три числа a, b, D, което означава, че  всички участъщи с номера от затворения интервал [a,b] ще имат един и същи наклон, равен на D, т.е. di  = D  за всяко i, a ≤ i ≤ b.
	При вяко пускане на кола се задава максималната височина h,  до която колата може да се издига. 

Задача   
Напишете програма която:
•	чете от стандартния вход последователност от данни за промени на пистата и пускания на колата;
•	за всяко пускане на колата намира броя на участъците, които колата ще измине; 
•	извежда резултата на стандартния изход.

Вход   
Първият ред на входа съдържа едно положително цяло число n – броя на участъците, 1≤ n ≤ 1 000 000 000. Всеки от следващите редове съдържат данни за промяна на пистата или за пускане на кола, последвани от маркер за край. За всеки от редовете е налице една от следните три възможности:
•	промяна на пистата – буквата ‘I’ и целите числа a, b и D, всичките разделени с точно по един интервал (1≤ a ≤ b ≤ n,  –1 000 000 000  ≤  D  ≤ 1 000 000 000);
•	пускане на кола – буквата ‘Q’ и цяло число h (0 ≤  h ≤  1 000 000 000), разделени с един интервал.
•	буквата ‘E’ – това е маркерът за край, показващ края на входните данни.

	Може да предполагате, че във всеки момент височината на всяка точка от пистата е в интервала [0, 1 000 000 000] сантиметра. 
	Входът съдържа не повече от 100 000 реда.
	В 50% от тестовите примери за n е изпълнено 1 ≤  n  ≤  20 000  и във входа има най-много 1000 реда. 	

Изход   
i-тият ред на изхода трябва да съдържа едно цяло число – броя на участъците, изминати от колата при i-тото пускане.
 
Пример   
За входните данни:	правилният резултат е:
4	4	
Q 1	1
I 1 4 2	0
Q 3	3
Q 1
I 2 2 –1
Q 3
E

Изгледи на пистата в начално състояние и след две промени. По оста x са нанесени номерата на участъците, а по оста y височината. Числата до точките са техните височини, а числата между точките са промените на височините.