Pizza Delivery

Alyssa is a college student living in New Tsukuba City. Every street section in the city is one way. A social experiment starting tomorrow reverses one street section between two adjacent intersections each day. All other sections keep their direction, and the reversal is canceled the next day. On day $i$ the reversed section is section $i$.

Alyssa orders a pizza every day from the same pizzeria. The pizza is delivered along the shortest route from the intersection with the pizzeria to the intersection with Alyssa's house.

Changing the traffic regulation may change the shortest route. Report how the experiment affects the delivery route on each day.

The input consists of a single test case in the following format.

n m
a1 b1 c1
.
.
.
am bm cm

The first line contains two integers, $n$, the number of intersections, and $m$, the number of street sections in New Tsukuba City ($2 \le n \le 100000$, $1 \le m \le 100000$). The intersections are numbered $1$ through $n$ and the street sections are numbered $1$ through $m$.

The following $m$ lines contain the information about the street sections, each with three integers $a_i$, $b_i$, and $c_i$ ($1 \le a_i \le n$, $1 \le b_i \le n$, $a_i \ne b_i$, $1 \le c_i \le 100000$). Section $i$ connects two intersections with the one way direction from $a_i$ to $b_i$ and has length $c_i$, and it is the section reversed on day $i$. More than one section may connect the same pair of intersections.

The pizzeria is on intersection $1$ and Alyssa's house is on intersection $2$. At least one route from the pizzeria to Alyssa's house exists before the experiment starts.

Print $m$ lines. Line $i$ must be

• HAPPY if the shortest route on day $i$ becomes shorter,
• SOSO if the length of the shortest route on day $i$ does not change, and
• SAD if the shortest route on day $i$ becomes longer, or if no route from the pizzeria to Alyssa's house remains.

Alyssa does not care whether the delivery bike can go back to the pizzeria.