[YsOI2020] 幼儿园

Ysuperman 热爱在 TA 的幼儿园里散步，为了更方便散步， TA 把幼儿园抽象成 $n$ 个点，$m$ 条边的**有向图**。 散步得多了， TA 就给了每一条边**无与伦比**的亲密程度：$1,2,\cdots,m$，越大代表越亲密。 TA 也给了每一个点无与伦比的编号：$1,2,\cdots,n$，其中 $1$ 代表着幼儿园大门，但是每个**点是没有亲密程度的**。 接下来 $k$ 天，Ysuperman 每天会有一次散步计划。具体而言， TA 希望从 $x_i$ 号点出发，只经过**亲密程度属于区间 $[l_i,r_i]$ 的边**，走到幼儿园大门 $1$ 号点，期间经过的边的亲密程度必须**单调递减**，不然会因为 TA 有强迫症而不能回家。 Ysuperman 看着自己刚刚画的草稿脑子一团浆糊， TA 发现 TA 始终没有办法规划出这么多合理路线，现在 TA 想请你帮 TA 。具体而言，对于每一天的计划，如果可行，则输出 `1`，反之输出 `0`。 当然啦，有的时候 Ysuperman 很着急，需要你立马回复，有的时候 TA 可以等等你，先把所有问题问完再等你回复。

第一行三个整数 $n,m,k,w$，分别表示节点个数、边个数、Ysuperman 的计划个数，和 Ysuperman 的焦急程度，此处的 $w$ 在后续输入中有用。 此后 $m$ 行的第 $i$ 行有两个整数 $u_i,v_i$，表示 Ysuperman 的幼儿园里有一条 $u_i$ 号点到 $v_i$ 号点的单向边，且**亲密程度为** $i$。 此后 $k$ 行的第 $i$ 行有三个整数 $x_i,l_i,r_i$，表示 Ysuperman 的第 $i$ 个计划。 此处如果 $w=0$，则 $x_i,l_i,r_i$ 为明文，可以直接使用。 如果 $w=1$，则 $x_i,l_i,r_i$ 为密文，你需要将它解密。解密操作是：令 $L$ 为之前所有询问的输出之和（没有询问过则为 $0$），你需要将 $x_i ,l_i,r_i$ 都异或 $L$。

$k$ 行，每行只可能是 `1` 或 `0`，第 $i$ 行的数表示第 $i$ 个计划是否可行。

5 7 5 0
3 2
1 2
4 3
5 4
3 1
5 3
5 1
3 1 4
1 2 2
5 5 6
4 5 7
2 1 7

0
1
1
0
0

5 12 10 0
4 2
4 2
5 3
3 3
1 5
1 4
4 4
2 4
5 3
1 5
2 2
4 1
4 3 5
4 2 3
1 4 5
3 1 8
3 1 4
3 5 5
2 1 12
4 10 12
2 5 5
1 1 3

0
0
1
0
0
0
0
1
0
1

5 12 10 1
4 2
4 2
5 3
3 3
1 5
1 4
4 4
2 4
5 3
1 5
2 2
4 1
4 3 5
4 2 3
1 4 5
2 0 9
2 0 5
2 4 4
3 0 13
5 11 13
0 7 7
3 3 1

0
0
1
0
0
0
0
1
0
1

### 样例说明 #### 样例说明 $1$  对于第 $2$ 条计划，Ysuperman 已经站在门口，所以计划可行。 对于第 $3$ 条计划，Ysuperman 只能通过路径 $5 \overset{6}{\rightarrow}3 \overset{5}{\rightarrow} 1$。（箭头上方数字表示的是边的亲密程度）。 其他计划都是不可行的。 #### 样例说明 $3$ 样例三为加密后的样例二。 ---- ### 数据范围 **本题采用捆绑测试。** | $\mathrm{subtask}$ | $n$ | $m$ | $k$ | 特殊性质 | 分数 | | :----------------: | :---------: | :--------------: | :---------------: | :---------: | :---: | | $1 $ | $\le17$ | $\le17$ | $\le 2\cdot 10^5$ | / | $ 5$ | | $2$ | $\le500$ | $\le500$ | $\le500 $ | / | $17$ | | $3 $ | $\le 3000$ | $\le 3000 $ | $\le 3000 $ | / | $18 $ | | $ 4 $ | $\le10^5$ | $\le2\cdot10^5$ | $\le2\cdot10^5$ | $v_i=1$ | $13$ | | $5 $ | $\le 10^5$ | $\le 2\cdot10^5$ | $\le 10^5$ | $l_i=1,w=0$ | $ 7 $ | | $6$ | $\le10^5 $ | $\le2\cdot10^5$ | $\le 10^5$ | $w=0 $ | $13 $ | | $7$ | $ \le 10^5$ | $\le 2\cdot10^5$ | $\le 2\cdot10^5$ | / | $27$ | 对于 $100\%$ 的数据，满足 $1 \le n \le 10^5 ,1 \le m \le 2\cdot10^5 ,0 \le k \le 2\cdot10^5$。 $w\in\{0,1\},1 \le u_i,v_i \le n$。 $x_i,l_i,r_i$ 在解密后保证 $1\le x \le n ,1 \le l_i,r_i \le m $。 ### 提示 **不保证不出现重边自环，不保证图联通**。