Alyssa 是一名大学生，住在新筑波市。城里的所有街道都是单行道。明天将开始一项新的社会实验，旨在进行替代交通管制，即反转某些街道的方向。每天，只有两条相邻交叉路口之间的一条街道会被反转方向；其他所有街道的方向保持不变，且该反转会在第二天取消。

Alyssa 每天都从同一家披萨店订购披萨。披萨沿着从披萨店所在交叉路口到 Alyssa 家所在交叉路口的最短路径进行配送。

改变交通管制可能会改变最短路径。请告诉 Alyssa 这项社会实验将如何影响披萨的配送路线。

输入格式

输入包含单个测试用例，格式如下：

$n$ $m$ $a_1$ $b_1$ $c_1$ $\vdots$ $a_m$ $b_m$ $c_m$

第一行包含两个整数 $n$（交叉路口的数量）和 $m$（新筑波市街道的数量）（$2 \le n \le 100\,000$，$1 \le m \le 100\,000$）。交叉路口编号为 $1$ 到 $n$，街道编号为 $1$ 到 $m$。

接下来的 $m$ 行包含街道信息，每行包含三个整数 $a_i, b_i, c_i$（$1 \le a_i \le n, 1 \le b_i \le n, a_i \neq b_i, 1 \le c_i \le 100\,000$）。这表示编号为 $i$ 的街道连接两个交叉路口，单行方向从 $a_i$ 到 $b_i$，该方向将在第 $i$ 天被反转。该街道的长度为 $c_i$。注意，连接同一对交叉路口的街道可能不止一条。

披萨店位于交叉路口 $1$，Alyssa 的家位于交叉路口 $2$。保证在社会实验开始前，至少存在一条从披萨店到 Alyssa 家的路径。

输出格式

输出应包含 $m$ 行。第 $i$ 行应为：

• HAPPY：如果第 $i$ 天的最短路径变短了。
• SOSO：如果第 $i$ 天的最短路径长度没有变化。
• SAD：如果第 $i$ 天的最短路径变长了，或者从披萨店到 Alyssa 家不再有路径。

Alyssa 不介意送货车是否能回到披萨店。

样例

样例输入 1

4 5
1 3 5
3 4 6
4 2 7
2 1 18
2 3 12

样例输出 1

SAD
SAD
SAD
SOSO
HAPPY

样例输入 2

7 5
1 3 2
1 6 3
4 2 4
6 2 5
7 5 6

样例输出 2

SOSO
SAD
SOSO
SAD
SOSO

样例输入 3

10 14
1 7 9
1 8 3
2 8 4
2 6 11
3 7 8
3 4 4
3 2 1
3 2 7
4 8 4
5 6 11
5 8 12
6 10 6
7 10 8
8 3 6

样例输出 3

SOSO
SAD
HAPPY
SOSO
SOSO
SOSO
SAD
SOSO
SOSO
SOSO
SOSO
SOSO
SOSO
SAD