Դավիթը և եռահատվածները

Դավիթը շատ էր սիրում հատվածներ, և մի պայծառ օր նա մտածեց, թե ինչու չի կարելի ուղղակի 3 հատված իրար կպցնել։ Հենց այդպես էլ առաջացավ եռահատվածի գաղափարը։
Այլ կերպ ասած, եռահատվածը ([a,b], [b,c], [c,d]) հատվածների եռյակ է։
Դավիթին շատ դուր եկավ եռահատվածների գաղափարը ու նա որոշեց տանը n եռահատված աճեցնել։ Ոստիկանությունը, իմանալով դրա մասին, հաջորդ օրը թակեց իրենց տան դուռը ու սկսեց հարցեր տալ Դավիթին: Ոստիկանության բոլոր հարցերը կարելի է նկարագրել երկու l, r թվերով, որոնց համար Դավիթը պետք է ասի այն եռահատվածների քանակը, որոնց գոնե մի հատվածը ամբողջովին ընկած է [l,r] միջակայքում։
Դավիթը ամբողջ օրը անցկացրել էր եռահատվածներ մշակելով ու փորձարկելով և, հոգնածության պատճառով, ձեզ է խնդրում պատասխանել տրված հարցերին։

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

Մուտքի առաջին տողում տրված են 1 ≤ n,q ≤ բնական թվերը։ Հաջորդ n տողերում տրված են, հերթական եռահատվածի համար բնական թվերը:Հաջորդ q տողերերից iրդը պարունակում է  թվերը: Նշանակենք ansը նախորդ հարցի պատասխանը (առաջին հարցի համար ans=0), դուք պետք է հերթական հարցի համար վերցնեք  թվերը, որտեղ ⊕-ը «բիթային բացառող կամ»* գործողությունն է: ()

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

Պետք է արտածել q թիվ՝ տրված հարցերի պատասխանները:

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

  • Ենթախնդիր 0 (0 միավոր) Օրինակները,
  • Ենթախնդիր 1 (13 միավոր) 1 ≤ n,q ≤ 5000
  • Ենթախնդիր 2 (11 միավոր) 
  • Ենթախնդիր 3 (14 միավոր)  և 
  • Ենթախնդիր 4 (21 միավոր) 
  • Ենթախնդիր 5 (41 միավոր) լրացուցիչ սահմանափակումներ չկան։

Օրինակ

Մուտք
Ելք
3 5 1 3 5 10 6 8 13 15 1 10 12 14 5 10 3 10 7 10 0 13 5 4
2 2 1 3 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++ լեզվում «բիթային բացառող կամ» գործողությունը կարող եք կատարել ^ օպերատորով։
 
Աղբյուրը՝ Հանրապետական 2022
 

Constraints

Time limit: 5.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue