直接按照欧拉函数的计算方式来即可

φ=区间积*区间出现（质数-1）的积/区间出现过的质数的积

区间积是满足类似区间减法的操作的（利用逆元）

由于强制在线，上主席树就可以了（维护每个质数上次出现的位置pre，求区间[l,r]，pre<l的元素即可）

1 const mo=1000777;  2 type node=record  3        po,next,num:longint;  4      end;  5      link=record  6        l,r:longint;  7        s1,s2:int64;  8      end;  9  10 var ni:array[0..mo] of int64; 11     s,sd:array[0..50010] of int64; 12     tree:array[0..50010*20*10] of link; 13     p,v,last:array[0..1000010] of longint; 14     e:array[0..500010] of node; 15     h,a,q:array[0..50010] of longint; 16     j,t,n,m,len,i,x,y,ans:longint; 17     wh:int64; 18  19 function build(l,r:longint):longint; 20   var m,q:longint; 21   begin 22     inc(t); 23     tree[t].s1:=1; 24     tree[t].s2:=1; 25     q:=t; 26     if l<>r then 27     begin 28       m:=(l+r) shr 1; 29       tree[q].l:=build(l,m); 30       tree[q].r:=build(m+1,r); 31     end; 32     exit(q); 33   end; 34  35 function add(l,r,last,x,y:longint):longint; 36   var m,q:longint; 37   begin 38     inc(t); 39     q:=t; 40     if l=r then 41     begin 42       tree[q].s1:=tree[last].s1*int64(y-1) mod mo; 43       tree[q].s2:=tree[last].s2*ni[y] mod mo; 44     end 45     else begin 46       m:=(l+r) shr 1; 47       if x<=m then 48       begin 49         tree[q].r:=tree[last].r; 50         tree[q].l:=add(l,m,tree[last].l,x,y); 51       end 52       else begin 53         tree[q].l:=tree[last].l; 54         tree[q].r:=add(m+1,r,tree[last].r,x,y); 55       end; 56       tree[q].s1:=tree[tree[q].l].s1*tree[tree[q].r].s1 mod mo; 57       tree[q].s2:=tree[tree[q].l].s2*tree[tree[q].r].s2 mod mo; 58     end; 59     exit(q); 60   end; 61  62 function get(a,b:link):int64; 63   var p1,p2:int64; 64   begin 65     p1:=b.s1*ni[a.s1] mod mo; 66     p2:=b.s2*ni[a.s2] mod mo; 67     exit(p1*p2 mod mo); 68   end; 69  70 function ask(l,r,x,y,z:longint):longint; 71   var m:longint; 72       p,q:int64; 73   begin 74     if z>=r then exit(get(tree[x],tree[y])) 75     else begin 76       m:=(l+r) shr 1; 77       if z<=m then exit(ask(l,m,tree[x].l,tree[y].l,z)) 78       else begin 79         p:=get(tree[tree[x].l],tree[tree[y].l]); 80         q:=ask(m+1,r,tree[x].r,tree[y].r,z); 81         exit(p*q mod mo); 82       end; 83     end; 84   end; 85  86 begin 87   for i:=2 to 1000000 do 88   begin 89     if v[i]=0 then 90     begin 91       inc(t); 92       p[t]:=i; 93       v[i]:=i; 94     end; 95     for j:=1 to t do 96     begin 97       if i*p[j]>1000000 then break; 98       v[i*p[j]]:=p[j]; 99       if i mod p[j]=0 then break;100     end;101   end;102   ni[1]:=1;103   for i:=2 to mo-1 do104   begin105     ni[i]:=-int64(mo div i)*ni[mo mod i] mod mo;106     if ni[i]<0 then ni[i]:=(ni[i]+mo) mod mo;107   end;108   readln(n,m);109   s[0]:=1;110   sd[0]:=1;111   for i:=1 to n do112   begin113     read(a[i]);114     s[i]:=s[i-1]*int64(a[i]) mod mo;115     sd[i]:=sd[i-1]*int64(ni[a[i]]) mod mo;116     x:=a[i];117     while x<>1 do118     begin119       inc(len);120       y:=v[x];121       e[len].po:=y;122       e[len].num:=last[y];123       e[len].next:=q[i];124       q[i]:=len;125       last[y]:=i;126       while x mod y=0 do x:=x div y;127     end;128   end;129   t:=0;130   tree[0].s1:=1;131   tree[0].s2:=1;132   h[0]:=build(0,n);133   for i:=1 to n do134   begin135     h[i]:=h[i-1];136     j:=q[i];137     while j<>0 do138     begin139       y:=e[j].po;140       h[i]:=add(0,n,h[i],e[j].num,y);141       j:=e[j].next;142     end;143   end;144   for i:=1 to m do145   begin146     readln(x,y);147     x:=x xor ans;148     y:=y xor ans;149     if x>y then150     begin151       t:=x; x:=y; y:=t;152     end;153     wh:=ask(0,n,h[x-1],h[y],x-1);154     ans:=wh*s[y] mod mo*sd[x-1] mod mo;155     if ans<0 then ans:=(ans+mo) mod mo;156     writeln(ans);157   end;158 end.