$1$ から $N$ までの番号が振られた $N$ 個の地点があります。

また、M本の道があり、$i$ 番目 $(1 \le i \le M)$ の道は地点 $a_i$ と地点 $b_i$ を結び、傾斜は $r_i$ あります。これらの道は双方向に移動可能です。

地点 $1$ にいる寺子さんは地点 $N$ にいる庵流くんに伝えたいことがあるため、地点 $N$ に行くことにしました。

寺子さんは道 $i$ を通るたびに $r_i$ 回「EHHO」と発言します。寺子さんはそれを言うのが恥ずかしいので、少ない発言で庵流君のところに行きたいと思っています。

寺子さんが最小の発言で庵流君のところに到着するよう道を選んだ時、発言した文字を出力してください。

• $2 \le N \le 10^5$
• $N-1 \le M \le min(10^6, \frac{N(N-1)}{2})$
• $1 \le a_i, b_i \le N$
• $1 \le r_i \le 90$
• 入力は全て整数
• 任意の地点から任意の地点へ道を通って移動可能

寺子さんが「EHHO」と言う回数を $E$ として、$E$ 行 EHHO を出力してください。

$\verb|EHHO|$
$\verb|EHHO|$
$\vdots$
$\verb|EHHO|$