Benny likes functions.

Initially, she has an array P consisting of n elements with indices from 0 to $n-1$. All the elements of the array are zeroes.

In this problem, she asks you to help her proceed some queries.

Each query looks like: t l r p. You have to make $P_i = P_i + F_t(i - l, p)$ for all i from l to r.

There are several types of functions.

• List item $F_1(x, p) = \ln(x + 1) \cdot p$, where $0 \le p \le 1337$ and p is integer.
• List item $F_2(x, p) = x^p$, where $p \in {0.25, 0.35, 0.5, 1, 2, 3}$
• List item $F_3(x, p) = \frac{p}{x + 1}$, where $0 \le p \le 1337$ and p is integer.

Input format

The first line contains two integers: n and m.

The next m lines contain four integers t, l, r, p

Constraints

$1 \le n, m \le 10^5$
$0 \le l \le r < n$
$1 \le t \le 3$

Output format

Output the result array P, each number with at least 6 digits after decimal point.

Scoring

Let Q be correct answer and P is the output produced by participant. Then the score is: $-1000 \cdot \ln{\left[ \max\left(\max\limits_i e_i, 10^{-10}\right) \right]}$, where $e_i$ is an error for i-th number, which is computed as $e_i = \frac{|P_i - Q_i|}{\max(1, Q_i)}$.