在遥远的艾莉芬特星球上，有着繁荣的艾莉芬特文明。和地球人一样，艾莉芬特人使用经纬度来标记星球上的每个位置。他们把艾莉芬特星球从北到南划分为n个纬度，从西到东划分为m个经度。在每条经线和纬线相交的地方都有一个国家，他们用(i,j)来表示纬度为i，经度为j的国家，显然一共有个国家。
艾莉芬特人在任意两个经度或者纬度相邻的国家之间都修建了一条双向道路。
考虑经度相邻的情况：对于任意一个国家，它和国家(i,j+1)之间都有一条道路，特别地当j=m时，(i,m)和(i,1)之间也有一条道路。
考虑纬度相邻的情况：对于任意一个国家，它和国家(i+1,j)之间都有一条道路。注意：南北极并不相邻。
艾莉芬特星球并不和平，部分国家卷入了世界大战之中。在接下来q个世纪的第i个世纪里，经度在之间的所有国家都卷入了该世纪发生的世界大战中。当世界大战发生时，被卷入战争的国家都很危险。如果一个国家未被卷入战争，那么它就是一个和平的国家；如果一条道路两端点都是和平的国家，那么它就是一条和平的道路。处于安全考虑，艾莉芬特联合政府会选择只开放一些和平的道路，使得任意两个和平的国家在战争期间都能仅通过这些开放的和平的道路直接或间接连通。
对于任意一条道路，将它保留下来所需的安保代价都不尽相同。请写一个程序，帮助联合政府找到安保代价之和最少的方案。
注意：一个世纪结束后，该世纪的世界大战将会结束，下一场战争的参战国与当前战争的参战国之间没有任何联系。

输入描述:

第一行包含六个正整数，其中n表示纬度的范围，m表示经度的范围。
为了减少输入量，每条道路的安保代价将由以下代码生成，其中addedge(a,b,c,d,w)表示(a,b)和(c,d)之间道路的安保代价为w：
unsigned int SA,SB,SC;
int lim;int getweight(){
    SA^=SA<<16;
    SA^=SA>>5;
    SA^=SA<<1;
    unsignedintt=SA;
    SA=SB;
    SB=SC;
    SC^=t^SA;
    returnSC%lim+1;
}
void gen(){
    scanf("%d%d%u%u%u%d",&n,&m,&SA,&SB,&SC,&lim);
    inti,j,w;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            w=getweight();
            if(j<m){
                addedge(i,j,i,j+1,w);
            }else{
                addedge(i,j,i,1,w);
            }
        }
    for(i=1;i<n;i++)
        for(j=1;j<=m;j++){
            w=getweight();
            addedge(i,j,i+1,j,w);
        }
}
第二行包含一个正整数q，表示询问次数。
接下来q行，每行两个正整数，依次表示每个询问。

输出描述:

输出q行，每行一个整数，依次回答每个询问，即安保代价之和。

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

9
5
13

备注:

对于的数据，。