灰烬魔女 Elena 决定在一个魔法国度度过一段时间，现在她正在寻找一个落脚点。这个国家由 $N$ 个城市组成，编号从 $1$ 到 $N$，并由 $M$ 条单向街道连接。由于城际旅行的飞行魔法已被禁止，Elena 必须依靠这些街道在城市之间移动。

每条街道由四个整数 $u, v, p$ 和 $h$ 描述，意味着有一条从城市 $u$ 通往城市 $v$ 的道路，需要 $p$ 级的通行证，且通行需要 $h$ 小时。要使用一条街道，Elena 需要一张通行证。如果她持有 $p$ 级的通行证，她可以使用任何通行证等级要求小于或等于 $p$ 的街道。从城市 $u$ 到城市 $v$ 可能存在多条街道。

Elena 为她的旅程准备了 $Q$ 个问题，每个问题属于以下两种类型之一：

• 类型 1：Elena 正在考虑住在城市 $u$，她想知道所需的最低通行证等级，使得在该通行证下，从城市 $u$ 到任何城市所需的旅行时间都不超过 $h$ 小时。
• 类型 2：Elena 正在选择居住地，她想找到一个城市，使得从该城市出发，她可以在 $h$ 小时内到达任何城市，同时所需的通行证等级尽可能低。如果有多个城市满足相同的最低要求，她会选择城市编号最小的那一个，因为那里的平均生活成本较低。

输入格式

第一行包含三个整数 $N, M$ 和 $Q$ ($2 \le N \le 100, 1 \le M \le 10^4, 1 \le Q \le 10^5$)，分别表示城市数量、街道数量和询问数量。

接下来的 $M$ 行，每行包含四个整数 $u, v, p$ 和 $h$ ($1 \le u, v \le N, u \neq v, 1 \le p \le 10^9, 1 \le h \le 10^9$)，表示有一条从城市 $u$ 到城市 $v$ 的道路，需要 $p$ 级的通行证，且通行需要 $h$ 小时。

接下来的 $Q$ 行描述了询问，每行遵循以下两种格式之一：

• 类型 1：1 u h ($1 \le u \le N, 1 \le h \le 10^{12}$, $u$ 和 $h$ 为整数)
• 类型 2：2 h ($1 \le h \le 10^{12}$, $h$ 为整数)

输出格式

对于每个询问 $i$ ($1 \le i \le Q$)，输出第 $i$ 个询问的答案。

如果询问是类型 1，输出一个整数——所需的最低通行证等级。如果没有有效的答案，输出 -1。

如果询问是类型 2，输出两个整数——城市编号和所需的最低通行证等级。如果不可能，输出 -1 -1。如果有多个城市达到相同的最低通行证等级，输出编号最小的那个。

样例

输入 1

5 6 4
1 2 1 3
2 3 1 1
3 4 1 2
4 5 1 3
5 1 1 2
1 3 2 1
1 1 9
2 8
1 1 8
1 1 5

输出 1

1
2 1
2
-1

说明

在第一个问题中，Elena 决定住在城市 1。使用 1 级通行证，到达城市 5 所需时间最长，为 9 小时——仍在时间范围内。

在第二个问题中，使用 1 级通行证，Elena 可以从城市 2 在 8 小时内到达任何城市。城市 5 也达到了相同的时间，但其编号更大。

在第三个问题中，使用 2 级通行证，Elena 可以从城市 1 在 3 小时内到达城市 2，在 1 小时内到达城市 3，在 3 小时内到达城市 4，在 6 小时内到达城市 5。

在第四个问题中，无论使用何种等级的通行证，Elena 都无法在 6 小时内从城市 1 到达城市 5。