Novak 和 Rafael 正在玩一个简化版的 Alias 游戏。Novak 需要让 Rafael 在不直接说出某个单词的情况下猜出它。Rafael 的脑海中有一个包含 $n$ 个单词的数据库，并且某些单词之间存在 $m$ 条关联。单词 $x$ 和 $y$ 之间用时为 $t$ 的关联意味着：如果 Rafael 想起或听到了单词 $x$，在 $t$ 毫秒后他就会想起单词 $y$。

Novak 和 Rafael 将进行 $q$ 轮游戏。在每一轮中，Novak 想知道：如果他说出单词 $a$，Rafael 在多少毫秒后会第一次想起单词 $b$？各轮游戏之间是独立的。

输入格式

第一行包含两个整数 $n$ ($2 \le n \le 1000$) 和 $m$ ($1 \le m \le 1000$)，分别表示单词的数量和关联的数量。

接下来的 $m$ 行，每行包含两个不同的单词 $x_i$ 和 $y_i$，以及一个整数 $t_i$ ($1 \le t_i \le 10^9$)，描述一条关联。单词最多由 20 个英文小写字母组成。Rafael 数据库中的所有单词都将至少出现一次。某些单词对之间可能存在多条关联。

下一行包含一个整数 $q$ ($1 \le q \le 1000$)，表示轮数。

接下来的 $q$ 行，每行包含两个不同的单词 $a_i$ 和 $b_i$，分别表示在第 $i$ 轮中 Novak 将说出的单词和 Rafael 需要想起来的单词。这两个单词都存在于 Rafael 的数据库中。

输出格式

输出 $q$ 行。在第 $i$ 行中，输出第 $i$ 轮所需的毫秒数；如果 Rafael 永远无法想起该单词，则输出 Roger。

子任务

• 在价值 20 分的测试数据中，满足 $1 \le n \le 10$。
• 在额外价值 20 分的测试数据中，满足 $1 \le n \le 100$。

样例

输入样例 1

3 2
novak goat 1
goat simulator 3
2
novak simulator
simulator goat

输出样例 1

4
Roger

输入样例 2

3 3
kile legend 4
legend beer 5
beer kile 6
2
kile beer
legend kile

输出样例 2

9
11

输入样例 3

4 5
rafael me 5
me ow 6
ow ausopenfinal 2012
ausopenfinal me 2
rafael ausopenfinal 2
3
rafael me
me rafael
ow me

输出样例 3

4
Roger
2014

说明

第一个样例解释：

在第一轮中，Novak 会说出单词 novak。1 毫秒后，Rafael 会想起单词 goat，再过 3 毫秒后，他会想起目标单词 simulator（共用时 4 毫秒）。在第二轮中，Novak 会说出单词 simulator，但 Rafael 无法想起任何其他单词。