SuperNim Junior#2878
Nim, iki oyuncu üçün nəzərdə tutulmuş bir oyundur; oyuncular növbə ilə bir neçə yığın (pilə) üzərində yerləşdirilmiş əşyaları götürürlər. Hər gedişdə oyunçu boş olmayan bir yığını seçir və oradan istənilən qeyri-sıfır sayda əşya götürür. Öz növbəsində hərəkət edə bilməyən (yəni, sonuncu əşyanı rəqibi alan) oyunçu uduzur.
Bu oyun tam şəkildə riyazi olaraq analiz edilib. Uduzan vəziyyətlər elə vəziyyətlərdir ki, həmin vəziyyətdə hər hansı bir gediş edən oyunçunun seçiminə rəqibi həmişə elə cavab verə bilər ki, sonda özü udacaq (yəni, rəqibin uduş strategiyası var). Udan vəziyyətlər isə elə vəziyyətlərdir ki, fərq etməz rəqib necə oynayır, gediş edən oyunçu həmişə elə cavab verə bilər ki, sonda özü udacaq (yəni, oyunçunun uduş strategiyası var).
Məlumdur ki, vəziyyətin uduş olub-olmaması nim-cəmi ilə təyin olunur:
burada p_i -ci yığındakı əşyaların sayıdır, isə ikilik məntiqi "yexklusiv və ya" əməliyyatını (yəni, rəqəmlərin ikilikdə üst-üstə toplanmasını daşımısız) bildirir. Əgər nim-cəm sıfır deyilsə, vəziyyət uduş vəziyyətidir; əgər sıfırdırsa, uduzan vəziyyətdir.
Bu məsələdə sizə çoxlu sayda yığın verilir. Tapşırıq: yığınların ölçüləri verildikdə, ilkin mövqedən birinci oyunçunun elə birinci gedişi etmə yollarının sayını müəyyən edin ki, bu gedişdən sonra birinci oyunçunun hələ də uduş strategiyası qalsın (yəni, gedişdən sonra birinci oyunçu uduş vəziyyətində olsun).
Birinci sətirdə — yığın qruplarının sayı verilir. Növbəti sətirin hər birində iki tam ədəd və təqdim edilir. Hər bir qrup -dan -yə qədər (hər ikisi daxil olmaqla) ölçülərə malik b-a+1 yığından ibarətdir.
1 \leq M \leq 100000, 0 \leq a \leq b \leq 10^{12}.
Bir tam ədəd çap edin — birinci oyunçuya uduş strategiyası saxlayan birinci gedişi icra etmə yollarının sayını.
Nümunə 1