Meitou-nao and Bu-gaoxing are inseparable best friends who go to school and play together.

One day, the two friends get together to play a card game. There are $N$ cards in total, each labeled with a unique number from $1$ to $N$. According to their rules, at the beginning of each game, all cards must be arranged in order from $1$ to $N$. After happily finishing a game, they find that the order of the cards is in a mess, and sorting them back is quite a troublesome task.

They arrange the messy cards in a row on the table and begin the sorting process. Because Bu-gaoxing lost the game, he is very unhappy. He only sorts the cards at odd-numbered positions into ascending order and pushes the rest of the task to Meitou-nao. Meitou-nao is quite scatterbrained, and he adopts a rather clumsy sorting method: he repeatedly finds two adjacent cards that are in the wrong order and swaps them until the entire sequence is sorted.

As someone who loves to explore, you want to study the time Meitou-nao spends swapping cards when the initial permutation is random. Assuming that each swap of a pair of cards takes $1$ unit of time, you want to find the expected value of his sorting time. Furthermore, to better analyze this problem, you also want to calculate the variance of the time spent. Even further, if the positions that Bu-gaoxing sorts change, can you still calculate the expected value of the time Meitou-nao spends sorting?

Input

The input file contains $M+1$ lines.

The first line contains two positive integers $N$ and $M$.

The next $M$ lines each contain three integers $l$, $r$, and $v$, where $1 \leq l \leq r \leq N$ and $v \in \{0, 1\}$. If $v = 0$, it means Bu-gaoxing no longer sorts the positions from $l$ to $r$; conversely, if $v = 1$, it means the positions sorted by Bu-gaoxing will now include the range from $l$ to $r$.

Output

The output file contains $M+2$ lines. Each line should output a rational number in the form $p/q$, where $(p, q) = 1$, $q \geq 1$, and $p, q \in \mathbb{Z}$.

The first line outputs the expected value of Meitou-nao's sorting time under the initial conditions.

The second line outputs the variance of Meitou-nao's sorting time under the initial conditions.

The next $M$ lines each output the expected value of Meitou-nao's sorting time after each respective modification to the positions sorted by Bu-gaoxing.

Examples

Input 1

3 3  
2 3 0  
2 2 1  
1 3 1

Output 1

2/3  
2/9  
3/2  
1/1  
0/1

Note 1

Under the initial conditions, Bu-gaoxing will sort the cards at positions $1$ and $3$. For permutations $(1,2,3)$ and $(3,2,1)$, he will arrange them into $(1,2,3)$, and Meitou-nao needs no operations; for permutations $(1,3,2)$ and $(2,3,1)$, he will arrange them into $(1,3,2)$, and Meitou-nao needs one swap; for permutations $(2,1,3)$ and $(3,1,2)$, he will arrange them into $(2,1,3)$, and Meitou-nao needs one swap. Therefore, the expected time spent by Meitou-nao is $(0 \times 2 + 1 \times 2 + 1 \times 2)/6 = 2/3$; the variance is $((0 - 2/3)^2 \times 2 + (1 - 2/3)^2 \times 2 + (1 - 2/3)^2 \times 2)/6 = 2/9$.

After the first modification, Bu-gaoxing only sorts position $1$, which has the same effect as not sorting at all; after the second modification, he sorts positions $1$ and $2$; after the last modification, he sorts positions $1, 2, 3$, so Meitou-nao does not need to participate in the sorting work at all. The expected values for these cases can be calculated accordingly.

Subtasks

If the first two lines of the output are correct and the remaining lines are incorrect, you can receive $40\%$ of the points.

If the first two lines of the output are incorrect and the remaining lines are correct, you can receive $50\%$ of the points.

If all lines of the output are completely correct, you can receive $100\%$ of the points.

In all other cases, you receive no points.

Constraints