Problem Statement

You are given a performance procedure for $N$ performers, numbered from performer $1$ to performer $N$. The procedure consists of $Q$ instructions, and the $i$-th instruction is "Performer $I_i$ shall play from time $S_i$ to time $T_i$." Here, time $X$ means the moment $X$ seconds after the whole performance begins. A performer who is playing at some time is never given another instruction to play at that time.

Each performer has a prominence defined according to the performance so far, and at time $0$ the prominence of every performer is $0$. While nobody is playing, the prominence does not change. While $n$ people $(1 \leq n)$ are playing, the prominence of each playing performer increases by $ \frac {1}{n}$ per $1$ second.

Find the final prominence of each performer when the performance is played to the end according to this procedure.

Constraints

• All values are integers.
• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq I_i \leq N$
• $0 \leq S_i \lt T_i \leq 10^5$
• When $i \neq j$ and $I_i = I_j$, the interval $[S_i,T_i]$ and the interval $[S_j,T_j]$ have no range in common.

Input

The input is given from standard input in the following format.

$N$ $Q$
$I_1$ $S_1$ $T_1$
$I_2$ $S_2$ $T_2$
$ \hspace{5px}\vdots $
$I_Q$ $S_Q$ $T_Q$

Output

The output consists of $N$ lines. On the $i$-th line, print the final prominence of performer $i$ as a decimal.

For each value, reference data has been prepared whose absolute or relative error from the true value is at most $10^{-8}$, and your output is accepted if the absolute or relative error of the value printed by the submitted program, measured against that data, is at most $10^{-5}$. Print a newline at the end.

Sample

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

0.14285714285714
0.14285714285714
0.14285714285714
0.14285714285714
0.14285714285714
0.14285714285714
0.14285714285714

2 3
1 0 10000
1 20000 30000
1 40000 50000

30000
0

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

2.59285714285714
1.75952380952381
1.45952380952381
1.37619047619048
1.45952380952381
1.75952380952381
2.59285714285714