Միջակայքի XOR հարցումներ

Ձեզ տրված է n էլեմենտից բաղկացած զանգված և q հարցում: Հարցումները երկու տեսակ են.

1. Միջակայքի բացառող կամ (XOR) արժեքի հաշվում

2. Զանգվածի արժեքի փոփոխում որոշակի դիրքում

Ձեր խնդիրը հարցումները արդյունավետ կերպով մշակելն է:

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր n և q (1 ≤ n, q ≤ 100000), որոնք ներկայացնում են զանգվածի էլեմենտների քանակը և հարցումների քանակը:

Մուտքի երկրորդ տողում տրված են n ամբողջ թվեր (), որոնք հանդիսանում են զանգվածի նախնական արժեքները:

Հաջորդ q տողերից յուրաքանչյուրն ներկայացնում է մեկ հարցում.

1. Միջակայքի XOR հարցման համար: Տողը սկսվում է 1 թվով, որին հաջորդում են և (1 ≤ li ≤ ri ≤ n) թվերը, որոնք սահմանում են այն ինդեքսների միջակայքը [], որի համար անհրաժեշտ է հաշվել XOR արժեքը:

2. Զանգվածի նորացման հարցման համար: Տողը սկսվում է 2 թվով, որին հաջորդում են և (1 ≤ pi ≤ n, 0 ≤ xi < 2^{30}), որոնք սահմանում են դիրքում գտնվող էլեմենտը և նրա նոր արժեքը:

Ելք

Վերոհիշյալ XOR հարցումներից յուրաքանչյուրի համար անհրաժեշտ է տպել համապատասխան միջակայքի էլեմենտների XOR արժեքը առանձին տողում:

Օրինակներ