SPOJ in Armenian

Շարադրանք

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

1. S֊ին ավելացնել ind ինդեքսը
2. S֊ից հեռացնել ind ինդեքսը
3. S֊ում գտնվող բոլոր i ինդեքսների համար ai֊ին ավելացնել x թիվը
4. արտածել ai թիվը

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

Առաջին տողում տրված է բնական թիվ n֊ը (1 ≤ n ≤ 105)։ Հաջորդ տողում տրված են բացատով անջատված n բնական թվեր՝ a1, a2, ..., an (1 ≤ ai ≤ 109)։ Հաջորդ տողում տրված է q բնական թիվը (1 ≤ q ≤ 105)։ Հաջորդ q տողերում տրված են հարցումները։ Հարցումները տրված են հետևյալ տեսքով․ 1 ind առաջին տեսքի հարցման համար (1 ≤ ind ≤ n), 2 ind երկրորդ տեսքի հարցման համար (1 ≤ ind ≤ n), 3 x երրորդ տեսքի հարցման համար (1 ≤ x ≤ 109) և 4 ind չորրորդ տեսքի հարցման համար (1 ≤ ind ≤ n)։ Երաշխավորվում է, որ 1 տիպի հարցման դեպքում ind֊ը S֊ում բացակա է, իսկ 2 տեսքի հարցման դեպքում S֊ը պարունակում է ind֊ը։

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

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

Օրինակ

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

Ամենասկբում հաջորդականությունը [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 բազմությունը դատարկ է։

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