Description

给定一个长度为$n$的序列$a$，和一个$m$，每次执行以下两种操作：

1.
for(int i=1;i<=n;i++)b[i]=a[i];
for(int i=1;i<=m;i++)a[i]+=b[n-m+i];
2.
for(int i=1;i<=n;i++)b[i]=a[i];
for(int i=1;i<=m;i++)a[n-m+i]=b[i];

（pscal语言选手相信看懂没有太大困难？就将就一下吧TAT……不懂的可以咨询出题人哦！）
现在您要维护上述操作，还要随时回答对**某个区间的数的和模$2^32$的值**的询问。
由于本题数据规模较大，为了省去时间，我们有特殊的数据生成方式。
首先我们需要一个随机函数：

const unsigned int Mod=998244353
long long seed;
unsigned int Rand(){
	seed*=3;
	while(seed>=Mod)seed-=Mod;
	return seed;
}

其中正整数$seed$在输入时给定（在$int$范围内），下面的图也有说明。

$a$的声明方式如下：

cin>>seed;
cin>>n>>m;
for(int i=1;i<=n;i++)a[i]=Rand;

而操作序列的生成方式如下。

cin>>q;
for(int i=1;i<=q;i++)
{
	bool ty=Rand%2;
	if(ty==0)
	{
	int l=Rand()%n+1,r=Rand()%n+1;
	if(l>r)swap(l,r);
	//Query on interval[l,r]
	}
	else 
	{
		ty=Rand%2;
		if(ty==1)//Modify 1
		else //Modify 2
	}
}

另外，为了省去输出时间，本题只要求输出所有询问的答案的和。

Input

按照题意中描述的方法输入即可，也可参考样例。

Output

一个数，所有询问的答案的和。

Samples

3
10 2
10

315918

Limitation

注意：样例解释见数据范围中1.4.3 explanation