시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 178 55 46 34.328%

문제

지훈이는 수열을 좋아한다. 지금 지훈이는 size 가 N 인 수열을 가지고 놀고 있다. 지훈이는 K 개의 쿼리에 따라 수열을 변화시킬 것인데, 쿼리의 형식 및 작업 과정은 다음과 같다.

  • L R X : 수열을 오름차순으로 정렬한 결과를 A[1], A[2], … , A[N]이라 하자. 우선 A[L], A[L+1], … , A[R]에 X 만큼 더한다. 그 결과 수열을 다시 오름차순으로 정렬한다.

쿼리들을 순서대로 모두 수행한 후의 수열을 출력하라.

입력

첫째 줄에 N 과 K 가 띄어쓰기로 구분되어 주어진다. (N <= 100000, 1 <= K <= 1000)

둘째 줄에 절댓값이 10^18 이하인, 수열을 이루는 N 개의 숫자가 주어진다.

셋째 줄부터 K+2 번째 줄까지 쿼리 L R X 가 주어진다. (1<=L<=R<=N, |X| <= 10^9)

출력

쿼리들을 순서대로 모두 수행한 후의 수열을 출력한다.

예제 입력

7 3
1 2 3 4 5 6 7
1 6 3
2 7 -4
4 5 6

예제 출력

1 2 3 4 5 9 10

힌트

출처

University > KAIST > 2016 KAIST 6th ACM-ICPC Mock Competition J번

  • 빠진 조건을 찾은 사람: doju
  • 문제를 만든 사람: jihoon