33583번 - 수열과 띄엄띄엄 쿼리

문제

진우는 무언가를 띄엄띄엄 하는 것을 좋아한다. 그래서 연속된 구간에 다음과 같이 띄엄띄엄 쿼리를 처리한다.

• 1 l r d x: $A_l,,円 A_{l+d},,円 A_{l+2d},,円 \cdots,,円 A_r$에 각각 $x$를 더한다. $(-10^9\leq x\leq 10^9, 1\leq l\leq r\leq N,1\leq d\leq 6,(r-l)$는 $d$의 배수$)$
• 2 l r d: $A_l + A_{l+d} + A_{l+2d} + \cdots + A_r$의 값을 출력한다. $(1\leq l\leq r\leq N,1\leq d\leq 6, (r-l)$는 $d$의 배수$)$

쿼리를 보고도 수행을 미루고 있는 진우 대신 위 쿼리를 수행하는 프로그램을 작성하시오.

입력

첫 번째 줄에 배열의 길이 $N$과 쿼리의 개수 $Q$가 공백으로 구분하여 주어진다. $(1\leq N\leq 10^5, 1\leq Q\leq 50,000円)$

두 번째 줄에 $A_1, A_2, \cdots ,A_N$이 공백으로 구분하여 주어진다. $(-10^9\leq A_1,A_2,\cdots,A_N\leq 10^9)$

세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

출력

첫 번째 줄부터 2ドル$번 쿼리가 주어질 때마다 정답을 한 줄에 하나씩 순서대로 출력한다. 2ドル$번 쿼리는 적어도 한 번 이상 주어진다.

제한

힌트