토끼와 거북이

토끼 스탠(Stan)과 거북이 조지(George)가 노드 $N$개와 간선 $M$개로 이루어진 그래프에서 경주한다. 경주는 노드 1에서 시작해 노드 $N$에서 끝난다. 두 선수는 미리 각자 경로를 정했고, 그래프와 두 경로, 그리고 각 간선을 건너는 데 걸리는 시간을 모두 알고 있다.

조지는 자신의 경로에서 몇 개의 노드를 골라 그곳에서 잠시 잔다. 조지가 스탠의 반칙을 알아채면 잠을 멈추고 곧장 결승선으로 달린다.

스탠은 약속을 지킬 생각이 없다. 어떤 노드에서 배정받은 경로를 버리고 노드 $N$까지 가장 짧은 경로로 바꾸려 한다. 경로는 노드에 있을 때만 바꿀 수 있고, 간선 위에서는 바꿀 수 없다. 조지가 깨어 있을 때 스탠이 반칙하면 조지는 즉시 알아챈다. 조지가 자고 있다면 깨어난 뒤에 알아챈다.

스탠이 경로를 바꾸고도 이길 수 있는 시점의 개수를 구하라.

첫 줄에 $N$과 $M$이 주어진다. 이어지는 $M$개의 줄에는 $A$, $B$, $T$, $R$이 주어지며, 노드 $A$에서 노드 $B$로 가는 간선이 있다는 뜻이다. 조지는 이 간선을 $T$의 시간에 건너고, 스탠은 $R$의 시간에 건넌다. $i$번째 간선의 번호는 $i$이다.

다음 줄에는 조지의 경로에 있는 노드 수 $P_T$가 주어진다. 이어지는 $P_T$개의 줄에는 조지가 다음에 사용할 간선 번호와, 그 간선을 건넌 뒤 잘 잠의 길이가 주어진다. 마지막 간선의 잠 시간은 조지가 결승선에 도착하므로 의미가 없다.

다음 줄에는 스탠의 처음 경로에 있는 간선 수 $P_R$이 주어진다. 마지막 줄에는 스탠이 사용하는 간선 번호 $P_R$개가 순서대로 주어진다.

첫 줄에 스탠이 반칙할 수 있는 시점의 수 $x$를 출력한다. 둘째 줄에는 그 $x$개의 노드 번호를 오름차순으로 출력한다.

• $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$
• 경로를 설명하는 간선은 올바른 순서로 주어진다.
• 조지의 경로에 있는 노드는 반복되지 않는다.
• 스탠의 경로에 있는 노드는 반복되지 않는다.
• 두 선수가 같은 시각에 결승선에 도착하면 스탠이 이긴다.
• 스탠이 조지가 잠드는 바로 그 순간에 반칙하면, 조지는 먼저 잠든 뒤 깨어나서야 반칙을 알아챈다.
• 스탠은 원래 경로를 벗어나고, 새 경로가 원래 나머지 경로보다 엄격하게 빠를 때에만 반칙으로 본다.
• 반칙 경로는 원래 경로와 노드를 공유할 수 있다. 반칙하는 순간에는 원래 경로와 다른 간선을 택해야 한다. 간선이 허용하면 이전 노드로 되돌아가도 된다.