개미 나라

개미 나라는 계속 확장된다. 새로운 마을은 다음과 같이 세워진다. 어떤 마을이 너무 붐비면 주민 일부가 떠나 새 마을을 세운다(떠날 때 항상 일부 개미는 원래 마을에 남는다). 처음에 개미 나라에는 마을이 단 하나뿐이다.

오래된 전통에 따라 모든 마을에는 정확히 $M$개의 개미굴이 있어야 하며, 개미굴에는 $1$부터 $M$까지 번호가 매겨져 있고 각 개미굴에 사는 개미 수(수용량)를 알고 있다. 새 마을이 세워질 때 $M$개의 개미굴이 한꺼번에 만들어진다. 전통을 존중하기에, 새 마을은 자신이 떠나온 마을을 본떠 만들어진다. 즉 모든 $k$에 대해 새 마을의 $k$번 개미굴은 원래 마을의 $k$번 개미굴과 같은 수용량으로 시작한다.

한편 혁신을 좋아하는 개미들은 설계를 조금 바꾼다. 새 마을이 세워지는 순간, 촌장들은 $L$번부터 $R$번까지(양 끝 포함)의 개미굴 수용량을 각각 같은 값 $V$만큼 늘리라고 지시한다.

새 마을의 개미굴이 모두 만들어지고 나면, 그 마을의 명예 구역은 $i$번부터 $j$번까지(양 끝 포함)의 개미굴로 이루어진다. 촌장들은 이 명예 구역이 총 몇 마리의 개미를 수용할 수 있는지 궁금해한다.

새 마을이 세워질 때마다 이 질문에 답하는 프로그램을 작성하라.

첫째 줄에 두 정수 $N$과 $M$이 주어진다. $N$은 모든 새 마을이 세워진 뒤 개미 나라에 있는 마을의 총 개수이고, $M$은 각 마을의 개미굴 개수이다.

둘째 줄에 $M$개의 정수 $A_1, A_2, \ldots, A_M$이 주어진다. $A_i$는 첫 번째 마을의 $i$번 개미굴의 수용량이다.

이어지는 $N-1$개의 줄에는 각각 새 마을 하나가 세워지는 과정을 나타내는 여섯 정수 $P, X, Y, V, Z, T$가 주어진다.

• $P$는 새 마을을 세울 기준이 되는 마을의 번호이다. 첫 번째 마을의 번호는 $1$이다. 새로 세워지는 마을은 아직 마을 번호로 쓰이지 않은 가장 작은 양의 정수를 번호로 받는다(따라서 마을은 세워지는 순서대로 $2, 3, \ldots, N$번이 된다).
• 값 $L, R, i, j$는 갱신되는 값 $S$로부터 다음과 같이 계산된다.
  • $L = ((X + S) \bmod M) + 1$
  • $R = ((Y + S) \bmod M) + 1$
  • $i = ((Z + S) \bmod M) + 1$
  • $j = ((T + S) \bmod M) + 1$

$S$는 $0$에서 시작한다. 새 마을이 세워지면 $S$는 그 마을의 답(명예 구역, 즉 $i$번부터 $j$번까지 개미굴의 총 수용량)으로 갱신되고, 이 갱신된 $S$가 다음 마을의 매개변수를 계산하는 데 쓰인다. 모든 마을에 대해 $L \le R$이고 $i \le j$임이 보장된다.

새로 세워지는 각 마을에 대해, 그 마을의 명예 구역이 수용할 수 있는 개미의 총 수를 한 줄에 하나씩 정수로 출력한다.

• $1 \le N, M \le 100000$
• 모든 $i$에 대해 $0 \le A_i \le 100000$, 그리고 모든 마을 건설에 대해 $0 \le V \le 100000$
• 새로 세워지는 모든 마을에 대해 $1 \le L \le R \le M$
• 새로 세워지는 모든 마을에 대해 $1 \le i \le j \le M$
• $0 \le X, Y, Z, T < M$

풀이 예시(첫 번째 예제와 일치한다). 마을 $1$의 수용량은 $\{3, 6, 7, 5\}$이다.

• 마을 $1$에서 세운 마을 2: $S = 0$이므로 $L = 3, R = 4, V = 1, i = 1, j = 2$. 개미굴 $3$–$4$에 $1$을 더하면 $\{3, 6, 8, 6\}$이 된다. 명예 구역(개미굴 $1$–$2$)의 수용량은 $3 + 6 = 9$이므로 답은 $9$이고 $S$는 $9$가 된다.
• 마을 $2$에서 세운 마을 3: $S = 9$이므로 $L = ((1+9) \bmod 4)+1 = 3, R = 4, i = ((2+9) \bmod 4)+1 = 4, j = 4, V = 6$. 마을 $2$의 $\{3, 6, 8, 6\}$에서 개미굴 $3$–$4$에 $6$을 더하면 $\{3, 6, 14, 12\}$가 된다. 명예 구역(개미굴 $4$)의 수용량은 $12$이므로 답은 $12$이고 $S$는 $12$가 된다.
• 마을 $1$에서 세운 마을 4: $S = 12$이므로 $L = 1, R = 3, i = 1, j = 4, V = 8$. 마을 $1$의 $\{3, 6, 7, 5\}$에서 개미굴 $1$–$3$에 $8$을 더하면 $\{11, 14, 15, 5\}$가 된다. 명예 구역(개미굴 $1$–$4$)의 수용량은 $11 + 14 + 15 + 5 = 45$이므로 답은 $45$이다.

각 새 마을은 세울 기준이 된 마을의 독립적인 복사본이므로, 한 마을을 세우는 일이 이전 마을들의 수용량을 바꾸지 않는다.