Դավիթը շատ էր սիրում հատվածներ, և մի պայծառ օր նա մտածեց, թե ինչու չի կարելի ուղղակի 3 հատված իրար կպցնել։ Հենց այդպես էլ առաջացավ եռահատվածի գաղափարը։
Այլ կերպ ասած, եռահատվածը ([a,b], [b,c], [c,d]) հատվածների եռյակ է։
Դավիթին շատ դուր եկավ եռահատվածների գաղափարը ու նա որոշեց տանը n եռահատված աճեցնել։ Ոստիկանությունը, իմանալով դրա մասին, հաջորդ օրը թակեց իրենց տան դուռը ու սկսեց հարցեր տալ Դավիթին: Ոստիկանության բոլոր հարցերը կարելի է նկարագրել երկու l, r թվերով, որոնց համար Դավիթը պետք է ասի այն եռահատվածների քանակը, որոնց գոնե մի հատվածը ամբողջովին ընկած է [l,r] միջակայքում։
Դավիթը ամբողջ օրը անցկացրել էր եռահատվածներ մշակելով ու փորձարկելով և, հոգնածության պատճառով, ձեզ է խնդրում պատասխանել տրված հարցերին։
Մուտքային տվյալներ
Մուտքի առաջին տողում տրված են 1 ≤ n,q ≤ բնական թվերը։ Հաջորդ n տողերում տրված են, հերթական եռահատվածի համար բնական թվերը:Հաջորդ q տողերերից iրդը պարունակում է թվերը: Նշանակենք ansը նախորդ հարցի պատասխանը (առաջին հարցի համար ans=0), դուք պետք է հերթական հարցի համար վերցնեք թվերը, որտեղ ⊕-ը «բիթային բացառող կամ»* գործողությունն է: ()
Առաջին հարցում l=5 և r=10։ Քանի որ առաջին եռահատվածի երրորդ և երկրորդ եռահատվածի առաջին հատվածները ամբողջովին ընկած են այդ հատվածի մեջ, հարցի պատասխանը 2 է։
Երկրորդ հարցում l=1 և r=8։ Քանի որ առաջին եռահատվածի առաջին հատվածը, և երկրորդ եռահատվածի առաջին հատվածը ամբողջովին ընկած են այդ հատվածի մեջ, հարցի պատասխանը նույնպես 2 է։
Երրորդ հարցում l=5 և r=8։ Քանի որ միայն երկրորդ եռահատվածը ունի հատված ամբողջովին ընկած այդ միջակայքում, պատասխանը 1 է։
Չորորդ հարցում l=1 և r=12։ Բոլոր երեք եռահատվածները ունեն գոնե մի հատված ընկած այդ հատվածում։
Առաջին հարցումում l=6 և r=7։ Ոչ մի եռահատված չունի հատված ամբողջովին ընկած այդ հատվածում։
*c++ լեզվում «բիթային բացառող կամ» գործողությունը կարող եք կատարել ^ օպերատորով։