Problem Statement

Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ is the sequel to Splarraay ｽﾌﾟﾗﾚｪｰｲ, a simple game in which you just paint an array.
The players are divided into Team A, Team B, Team C, Team D, and Team E, and they compete by painting a single $1$ array with the colors representing their teams.
The final score is determined by the sum of the number of elements painted in that team's color and the bonus points described below, and the team with the higher score wins the game.

Rules

1. An array of length $N$, not painted in any color, is given. That is, for every element, the thickness of each color is $0$.
2. The $5$ teams paint some interval $[l,r]$ of the array with their team's color.
   At that time,
   • if an element was not painted in any color, it is painted in that team's color, and the thickness of that team's color becomes $1$;
   • for an element already painted in that team's color, the thickness of that color increases by $1$;
   • if an element was painted in another team's color, it is overwritten by the color painted later: the thickness of the other team's color becomes $0$, and then the thickness of the painting team's color becomes $1$.
3. Bonus chances are given at irregular times.
   In a bonus chance, an interval $[l,r]$ is given. Let $X_{lr}$ ($X=A,B,C,D,E$) be the sum of the thicknesses of Team X's color over the interval $[l,r]$ at that moment. The team with the largest such value receives $\max(A_{lr},B_{lr},C_{lr},D_{lr},E_{lr})$ bonus points.
   If multiple teams share the largest value, no team receives any bonus points.
4. When the time limit arrives and the game ends, the score of a team is the sum of the thicknesses of that team's color over the entire interval $[0,N−1]$ of the array plus the total bonus points it has obtained so far.

The game has already ended, and all that remains is to calculate the scores. The history of each team's actions and the details of the bonus chances are given in chronological order, so compute the final scores.

Input

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

$N$ is the length of the array to be painted.
$Q$ is the total of the number of actions by the teams and the number of bonus chances. Over the following $Q$ lines, the details of the actions/bonus chances are given in chronological order.
When $x_k=0$, it is a bonus chance on the interval $[l_k,r_k]$.
When $x_k=1$, it is a painting action by Team A on the interval $[l_k,r_k]$.
When $x_k=2$, it is a painting action by Team B on the interval $[l_k,r_k]$.
When $x_k=3$, it is a painting action by Team C on the interval $[l_k,r_k]$.
When $x_k=4$, it is a painting action by Team D on the interval $[l_k,r_k]$.
When $x_k=5$, it is a painting action by Team E on the interval $[l_k,r_k]$.

All input values are integers and satisfy the following constraints.
$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$

Output

Output the scores of Team A, Team B, Team C, Team D, and Team E, each modulo ${\rm mod}\ 10^{18}+9$, separated by spaces.

Sample

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