见过O(N)的st表吗？

【题意】
一个长度为n的a序列
给定m次询问
每次询问区间[l,r]的最大值
但是为了减少IO量
我们用seed来制造数据
一开始读入n，m，seed
然后调用下面的模版来进行每次读入

int seed;
int read()
{
	seed^=seed<<5;
	seed^=seed>>2;
	seed^=seed<<7;
	return (seed%100000000+100000000)%100000000;
}

先调用n次read()读入a序列，即

for(int i=1;i<=n;i++)a[i]=read();

然后读入m次询问，每次调用两次read()读入l和r，表示每次询问的区间
读入的l和r都要对n取模，然后加1
如果l>r就交换l和r
程序结束前，你要把对应的所有的答案异或起来输出（一个数）

【输入格式】
只有一行三个整数n，m，seed

【输出格式】
输出所有答案的异或和

【输入样例】
10 10 1989

【输出样例】
29280708

【提示】
1<=n,m<=10000000
0<=a[i]<=100000000