Informatica Online Judge

  악덕 시장 [2173 / 087D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 5   Total Tried : 5


The Champion of this Problem (C++) : gs17003 - 0ms / 799byte
My Best Submission (C++) : N/A

[koistudy.net (33th 최지원)]

Background

경곽의 합법 마약 koi를 독점 생산하는 koistudy의 악덕 사장 admin은 지원이를 가둬놓고 아래와 같은 쿼리를 $n$개 처리하게 하고 있다

처리하지 못하면 더이상 koi를 할 수 없다!

$a$ $b$ $c$ : 수열 $x$에서 $a$~$b$ 번째 수에 $c$씩 더한다

금단 현상으로 고통받는 지원이는 다행히 이것을 시간 복잡도 $O(n)$만에 해결할 수 있었다.

하지만 admin은 쿼리를 더 어렵게 바꿔놓았다!

$a$ $b$ : 수열 $x$에서 ($a≤i≤b$) $i$번째 수에 $(i-a+1)(i-a+2)/2$ 씩 더한다

지원이는 이를 놀라운 방법으로 해결했지만, 베터리가 부족하여 다 코딩하지 못한다.

금단 현상에 미쳐가는 지원이를 대신해 쿼리를 처리해 주자

Input

첫번째 줄에 수열 $x$의 길이 $n$과 쿼리의 개수 $q$가 주어진다.

수열 $x$의 초기값은 모든 자리에서 $0$이다.

이후로 각 $i$번째 줄에 쿼리가 다음과 같이 $n$줄에 걸쳐서 입력된다.

$a_i$ $b_i$

[입력값의 정의역]
$1≤n, q≤100,000$
$1≤a_i≤b_i≤n$

Output

모든 쿼리를 처리한 후 수열 $x$를 출력한다.

값이 너무 커지기 때문에 $10^9+7$로 나눈 나머지를 출력한다.

IO Example

입력
5 1
1 3

출력
1 3 6 0 0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]