쿠어리

길이가 n이고 초기값이 모두 0인 수열 X가 존재한다.

다음과 같은 쿼리가 m번 입력된다.

a b -> a<=i<=b 일 때 Xi에 (i-a+1)^3을 더한다.

모든 쿼리의 처리가 끝난 후 수열 X를 출력하라

input

첫째 줄에 n m 이 차례로 입력된다(1<=n,m<=100000)

다음줄부터 ai bi가 m번 입력된다.(1<=ai<=bi<=n)

output

모든 쿼리 처리가 끝난 수열 X를 출력한다. 수가 너무 커지기 때문에 모든 값은 10억7로 나눈값을 출력하다.
 
example

5 2

1 5
1 5

답

2 16 54 128 250