Rabbit vs Turtle

A rabbit named Stan and a turtle named George race on a graph with $N$ nodes and $M$ edges. The race starts at node 1 and ends at node $N$. Each racer picks a path before the race. Both know the graph, both paths, and the time each racer needs to cross each edge.

George chooses some nodes on his path where he sleeps for a while. If George realizes that Stan is cheating, he stops sleeping and runs straight to the finish.

Stan does not intend to keep his promise. At some node he plans to switch from his assigned path to the shortest path to node $N$. He can change paths only while he is at a node, never while he is on an edge. If Stan cheats while George is awake, George notices at once. If George is asleep, he notices when he wakes up.

Count the moments when Stan can switch paths and still win the race.

The first line contains $N$ and $M$. Each of the next $M$ lines has four values $A$, $B$, $T$, $R$, meaning there is an edge from node $A$ to node $B$. George needs $T$ time units to cross it, and Stan needs $R$ time units. The $i$-th edge has index $i$.

The next line contains $P_T$, the number of nodes on George's path. The next $P_T$ lines each contain an edge index and a sleep time: the edge George uses next, and how long he sleeps after using it. The sleep value on the last edge does not matter, since George reaches the finish.

The next line contains $P_R$, the number of edges on Stan's initial path. The last line contains $P_R$ edge indices, the edges Stan uses in order.

On the first line, print $x$, the number of moments when Stan can cheat. On the second line, print the $x$ node indices in ascending order.

• $2 \le N \le 100000$
• $1 \le P_R, P_T < 100000$
• $1 \le M \le 200000$
• $1 \le T, R \le 1000000000$
• $0 \le \text{sleep} \le 1000000000$
• The edges in the path descriptions are given in the correct order.
• The nodes on George's path do not repeat.
• The nodes on Stan's path do not repeat.
• If Stan and George reach the finish at the same time, Stan wins.
• If Stan cheats at the exact moment George starts to sleep, George falls asleep first and notices the cheating only after waking up.
• Stan cheats only if he leaves his original path and the new path is strictly faster than the rest of the original path.
• The cheating path may share nodes with the original path. At the moment of cheating, Stan must take a different edge from his original one. He may return to the previous node if an edge allows it.