You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小明的班上有$n$个小朋友，一开始第$i$个小朋友坐在第$i$个位置上。

现在经历了$m$轮换位置，第$i$轮，坐在第$x_i$个位置上的小朋友，跟坐在第$y_i$个位置上的小朋友交换了位置。

显然，模拟这个过程谁都会的，所以小明的问题比这个难一点：

一共有$Q$组询问，第$i$组询问是这样的：

t u v id：表示的是，假设$x_t=u,y_t=v$，其余不变，那么执行完$m$轮换位置后，$id$小朋友现在坐在哪个位置上。

注意，每次询问对后续是无影响的。

输入格式

由于数据量太大了，所以数据按照如下格式输入，含义如上所示：

int randseed,n,m,Q;
int x[maxn],y[maxn],t[maxn],u[maxn],v[maxn],id[maxn];
unsigned int rnd()
{
  unsigned int r;
  r = randseed = randseed * 1103515245 + 12345;
  return (r << 16) | ((r >> 16) & 0xFFFF);
}
void init()
{
	cin>>n>>m>>Q>>randseed;
	for (int i=1;i<=m;i++) {x[i]=rnd()%n+1; y[i]=rnd()%n+1;}
	for (int i=1;i<=Q;i++) {t[i]=rnd()%m+1; u[i]=rnd()%n+1; v[i]=rnd()%n+1; id[i]=rnd()%n+1;}
}

输出格式

输出$\sum_{i=1}^Q i\times ans[i]$模$998244353$的结果。

5 5 5 114

50

样例解释 #1

实际上输入的数据是：$n=5,m=5,Q=5$。

原先的五次操作分别是：

2 3
5 4
1 5
5 4
2 2

对应的$Q$次查询分别是：

1 3 1 5
1 1 3 5
4 3 2 3
4 1 5 5
5 2 3 2

每次的答案分别是：5 5 3 4 2。

114 514 1919 810

104434340

数据范围

对于30%的数据：$n,m,Q\leq 1000$。

对于50%的数据：$n,m,Q\leq 2\times 10^5$。

对于80%的数据：$n,m,Q\leq 10^6$。

对于100%的数据：$n,m,Q\leq 2\times 10^6$。