题目描述

​ 教练给小Z布置了一个作业，教练给出了 $n$ 个命题，让他证明 $n$ 个命题全部为真。但是小Z非常的懒，一旦需要证明的命题数量大于 $K$，小Z就会摆烂不完成作业。因此小Z向他的好朋友黑恶卷怪小L求助。小L帮小Z证明了 $m$ 个等价关系，即对于 $1\leq i\leq m$，小L证明了 $u_i$ 和 $v_i$ 是等价的。小L把他的成果发给了小Z，但是网络质量不佳，小Z只收到了一个区间的等价关系证明。

​ 现在有 $q$ 条时间线，你需要对于每条时间线，求出假如小Z收到了第 $l\sim r$ 个等价关系的证明，小Z是否能够完成作业。

输入格式

​ 第一行四个整数 $n,m,K,tp$，分别表示小Z需要证明的命题个数，小L证明出的等价关系数，小Z摆烂的临界值，是否强制在线。

​ 接下来 $m$ 行，第 $i+1$ 行包含两个整数 $u_i,v_i$ ，表示小L的第 $i$ 个证明给出了 $u_i$ 和 $v_i$ 是等价的结论。

​ 第 $m+2$ 行一个整数 $q$ ，表示时间线的个数。

​ 接下来 $q$ 行，每行两个整数 $l_i,r_i$，表示小Z收到了第 $l_i\sim r_i$ 个证明，你需要求出小Z是否能够完成作业。如果小Z能够完成作业，输出 “Yes”（不包含引号），如果小Z会摆烂不完成作业，输出 “No”（不包含引号）。

​ 如果 $tp=1$，表示输入的 $l_i$ 和 $r_i$ 是经过加密的。用 $lans_{i-1}$ 表示 $1\sim i-1$ 个询问的答案按顺序从左到右拼接构成的二进制数（Yes视为 $1$，No视为 $0$），你需要令 $l_i\leftarrow \left(\left((l_i+lans_{i-1})\ \operatorname{mod}\ 2^{32}\right)\ \operatorname{mod}\ m\right)+1$，$r_i\leftarrow \left(\left((r_i+lans_{i-1})\ \operatorname{mod}\ 2^{32}\right)\ \operatorname{mod}\ m\right)+1$，然后如果 $l_i>r_i$ 则交换 $l_i,r_i$ 。

​ 以下参考代码片段实现了这一强制在线的过程：

unsigned lans=0;
for(int i=1;i<=q;++i){
    int l,r;
    std::cin>>l>>r;
    if(tp==1){
        l=(l+lans)%m+1;
        r=(r+lans)%m+1;
        if(l>r) std::swap(l,r);
    }
    //solve
    lans<<=1;
    if(Answer_Is_Yes) ++lans;
}

本题下发文件中的 online.cpp 会包含该代码段。

输出格式

​ 每行一个字符串 Yes 或者 No，表示小Z是否能够完成作业。

样例一

input

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

output

Yes
Yes
Yes
No
Yes

样例二

input

10 10 6 1
3 9
2 3
7 10
5 3
2 10
4 8
7 6
3 2
4 3
10 10
10
6 7
9 10
3 8
6 7
3 7
1 3
7 10
3 5
4 9
5 6

output

No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No

样例解释二

加密前的原始数据为

7 8
1 10
5 10
1 10
1 5
7 9
1 8
5 7
2 7
1 2

限制与约定

​ 对于 $100\%$ 的数据，满足 $1\leq n,m\leq 2\times 10^5$，$1\leq K\leq n$，$tp\in \{0,1\}$，$1\leq q\leq 5\times 10^5$，$1\leq u_i,v_i\leq n$，$1\leq l_i,r_i\leq m$，当 $tp=0$ 时，有 $l_i\leq r_i$ 。