一只兔子和一只乌龟决定进行一场比赛。由于乌龟来自克拉约瓦（Craiova），而兔子来自特兰西瓦尼亚（Ardeal），乌龟显然比兔子跑得快。我们的目标是帮助兔子赢得比赛。

比赛在一个拥有 $N$ 个节点和 $M$ 条边的图上进行。比赛从节点 $1$ 开始，在节点 $N$ 结束。兔子和乌龟都提前决定了他们将要使用的路径（每个人都有自己的路径）。因此，他们了解图的结构、各自的路径以及穿越图中每条边所需的时间。

乌龟可能比兔子快，但它终究是一只乌龟（我们称之为 George）。George 会在它的路径上选择一些节点，决定在这些地方睡一会儿。如果他在任何时刻意识到兔子作弊了，George 就会停止睡觉，并直接前往终点，不再休息。

兔子（我们称之为 Stan）只有一个优势。Stan 有一位曾曾曾……曾祖母是狐狸，因此他很狡猾。Stan 并不打算遵守他关于路径的承诺（但 George 会遵守）。在某个时刻，他的计划是改变他最初指定的路径，改走前往节点 $N$ 的最短路径。唯一的问题是他必须聪明地行事。一旦 George 发现 Stan 在作弊，他就会停止睡觉，这对他不利。

Stan 只能在节点上改变他的路径（显然不能在边上）。他不知道 George 的睡眠时间表，但你知道！！！请计算 Stan 可以改变路径并赢得比赛的时刻数量。Stan 作弊的瞬间，只要 George 没有在睡觉，他就会立即发现。如果 George 在那个时刻正在睡觉，他会在醒来后发现。

输入格式

第一行包含两个数字 $N$ 和 $M$。接下来的 $M$ 行描述图，每行包含 $(A, B, T, R)$：表示有一条从节点 $A$ 到节点 $B$ 的边。乌龟穿越该边需要 $T$ 个时间单位，而兔子需要 $R$ 个时间单位。第 $i$ 条这样的边被视为索引为 $i$ 的边。

下一行包含一个数字 $P_T$，即 George 路径上的节点数。接下来的 $P_T$ 行描述该路径，每行包含 $(edge\_index, sleep)$：George 将要使用的下一条边的索引，以及他在使用该边后要睡觉的时间单位数。最后一条边的睡眠值无关紧要，因为乌龟届时已经到达终点。

下一行包含一个数字 $P_R$，即 Stan 初始路径上的边数。最后一行包含 $P_R$ 个值，即 Stan 将要使用的边的索引。

输出格式

输出的第一行包含一个值 $x$，即 Stan 可以作弊的时刻（路径上的节点）数量。 第二行包含 $x$ 个数字，按升序排列，表示 Stan 可以作弊的节点索引。

数据范围

• $2 \le N \le 100.000$
• $1 \le P_R, P_T < 100.000$
• $1 \le M \le 200.000$
• $1 \le T, R \le 1.000.000.000$
• $0 \le sleep \le 1.000.000.000$
• 输入中描述路径的边按正确顺序给出。
• 乌龟路径上的节点不重复。
• 兔子路径上的节点不重复。
• 如果兔子和乌龟同时到达终点，兔子获胜。
• 如果兔子在乌龟入睡的瞬间作弊，乌龟会先睡着，只有在醒来后才会意识到作弊。
• 兔子只有在改变路径方向，且他将要采取的新路径严格快于原路径时，才被视为作弊（否则作弊没有意义）。
• 作弊路径可能与原路径有公共节点。唯一的限制是，在作弊的瞬间，兔子必须选择一个不同的节点。如果存在允许的边，他甚至可以回到上一个节点。

样例

样例输入 1

8 12
1 2 2 10
2 3 1 10
3 8 2 10
1 4 10 3
4 5 10 2
5 6 10 4
6 8 10 2
1 7 10 5
4 7 10 2
5 7 10 2
6 7 10 1
7 8 10 1
3
1 3
2 2
3 0
4
4 5 6 7

样例输出 1

2
4 5

样例输入 2

6 6
1 4 1 3
4 6 1 1
4 2 1 6
2 6 6 6
3 4 2 3
1 3 4 5
2
1 2
2 0
4
6 5 3 4

样例输出 2

0