题目描述

某个国家有 $n$ 座城市以及 $m$ 条连接城市的双向铁路。第 $i$ 条铁路由第 $c_i$ 家铁路公司运营，铁路的长度是 $l_i$。

您想要从城市 $1$ 开始进行全国旅行。您已经为旅行购买了 $k$ 张车票。第 $i$ 张车票可以记为两个整数 $a_i$ 和 $b_i$，表示如果您使用了这张车票，就可以一次性经过若干条均由公司 $a_i$ 运营的，且总长度不超过 $b_i$ 的铁路。即使您使用了车票，也可以选择待在当前城市。您同时只能使用一张车票，且每张车票只能使用一次。

由于决定车票的使用顺序太麻烦了，您打算直接按现有的顺序使用车票。更正式地，您将执行 $k$ 次操作。在第 $i$ 次操作中，您可以选择待在当前的城市 $u$；也可以选择一座不同的城市 $v$，满足城市 $u$ 和 $v$ 之间存在一条路径，且路径上的所有铁路均由公司 $a_i$ 运营，且铁路总长不超过 $b_i$，然后移动到城市 $v$。

对于每座城市，判断在使用 $k$ 张车票之后能否到达该城市。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：

第一行输入三个整数 $n$，$m$ 和 $k$（$2 \le n \le 5 \times 10^5$，$1 \le m \le 5 \times 10^5$，$1 \le k \le 5 \times 10^5$）表示城市的数量，铁路的数量以及车票的数量。

对于接下来 $m$ 行，第 $i$ 行输入四个整数 $u_i$，$v_i$，$c_i$ 和 $l_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$，$1 \le c_i \le m$，$1 \le l_i \le 10^9$），表示第 $i$ 条铁路连接了城市 $u_i$ 和 $v_i$，该铁路由公司 $c_i$ 运营，且铁路长度为 $l_i$。注意，可能有多条铁路连接同一对城市。

对于接下来 $k$ 行，第 $i$ 行输入两个整数 $a_i$ 和 $b_i$（$1 \le a_i \le m$，$1 \le b_i \le 10^9$），表示如果您使用了第 $i$ 张车票，就可以一次性经过若干条均由公司 $a_i$ 运营的，且总长度不超过 $b_i$ 的铁路。

保证所有数据 $n$ 之和，$m$ 之和与 $k$ 之和均不超过 $5 \times 10^5$。

输出格式

每组数据输出一行一个长度为 $n$ 的字符串 $s_1s_2\cdots s_n$，其中每个字符要么是 $0$，要么是 $1$。如果您可以用 $k$ 张车票从城市 $1$ 到达城市 $i$，则 $s_i = 1$；否则 $s_i = 0$。

2
5 6 4
1 2 1 30
2 3 1 50
2 5 5 50
3 4 6 10
2 4 5 30
2 5 1 40
1 70
6 100
5 40
1 30
3 1 1
2 3 1 10
1 100

11011
100

提示

对于第一组样例数据：

• 为了到达城市 $4$，您可以使用第 $1$ 张车票从城市 $1$ 移动到城市 $2$，然后在使用第 $2$ 张车票的时候待在城市 $2$，然后使用第 $3$ 张车票从城市 $2$ 移动到城市 $4$，然后在使用第 $4$ 张车票的时候待在城市 $4$。
• 为了到达城市 $5$，您可以使用第 $1$ 张车票，经由第 $1$ 条和第 $6$ 条铁路从城市 $1$ 移动到城市 $5$，然后在使用后续车票的时候待在城市 $5$。
• 由于您不能更改使用车票的顺序，您无法到达城市 $3$。