alan的图
题号：NC219236
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小y给了alan一张  个  条边的连通图，并且这个图是一个二分图
其中的图上的每个点都有一个点权  。
然后有  组询问，每次询问给定两个点 , ，小y想让alan求出点  到点  的路径权值最大值，注意这个路径不一定是简单路径哦。
特别的，我们定义一条路径的权值为这条路径上的所有点的异或和，注意同一个点在路径上被经过多次那么则计算多次。

具体这里给出数据的生成方式 


    n=read();m=read();Q=read();base=read();xx=read();yy=read();
    ........
    int lastans=0;
    while (Q--){
        xx=((ll)xx*base+lastans)%n+1; 
        yy=((ll)yy*base+lastans)%n+1;
        ...........
        //cur代表当前我们的答案
        lastans=cur;
        ans+=(ll)lastans;
    }
    printf("%lld\n",ans);

输入描述:

第一行三个数
代表图的点数边数和询问的个数
然后一行三个数和一会儿的数据生成方式有关
接下来一行个整数，第个整数。
接下来行每行两个正整数，表示这个图存在一条两个端点为的边。
接下来行每行两个正整数，表示一次小y给alan的询问。

输出描述:

表示个询问的答案的和
示例1

输入

复制 
4 3 5 6 1 4
2 3 1 4
1 2
2 3
2 4

输出

复制 
35

备注: