수열 정렬 쿼리

시간 제한1초메모리 제한128 MB

요약
수열이 주어질 때, 각 질의마다 수열을 정렬한 뒤 L번째부터 R번째 원소에 X를 더하고 다시 정렬한다. 모든 질의를 처리한 뒤의 수열을 오름차순으로 출력한다.
난이도

보통10점 중 6점

유형
정렬, 구현, 누적 합, 그리디
정답자
아직 제출이 없습니다

문제

지훈이는 길이가 NN인 수열을 가지고 논다. 지훈이는 이 수열에 KK개의 쿼리를 주어진 순서대로 적용한다.

쿼리 LL RR XX는 다음과 같이 처리한다.

  1. 수열을 오름차순으로 정렬하고, 그 결과를 A1,A2,…,ANA_1, A_2, \dots, A_N이라 하자.
  2. AL,AL+1,…,ARA_L, A_{L+1}, \dots, A_R에 각각 XX를 더한다.
  3. 값이 바뀐 수열을 다시 오름차순으로 정렬한다.

쿼리를 모두 적용한 뒤의 수열을 출력하라.

입력

첫째 줄에 NN과 KK가 공백으로 구분되어 주어진다. (1≤N≤100 0001 \le N \le 100\,000, 1≤K≤1 0001 \le K \le 1\,000)

둘째 줄에 수열을 이루는 NN개의 정수가 공백으로 구분되어 주어진다. 각 정수의 절댓값은 101810^{18} 이하이다.

셋째 줄부터 KK개의 줄에 쿼리 LL RR XX가 한 줄에 하나씩 주어진다. (1≤L≤R≤N1 \le L \le R \le N, ∣X∣≤109|X| \le 10^9)

출력

쿼리를 모두 적용한 뒤의 수열을 오름차순으로 한 줄에 출력한다. 인접한 두 수 사이에는 공백을 하나만 둔다.

예제7

  1. 예제 1

    입력
    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

  2. 예제 2

    입력
    1 1
-1000000000000000000
1 1 -1000000000
    예상 출력
    -1000000001000000000

  3. 예제 3

    입력
    5 1
5 -3 0 12 -7
2 4 0
    예상 출력
    -7 -3 0 5 12

  4. 예제 4

    입력
    8 2
4 4 4 4 4 4 4 4
1 4 -2
5 8 3
    예상 출력
    2 2 2 2 7 7 7 7

  5. 예제 5

    입력
    6 2
-5 -1 0 3 8 100
1 6 -1000000000
1 6 1000000000
    예상 출력
    -5 -1 0 3 8 100

  6. 예제 6

    입력
    3 1000
1000000000000000000 999999999999999999 999999999999999998
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
1 3 1000000000
    예상 출력
    1000000999999999998 1000000999999999999 1000001000000000000

  7. 예제 7

    입력
    12 10
-5 -1 -14 5 10 -11 -15 -16 -19 5 15 -2
1 4 1
5 7 -7
5 8 -7
11 12 1
4 6 1
5 10 -7
10 11 9
9 10 -1
4 11 1
2 10 1
    예상 출력
    -22 -20 -20 -18 -17 -16 -15 -13 -1 8 17 20