수열에 구간 덧셈, 구간 d로 나눈 몫으로 치환을 적용하고 구간 최솟값과 구간 합을 구한다.
길이가 nnn인 수열 A0,A1,…,An−1A_0, A_1, \dots, A_{n-1}A0,A1,…,An−1이 있다. 다음 네 가지 쿼리를 처리하는 프로그램을 작성하시오.
1 l r c
2 l r d
3 l r
4 l r
⌊x⌋\lfloor x \rfloor⌊x⌋는 xxx 이하의 정수 중 가장 큰 값이다. 예를 들어 ⌊−2.5⌋=−3\lfloor -2.5 \rfloor = -3⌊−2.5⌋=−3이고, ⌊−7⌋=−7\lfloor -7 \rfloor = -7⌊−7⌋=−7이다.
첫째 줄에 수열의 크기 nnn과 쿼리의 개수 qqq가 주어진다. (1≤n,q≤100 0001 \le n, q \le 100\,0001≤n,q≤100000)
둘째 줄에 A0,A1,…,An−1A_0, A_1, \dots, A_{n-1}A0,A1,…,An−1이 주어진다. (−109≤Ai≤109-10^9 \le A_i \le 10^9−109≤Ai≤109)
다음 qqq개 줄에 쿼리가 한 줄에 하나씩 주어진다. (0≤l≤r≤n−10 \le l \le r \le n-10≤l≤r≤n−1, −104≤c≤104-10^4 \le c \le 10^4−104≤c≤104, 2≤d≤1092 \le d \le 10^92≤d≤109)
3번 쿼리와 4번 쿼리가 주어질 때마다 답을 한 줄에 하나씩 출력한다.
cho.shcho.sh