問題文

Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ はSplarraay ｽﾌﾟﾗﾚｪｰｲの続編であり、配列を塗りつぶすだけの簡単なゲームです。
プレイヤーはチームAとチームBとチームCとチームDとチームEに分かれ、それぞれのチームを表す色で $1$ つの配列を塗りつぶし合います。
最終的なスコアはそのチームの色で塗りつぶされた要素の数と、後述するボーナスポイントの和で決まり、スコアが高いチームがゲームの勝者となります。

ルール

1. 長さ $N$ の、何色にも塗られていない配列が与えられる。つまり、全ての要素に対して、それぞれの色の厚みは $0$ である。
2. $5$ つのチームは配列のある区間 $[l,r]$ をそのチームの色で塗りつぶしていく。
   その際、
   • 何色にも塗られていなかった場合は、それのチームの色で塗られ、そのチームの色の厚みが $1$ となり、
   • 既にそのチームの色で塗られていた要素に関しては、その色の厚みが $1$ だけ増え、
   • 別のチームの色で塗られていた場合は、後から塗られた色で上書きされ、別のチームの色の厚みを $0$ とした後、自分のチームの色の厚みが $1$ となる。
3. 不定期にボーナスチャンスが与えられる。
   ボーナスチャンスでは区間 $[l,r]$ が与えられ、その時点での区間 $[l,r]$ でのチームXの色の厚みの和を $X_{lr}$（$X=A,B,C,D,E$）とすると、この値が最も大きい方のチームに $\max(A_{lr},B_{lr},C_{lr},D_{lr},E_{lr})$ のボーナスポイントが与えられる。
   値が最も大きい物が複数ある場合、どのチームにもボーナスポイントは与えられない。
4. 時間制限が訪れゲームが終了したとき、配列の全区間 $[0,N−1]$ での、そのチームの色の厚みの和と、それまでに得たボーナスポイントの和がそのチームのスコアとなる。

既にゲームは終了し、後はスコアを計算するだけです。各チームの行動の履歴とボーナスチャンスの詳細が時系列順に与えられるので、最終スコアを算出してください。

入力

$N$
$Q$
$x_1$ $l_1$ $r_1$
$x_2$ $l_2$ $r_2$
$\vdots$
$x_Q$ $l_Q$ $r_Q$

$N$ 塗りつぶし合う配列の長さ
$Q$ 各チームの行動の回数とボーナスチャンスの回数の和。以下 $Q$ 行に渡って行動/ボーナスチャンスの詳細が時系列順に与えられる
$x_k=0$ のとき、区間 $[l_k,r_k]$ のボーナスチャンス
$x_k=1$ のとき、チームAによる区間 $[l_k,r_k]$ への塗りつぶし行動
$x_k=2$ のとき、チームBによる区間 $[l_k,r_k]$ への塗りつぶし行動
$x_k=3$ のとき、チームCによる区間 $[l_k,r_k]$ への塗りつぶし行動
$x_k=4$ のとき、チームDによる区間 $[l_k,r_k]$ への塗りつぶし行動
$x_k=5$ のとき、チームEによる区間 $[l_k,r_k]$ への塗りつぶし行動

また入力は全て整数で与えられ、以下の制約を満たす
$1 \leq N \leq 10^{13}$
$0 \leq Q \leq 150000 = 1.5 \times 10^5$
$0 \leq x_k \leq 5$
$0 \leq l_k \leq r_k < N$

出力

チームAのスコアとチームBのスコアとチームCとチームDとチームEのスコアをそれぞれ ${\rm mod}\ 10^{18}+9$ で空白区切りで出力してください。

サンプル

5
2
1 0 3
2 2 4

2 3 0 0 0

5
3
1 0 4
2 1 3
0 4 4

3 3 0 0 0

6
6
1 1 2
2 4 5
0 2 4
2 0 3
1 1 5
0 0 5

10 1 0 0 0