该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

翻面通行证

题目描述

给定一个包含 $n$ 个节点与 $m$ 条边的无向图。

你在图上行走时，会同时维护一个变量 $x$。变量 $x$ 只可能等于 $0$ 或 $1$。

图中的每条边都有一个权值 $c$，其中 $c \in {0,1}$。

当你经过一条权值为 $c$ 的边时，变量 $x$ 会变成：

其中 $\oplus$ 表示按位异或。

也就是说：

• 如果 $c = 0$，经过这条边后，$x$ 不变；
• 如果 $c = 1$，经过这条边后，$x$ 会在 $0$ 和 $1$ 之间切换。

此外，图中的某些节点是特殊点。

当你位于特殊点时，可以立刻把 $x$ 改成 $0$ 或 $1$ 中的任意一个值，也可以选择不修改。

现给出 $q$ 次独立的询问。每次询问包含四个整数 $s,t,b,e$，代表：

• 你从节点 $s$ 出发；
• 出发时 $x=b$；
• 你想要到达节点 $t$；
• 到达节点 $t$ 时，要求 $x=e$。

你可以重复经过同一个节点或同一条边，也可以选择不经过任何边，直接停留在原地。

请你判断，对于每次询问，是否存在一种合法的行走路线满足上述要求。

输入格式

第一行包含三个整数 $n,m,q$，分别表示图的节点数、边数和询问次数。

第二行包含一个长度为 $n$ 的字符串 $a$：

• 如果 $a_i = \text{'1'}$，表示第 $i$ 个节点是特殊点；
• 如果 $a_i = \text{'0'}$，表示第 $i$ 个节点不是特殊点。

接下来 $m$ 行，每行包含三个整数 $u,v,c$，表示节点 $u$ 和节点 $v$ 之间有一条无向边。

经过这条边时，变量 $x$ 会变成 $x \oplus c$。

接下来 $q$ 行，每行包含四个整数 $s,t,b,e$，表示一次询问。

数据范围

• $1 \le n,q \le 2 \times 10^5$
• $0 \le m \le 2 \times 10^5$
• $1 \le u,v,s,t \le n$，且保证 $u \ne v$
• $c,b,e \in {0,1}$
• 保证输入的图中没有自环，但可能存在重边。

输出格式

对于每次询问，如果存在满足条件的行走路线，输出 YES；否则输出 NO。

输入输出样例 #1

输入 #1

6 4 6
010000
1 2 1
2 3 0
4 5 1
5 6 0
1 3 0 0
1 3 0 1
4 6 0 1
4 6 0 0
1 6 0 1
2 2 0 1

输出 #1

YES
YES
YES
NO
NO
YES

说明/提示

在样例中，只有节点 $2$ 是特殊点。

• 第 1 组询问 $(1,3,0,0)$：

  从节点 $1$ 出发，初始 $x=0$。

  先经过边 $1-2$，这条边的权值为 $1$，所以：

  $$x = 0 \oplus 1 = 1$$

  到达节点 $2$ 后，由于节点 $2$ 是特殊点，可以把 $x$ 改成 $0$。

  然后经过边 $2-3$，这条边的权值为 $0$，所以 $x$ 保持为 $0$。

  最终到达节点 $3$ 时，$x=0$，满足要求，答案为 YES。

• 第 2 组询问 $(1,3,0,1)$：

  同样从节点 $1$ 走到节点 $2$，经过边 $1-2$ 后，$x$ 变成 $1$。

  这次在节点 $2$ 不修改 $x$，然后经过边 $2-3$。

  最终到达节点 $3$ 时，$x=1$，满足要求，答案为 YES。

• 第 4 组询问 $(4,6,0,0)$：

  从节点 $4$ 到节点 $6$ 只能经过路径：

  $$4 \to 5 \to 6$$

  两条边的权值分别为 $1$ 和 $0$，所以最终状态为：

  $$0 \oplus 1 \oplus 0 = 1$$

  这个连通块中没有特殊点，因此无法额外修改 $x$。

  所以不可能在到达节点 $6$ 时使 $x=0$，答案为 NO。

• 第 6 组询问 $(2,2,0,1)$：

  起点和终点都是节点 $2$。

  由于节点 $2$ 本身就是特殊点，可以原地把 $x$ 从 $0$ 改成 $1$。

  因此答案为 YES。