시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB1000.000%

문제

Ant-land continues to expand. The expansion is done in the following way: whenever an ant-town is overpopulated, a number of its residents move out and founds a new town (each time the ants move, there are some that will continue living in the old town). Initially, Ant-land has only a single town. From ancient times, the ants have introduced the rule that in every town there must be exactly M anthills, numbered with the integers from 1 to M, and for each anthill, we know how many ants live inside. When a new town is established, M anthills are built immediately. Because the ants respect their traditions, they have a natural inclination to build the anthills in the new town in a way that resembles the anthills in the town where they just moved out of. That is, anthill 1 in the new town will have the same capacity as anthill 1 in the old town, anthill 2 in the new one – the same capacity as anthill 2 in the old one, etc. On the other hand, there are innovator-ants who want to make some changes in the new town's city plan. The decision, which has been taken is that at the time of the founding of the new town, the ant-chieftains give the order that the capacities of the anthills numbered from L to R, inclusive is going to be increased by the same amount V.

After the anthills in the new town have been built, it turns out that the “prestigious” neighbourhood contains all anthills numbered from i to j, inclusive, and now, the antchieftains wonder how many ants the “prestigious” neighbourhood can accommodate.

Write a program ants that answers this question at the time when new towns are founded.

입력

On the first line of the standard input there are two integers: N – the number of towns in Ant-land after all new towns have been founded, and M – the number of anthills in each town.

On the second line of the standard input, there are M integers: A1, A2, A3, …, AM. Where Ai is the capacity of anthill i in the first town of Ant-land.

On each of the following N-1 lines, there are 6 integers: P, X, Y, V, Z, T, which describe the parameters used at the time when we are creating a new town. P is the index of the town, from which the new town is founded. The index of the initial town is 1. Each newly founded town is assigned an index equal to the smallest positive integer which isn't used as an index for another town that has already been built. The numbers L, R, i, j from the problem statement are generated as follows:

  • L = ((X + S) mod M) + 1; R = ((Y + S) mod M) + 1
  • i = ((Z + S) mod M) + 1; j = ((T + S) mod M) + 1

Where S initially equals 0, and after building a new town, the value of S will be updated to equal the number of ants that can live in the prestigious neighbourhood of the most recently built town, consisting of all anthills with numbers between i and j, inclusive. This value is going to be used when computing the parameters for the creation of the next town (next of the input list). It is guaranteed that L≤R and i≤j for each town.

출력

For every newly founded town output a single integer on a separate line: S – the number of ants that can live in the prestigious neighbourhood of that town.

제한

  • 1 ≤ N, M ≤ 100000
  • 0 ≤ Ai, V ≤ 100000 for each i between 1 and M, and V for each newly-founded town
  • 1 ≤ L ≤ R ≤ M for each newly founded town
  • 1 ≤ i ≤ j ≤ M for each newly founded town
  • 0 ≤ X, Y, Z, T < M

예제 입력 1

4 4
3 6 7 5
1 2 3 1 0 1
2 1 2 6 2 2
1 0 2 8 0 3

예제 출력 1

9
12
45

힌트

After all operations, we will have 4 towns. In each town, we will have 4 anthills. The anthills in town 1 are with capacities {3, 6, 7, 5}. Whenever we create town number 2, S = 0, L = 3, R = 4, V = 1, i = 1, j = 2. The capacities of the anthills in town 2 are {3, 6, 8, 6}, and the number of the ants that can live in the prestigious neighbourhood is 3 + 6 = 9. We set the value S = 9 before founding the new town.

At the time we create town 3, S = 9. Compute L = ((1 + 9) mod 4) + 1, R = 4, i = ((2 + 9) mod 4) + 1 = 4, j = 4 ; V = 6. As town 3 has formed as a result of overpopulating town 2, the ants are attempting to preserve the capacities from town 2 with little changes. The capacities of the anthills in town 3 are {3, 6, 14, 12}. The prestigious neighbourhood is just anthill 4, which has capacity 12. Set S = 12 before moving on to town 4.

Town 4 is formed from overpopulating town 1. With the new value of S (=12), we compute L = 1, R = 3, i = 1, j = 4. V = 8. The capacities are {11, 14, 15, 5}. All anthills are in the prestigious neighbourhoods: 11 + 14 + 15 + 5 = 45.