你正在为一次冒险做准备。这次冒险是在一个有向无环图（DAG）上从起点到终点的旅程。该 DAG 有 $n$ 个顶点，编号为 $0$ 到 $n - 1$，以及 $m$ 条边。起点是顶点 $0$，并且所有顶点都可以从起点到达。

每条从 $u_i$ 到 $v_i$ 的有向边都有两个属性：$l_i$ 和 $r_i$。它们表示安全通过该边所需的最少和最多时间。因此，你可以将该边的计划时间设置为区间 $[l_i, r_i]$ 内的任意整数 $t_i$。

你的许多朋友也在为这次冒险做准备。他们每个人都将选择一条不同的从起点到终点的路线。为了确保安全，你希望选择不同路线的朋友能够同时在每个顶点相遇。也就是说，你希望为每条边设置计划时间，使得对于每个顶点 $u$，所有从起点到 $u$ 的路径都具有相同的总时间。

如果一个图满足上述要求，我们称其为安全的。保证初始图是安全的。

任务 1

你想向图中添加一些新边以使其更有趣。你将执行 $q$ 次“添加新边”的操作。每次操作提供一条新的有向边 $(u_i, v_i, l_i, r_i)$。你已知在添加这条边后，图仍然是一个有向无环图，但不确定该图是否仍然安全。请判断在添加这条边后，图是否安全。如果是，则将该边添加到图中；如果不是，则应忽略此操作。

任务 2

在所有操作之后，你需要输出每条边（包括新添加的边）的计划时间，以证明你确定新图是安全的。

实现细节

你需要实现两个函数。

第一个需要实现的函数是 add_roads：

boolean[] add_roads(int32 N, int32 M, int32 Q,
 int32[] U, int32[] V,
 int32[] L, int32[] R,
 int32[] U2, int32[] V2,
 int32[] L2, int32[] R2);

• N：顶点数量；
• M：初始边数；
• Q：操作数量；
• U, V：长度为 M 的数组，其中 (U[i], V[i]) 表示第 i 条有向边；
• L, R：长度为 M 的数组，其中 [L[i], R[i]] 是边 i 的可行时间区间；
• U2, V2, L2, R2：长度为 Q 的数组，描述新边；
• 该函数在每个测试用例开始时被精确调用一次。

该函数应返回一个长度为 Q 的数组，如果第 i 次操作的边被添加，则第 i 个元素为 true，否则为 false。

第二个需要实现的函数是 assign_times：

int32[] assign_times();

• 该函数在调用 add_roads 之后，在每个测试用例中被精确调用一次。

该函数应返回一个数组，包含最终图中存在的每条边的计划时间 $t_i$（可以以任何有效顺序返回）。

数据范围

• $3 \le n \le 500$
• $n - 1 \le m \le 10^5$
• $0 \le q \le 500$
• $0 \le u_i < v_i < n$
• $1 \le l_i \le r_i \le 10^9$

子任务

1. (7 分): $n \le 3$
2. (21 分): $q = 0$
3. (12 分): $v_i = u_i + 1$
4. (11 分): $l_i = r_i$
5. (24 分): $n \le 100, m \le 100, q \le 100$
6. (25 分): 无附加限制

样例

输入样例 1

add_roads(4, 4, 2,
 [0, 1, 0, 0],
 [1, 3, 3, 2],
 [1, 3, 9, 6],
 [5, 7, 14, 8],
 [2, 2],
 [3, 3],
 [7, 5],
 [11, 7]);

assign_times();

输出样例 1

add_roads 返回: [false, true]
assign_times 返回: [5, 7, 12, 6, 6]

样例评测程序

样例评测程序将按以下格式读取输入：

• 第 1 行：三个整数 $n$，$m$ 和 $q$
• 接下来 $m$ 行：每行四个整数 $u_i$，$v_i$，$l_i$，$r_i$，描述每条边
• 接下来 $q$ 行：每行四个整数 $u_i$，$v_i$，$l_i$，$r_i$，描述每次操作