Ants

Ant-land keeps expanding, and new towns are founded like this: when a town becomes overcrowded, some of its residents leave and found a new town (some ants always stay behind in the old town). At the very start, Ant-land has just one town.

By ancient tradition, every town must contain exactly $M$ anthills, numbered $1$ through $M$, and each anthill holds a known number of ants. When a new town is founded, all $M$ of its anthills are built at once. Out of respect for tradition, the founders model the new town on the town they left: anthill $k$ in the new town starts with the same capacity as anthill $k$ in the old town, for every $k$.

Some innovator ants, however, tweak the plan. At the moment a new town is founded, the chieftains order that the capacities of anthills $L$ through $R$ (inclusive) each be increased by the same amount $V$.

Once the new town's anthills are built, its prestigious quarter turns out to consist of all anthills numbered $i$ through $j$ (inclusive), and the chieftains ask: how many ants can the prestigious quarter hold in total?

Write a program that answers this question every time a new town is founded.

The first line contains two integers $N$ and $M$: $N$ is the total number of towns in Ant-land after every new town has been founded, and $M$ is the number of anthills in each town.

The second line contains $M$ integers $A_1, A_2, \ldots, A_M$, where $A_i$ is the capacity of anthill $i$ in the first town.

Each of the next $N-1$ lines describes the founding of one new town with six integers $P, X, Y, V, Z, T$:

• $P$ is the index of the town the new town is founded from. The first town has index $1$. Each newly founded town receives the smallest positive integer not yet used as a town index (so towns are indexed $2, 3, \ldots, N$ in the order they are founded).
• The values $L, R, i, j$ are derived from a running value $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$ starts at $0$. After a new town is founded, $S$ is set to that town's answer (the total capacity of its prestigious quarter, anthills $i$ through $j$), and this updated $S$ is used when deriving the parameters of the next founding. It is guaranteed that $L \le R$ and $i \le j$ for every town.

For each newly founded town, print a single integer on its own line: the total number of ants its prestigious quarter can hold.

• $1 \le N, M \le 100000$
• $0 \le A_i \le 100000$ for every $i$, and $0 \le V \le 100000$ for every founding
• $1 \le L \le R \le M$ for every newly founded town
• $1 \le i \le j \le M$ for every newly founded town
• $0 \le X, Y, Z, T < M$

Worked example (this matches the first sample). Town $1$ has capacities $\{3, 6, 7, 5\}$.

• Town 2, founded from town $1$: $S = 0$, so $L = 3, R = 4, V = 1, i = 1, j = 2$. Adding $1$ to anthills $3$–$4$ gives $\{3, 6, 8, 6\}$. The prestigious quarter (anthills $1$–$2$) holds $3 + 6 = 9$, so the answer is $9$ and $S$ becomes $9$.
• Town 3, founded from town $2$: with $S = 9$, $L = ((1+9) \bmod 4)+1 = 3, R = 4, i = ((2+9) \bmod 4)+1 = 4, j = 4, V = 6$. Starting from town $2$'s $\{3, 6, 8, 6\}$ and adding $6$ to anthills $3$–$4$ gives $\{3, 6, 14, 12\}$. The prestigious quarter (anthill $4$) holds $12$, so the answer is $12$ and $S$ becomes $12$.
• Town 4, founded from town $1$: with $S = 12$, $L = 1, R = 3, i = 1, j = 4, V = 8$. Starting from town $1$'s $\{3, 6, 7, 5\}$ and adding $8$ to anthills $1$–$3$ gives $\{11, 14, 15, 5\}$. The prestigious quarter (anthills $1$–$4$) holds $11 + 14 + 15 + 5 = 45$, so the answer is $45$.

Each new town is an independent copy of the town it was founded from, so a founding never changes the capacities of any earlier town.