34951번 - 은하 충돌

문제

우주에는 $N$개의 은하와 $M$개의 블랙홀이 존재한다. 각 은하와 블랙홀은 거리 비용을 가진 단방향 워프 게이트로 연결되어 있으며, 사이클을 이루지 않는다.

우주에는 다음과 같은 시간-거리 개념이 존재한다.

1. 우주의 시간 $T$는 처음에 0ドル$이다.
2. 블랙홀은 각자 양의 정수 크기 $S$를 가진다.
3. 어떤 블랙홀에 처음 도착하는 즉시, 그 블랙홀의 크기 $S$만큼 우주의 시간이 지나 버린다.
4. 우주의 시간이 $S$만큼 흐르면, 모든 은하/블랙홀 간 거리는 중력에 의해 $S$만큼 가까워진다.

두 천체를 잇는 워프 게이트의 길이는 두 천체 간의 거리와 같다.

즉 우주의 시간이 $T$이고 처음 주어진 워프 게이트의 길이가 $w$일 때, 각 워프 게이트의 길이는 $\max(w - T, 0)$으로 정의된다.

워프 게이트로 이동하는 시간은 너무 미미하여 우주의 시간에 영향을 끼치지 않는다.

• 은하 간의 거리가 0ドル$이 되는 순간, 해당 은하들은 서로 충돌하여 그 안에 살던 생명체는 소멸한다.
• 블랙홀과 은하 간의 거리가 0ドル$이 되는 순간에도, 해당 은하는 블랙홀에 영향을 받아 그 안에 살던 생명체는 소멸한다.
• 단, 당신은 소멸하지 않는다.

은하의 번호는 1ドル$부터 $N$까지이고, 블랙홀의 번호는 $-1$부터 $-M$까지이다. 당신은 1ドル$번 은하에 살고 있다. $G$번 은하에는 당신의 원수가 살고 있으며, 당신은 원수가 같은 우주에 존재하는 것을 견딜 수 없다.

1ドル$번 은하에서 출발하여 워프 게이트를 따라 이동하면서 블랙홀을 방문함으로써 우주의 시간을 증가시킬 수 있다. 그 결과, 은하 $G$가 다른 은하 또는 블랙홀과 충돌하여 소멸하도록 만들 수 있는지 판단하자.

입력

첫째 줄에 은하의 개수 $N,ドル 블랙홀의 개수 $M$과 워프 게이트의 개수 $E$가 공백으로 구분되어 주어진다. (2ドル \le N \le 200,000円$; 1ドル \le M \le 200,000円$; 1ドル \le E \le 300,000円$)

다음 $E$개의 줄에 걸쳐, 각 줄에는 워프 게이트 정보 $u,ドル $v,ドル $w$가 공백으로 구분되어 주어진다. 이는 $u$에서 $v$ 방향으로 초기 길이가 $w$인 워프 게이트가 존재함을 의미한다. 두 천체를 같은 방향으로 잇는 워프 게이트는 최대 하나만 존재한다. ($-M \le u, v \le N$; $u \neq 0$; $v \neq 0$; $u \neq v$; 1ドル \le w \le 10^9$)

다음 줄에 $-1, -2, \cdots, -M$번 블랙홀의 크기를 나타내는 $M$개의 정수 $S_1, S_2,\cdots, S_M$이 공백으로 구분되어 주어진다. (1ドル \le S_i \le 10^9$)

다음 줄에 원수가 사는 은하의 번호 $G$가 주어진다. (2ドル \le G \le N$)

출력

은하 1ドル$에서 출발해 우주의 시간을 충분히 증가시켜 은하 $G$가 다른 천체와 충돌하여 소멸할 수 있다면 HAPPY를 출력하고, 그렇지 않다면 SAD를 출력한다.

제한

노트