Հարցումներ հաջորդականության վրա

Տրված է n տարր պարունակող a հաջորդականությունը և S դատարկ բազմությունը։ Պետք է հաջորդականության և բազմության վրա իրականացնել հետևյալ տեսքի q հարցումներ․

1. S֊ին ավելացնել ind ինդեքսը

2. S֊ից հեռացնել ind ինդեքսը

3. S֊ում գտնվող բոլոր i ինդեքսների համար $a_i$֊ին ավելացնել x թիվը

4. արտածել $a_i$ թիվը

Մուտքային տվյալներ

Առաջին տողում տրված է բնական թիվ n֊ը $(1 ≤ n ≤ 10^5)$։ Հաջորդ տողում տրված են բացատով անջատված n բնական թվեր՝ $a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9)$։ Հաջորդ տողում տրված է q բնական թիվը $(1 ≤ q ≤ 10^5)$։ Հաջորդ q տողերում տրված են հարցումները։ Հարցումները տրված են հետևյալ տեսքով․ 1 ind առաջին տեսքի հարցման համար (1 ≤ ind ≤ n), 2 ind երկրորդ տեսքի հարցման համար $(1 ≤ ind ≤ n)$, 3 x երրորդ տեսքի հարցման համար $(1 ≤ x ≤ 10^9)$ և 4 ind չորրորդ տեսքի հարցման համար $(1 ≤ ind ≤ n)$։ Երաշխավորվում է, որ 1 տիպի հարցման դեպքում ind֊ը S֊ում բացակա է, իսկ 2 տեսքի հարցման դեպքում S֊ը պարունակում է ind֊ը։

Ելքային տվյալներ

Պետք է արտածել 1֊ական տող ամեն չորրորդ տեսքի հարցման համար ըստ հարցման հերթականության։4 ind հարցման պատասխանը պետք է լինի մինչ այդ կատարված հարցումների արդյունքում ստացվող $a_{ind}$֊ի արժեքը։

Օրինակ

Բացատրություն

Ամենասկբում հաջորդականությունը [1, 2, 3, 4, 5] ֊ն է, իսկ S բազմությունը դատարկ է։

1. Առաջին հարցումից հետո Sբազմությունը կդառնա {2}

2. Երկրորդ հարցումից հետո Sբազմությունը կդառնա {2, 4}

3. Երրորդ հարցումից հետո a հաջորդականությունը կդառնա [1, 12, 3, 14, 5]

4. Չորրորդ հարցումից հետո Sբազմությունը կդառնա {2}

5. Հինգերորդ հարցումից հետո a հաջորդականությունը կդառնա [1, 14, 3, 14, 5]

6. Վեցերորդ հարցումից հետո Sբազմությունը կդառնա դատարկ

7. Յոթերորդ հարցումից a հաջորդականությունը չի փոխվի, քանի որ S բազմությունը դատարկ է։

Հաջորդ հարցումները պարզապես արտածում են նշված ինդքսում գրված տարրերը առանձին տողերի վրա։

Ենթախնդիրներ

• Ենթախնդիր 0 (0 միավոր) Օրինակները,

• Ենթախնդիր 1 (17 միավոր) 1 տեսքի հարցումներն ավելի շուտ են հանդիպում, քան 2 տեսքի հարցումները, որոնք ավելի շուտ են հանդիպում, քան 3 տեսքի հարցումները, որոնք ավելի շուտ են հանդիպում քան 4 տեսքի հարցումները։

• Ենթախնդիր 2 (23 միավոր) $n, q ≤ 10000$,

• Ենթախնդիր 3 (60 միավոր) $n, q ≤ 100000$: