На најдолгата авенија на Њујорк зградите се поредени една до друга, и имаат различни висини (број на спратови). Нека тоа се N згради, означени со броевите од 1 до N.

Заради брзиот развој на градот, многу често зградите се доградуваат со нови спратови. Процесот на доградба е раководен од градскиот архитект и тој одлучува во даден момент да ја зголеми висината на неколку соседни згради. Нека тој настан го означиме како настан од тип 1. Во настанот архитектот дава 3 броеви L, R и V. Сите згради од L до R (вклучувајќи ги L и R) се зголемуваат за висина V.

Спајдермен се движи скокајќи од зграда на зграда. Но, тој не е семоќен. Ако Спајдермен го почне своето патување од зграда со висина Х, тој може да скока само на згради со „слична“ висина, односно, може да скокне на згради со височина меѓу X-K и X+K, вклучително, за некое дадено K.

Како настан од тип 2 ќе го означиме скокањето на Спајдермен од некоја зграда на позиција Р на зградите во лево, се' дури може да скока според дадените правила. Значи, знаејќи ги висините на сите згради, за дадена позиција Р на зградата од која почнува да скока Спајдермен, и разликата во висини K, сакаме да знаеме до која најдалечна зграда тој може да доскока ако тргне во лево.

За дадена почетна низа со висините на N згради, и дефинирани Q настани - секој од еден од горните типови, ваша задача е да дадете одговор на прашањето поврзано со настанот од тип 2.

Влез

Првиот ред содржи два цели броеви N (1 ≤ N ≤ 500000) и Q (1 ≤ Q ≤ 500000).
Вториот ред содржи N цели броеви а₁, а₂, ..., а_N (1 ≤ а_i ≤ 1 000 000 000) – почетните висини на зградите.
Секој од наредните Q редови ќе започнува со еден цел број T (1 ≤ T ≤ 2) – се случува настан од тип T.
Ако T = 1, во истиот ред следуваат три цели броеви L, R (1 ≤ L ≤ R ≤ N) и V ( 1 ≤ V ≤ 1 000 000 000) – потребните броеви за настанот 1.
Ако Т = 2, во истиот ред следуваат два цели броеви K (0 ≤ K ≤ 10¹⁵) и P (1 ≤ P ≤ N) – потребните броеви за настанот 2.

Забелешка.
За 13 поени: N ≤ 1000 и Q ≤ 1000.
За следни 39 поени: N,Q ≤ 100 000.
За следни 39 поени: N ≤ 500 000, Q ≤ 200 000.

За забрзување на читањето податоци се препорачува да се користат следниве линии на почетокот од main функцијата во вашата програма:
ios_base::sync_with_stdio(false);
cin.tie(0);
Исто така се препорачува да не се користи endl за печатење на нова линија, туку да се користи “\n”.

Излез

За секој настан од тип 2 (Т = 2) отпечатете ја позицијата на зградата каде што ќе доскока (и застане) Спајдермен.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
5 5
5 1 5 10 9
2 13 5
1 2 3 20
2 13 5
1 4 5 10
2 3 4

излез
1
4
4

влез
4 7
5 2 2 8
2 4 4
2 10 4
1 1 3 10
1 2 4 9
2 4 4
1 4 4 8 
2 4 4

излез
4
1
1
2

влез
4 10
3 4 8 6
1 4 4 6
2 8 4
1 4 4 9
2 8 2
1 1 4 8
1 3 4 5
1 2 2 3
1 3 3 6
2 7 3
2 3 1

излез
2
1
3
1

Објаснување 1:
Во првиот настан од тип 2, висините на зградите е [5, 1, 5, 10, 9], Спајдермен се наоѓа на зграда на позиција 5, неговиот интервал на скокање е [-4, 22], што значи дека Спајдермен може да скокне до сите згради, најдалечната зграда до која што тој може да доскока лево е на позиција 1.
Потоа следи настан од тип 1, во кој висините на зградите 2 и 3 се зголемуваат за по 20.
Потоа, во вториот настан од тип 2, висините на зградите се [5, 21, 25, 10, 9], Спајдермен се наоѓа на зграда на позиција 5, неговиот интервал на скокање е [-4, 22], што значи дека Спајдермен не може да скокне на зградата на позиција 3, па најдалечната зграда на која што тој може да скокне во лево е на позиција 4.
Во третиот настан од тип 2, висините на зградите се [5, 21, 25, 20, 19], Спајдермен се наоѓа на позиција 4, неговиот интервал на скокање е [17, 23], што значи дека тој не може да скокне ни на зградата на позиција 3, односно си останува на својата позиција (позиција 4).

Објаснување 2:
Во првиот настан од тип 2, висините на зградите се [5, 2, 2, 8], Спајдермен се наоѓа на зграда на позиција 4, неговиот интервал на скокање е [4, 12], што значи дека тој не може да скокне на ниту една зграда на лево.
Во вториот настан од тип 2, висините на зградите се [5, 2, 2, 8], Спајдермен се наоѓа на зграда на позиција 4, и неговиот интервал на скокање е [-2, 18], можеме да видиме дека сите згради се во интервалот на скокање, што значи дека Спајдермен ќе застане на најдалечната зграда движејќи се кон лево, тоа е зградата на позиција 1.
Во третиот настан од тип 2, висините на зградите се [15, 21, 21, 17], Спајдермен се наоѓа на зградата на позиција 4, и неговиот интервал на скокање е [13, 21]. Можеме да видиме дека висините на сите згради влегуваат во неговиот интервал на скокање, што значи дека тој ќе стигне до зградата на позиција 1 (најоддалечената зграда во лево).
Во четвртиот настан од тип 2, висините на зградите се [15, 21, 21, 25], Спајдермен се наоѓа на зградата на позиција 4, со интервал на скокање [21, 29], можеме да видиме дека тој ќе застане на зградата на позиција 2 бидејќи висината на зградата на позиција 1 не влегува во неговиот интервал на скокање.