Dinamik massiv

Dinamik bir massiv təşkil edən məlumat strukturu yaratmalısınız ki, aşağıdakı əməliyyatları dəstəkləsin:

1. u mövqeyindəki ədədə p dəyərini təyin etmək.

2. u mövqeyindən sonra (əgər varsa, u+1 mövqeyindən əvvəl) p ədədini əlavə etmək.

3. u ilə v mövqeləri arasında (hər iki mövqe daxil olmaqla) p dəyərindən böyük olmayan neçə ədədin olduğunu hesablamaq.

Massivin elementləri 1-dən başlayaraq nömrələnir.

Giriş verilənləri

Birinci sətirdə iki natural ədəd n və m verilir - massivdəki başlanğıc elementlərin sayı və əməliyyatların sayı (1 ≤ n ≤ 200000, 1 ≤ m ≤ 200000). İkinci sətirdə n tam ədədlər a_1, a_2, ..., a_n - başlanğıc massiv elementləri (0 ≤ a_i ≤ 10^6) verilir. Növbəti m sətir əməliyyatların təsvirini aşağıdakı formatda ehtiva edir:

1 u p (u ≥ 1, u cari massiv ölçüsünü keçmir, 0 ≤ p ≤ 10^6),

2 u p (u ≥ 0, u cari massiv ölçüsünü keçmir, 0 ≤ p ≤ 10^6)

və ya

3 u v p (1 ≤ u ≤ v, v cari massiv ölçüsünü keçmir, 0 ≤ p ≤ 10^6).

Çıxış verilənləri

Çıxış faylında sorğuların cavabları hər biri bir sətirdə olmaqla verilməlidir.

Nümunələr