你的州里有若干座城市，城市之间由道路相连。不幸的是，所有的道路都是收费公路！

你现在负责当地的 AAA（美国汽车协会）分会，人们经常向你咨询有关通行费的问题。具体来说，他们一直在询问两座城市之间路径上任意单条道路的通行费！这很奇怪，但这就是他们一直在问的问题！

给定你所在州城市和连接它们的道路的描述，以及一系列由两座不同城市组成的查询，对于每个查询，请确定两件事：

• 第一，使得两座城市之间存在一条路径，且路径上没有任何道路的通行费超过该值的最小值。
• 第二，从你的起始城市出发，使用通行费不超过上述第一个值的任何道路，所能到达的城市数量。

输入格式

输入的第一行包含三个整数 $n$ ($2 \le n \le 2 \times 10^5$)、$m$ ($1 \le m \le 2 \times 10^5$) 和 $q$ ($1 \le q \le 2 \times 10^5$)，其中 $n$ 是城市数量，$m$ 是道路数量，$q$ 是查询数量。城市编号为 $1$ 到 $n$。

接下来的 $m$ 行，每行包含三个整数 $u, v$ ($1 \le u, v \le n, u \neq v$) 和 $t$ ($0 \le t \le 2 \times 10^5$)，表示城市 $u$ 和 $v$ 之间有一条通行费为 $t$ 的道路。道路是双向的，且通行费在两个方向上相同。保证任意两座城市之间都存在路径，且任意两座城市之间最多只有一条道路。

接下来的 $q$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$)。这表示一个关于从 $a$ 到 $b$ 的路径的查询。

输出格式

输出 $q$ 行。每行按照查询出现的顺序输出一个答案。每行输出两个空格分隔的整数 $w$ 和 $k$，其中 $w$ 是使得从 $a$ 到 $b$ 存在一条路径且路径上没有通行费超过 $w$ 的道路的最小值，$k$ 是从 $a$ 出发使用通行费不超过 $w$ 的道路所能到达的城市数量。

样例

样例输入 1

4 3 6
1 2 1
2 3 3
3 4 2
1 2
1 3
1 4
2 3
2 4
3 4

样例输出 1

1 2
3 4
3 4
3 4
3 4
2 2