The Quest for El Dorad

有一个王国，包含 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_1 s_2 \cdots s_n，其中每个字符为 0 或 1。如果使用这 k 张票可以从城市 1 到达城市 i，则 s_i = 1；否则 s_i = 0。