SDGAME - Super Dice Game

Alice and Bob are playing a game. The game consists of a circular track of M (2 <= M <= 1,000,000,000) cells labeled 0 through M - 1. Initially both players start at cell 0. The game progresses by having each player take turns rolling one of N (1 <= N <= 10,000) 'super-dice' labeled 0 through N - 1. The actual mechanics of the 'super-dice' is not very well understood; however, it is known that they will only ever turn up a number between 0 and 1,000,000,000 inclusive after a roll. After rolling the super-dice the number of spaces a player moves is determined by the product of a contiguous subsequence of the values shown on the dice (There are special rules for determining the range that vary each move that will not be discussed).

To make matters more complicated, after any turn if Alice and Bob land on the same cell the value shown on all dice is multiplied by the label of the cell they are on. Note in this way it is possible for some dice to show numbers greater than 1,000,000,000. This multiplier does not apply to future rolls.

After playing this game for a while, Alice and Bob have grown frustrated because the calculations became too difficult. Given the series of R (1 <= R <= 100,000) dice rolls and ranges, help Alice and Bob determine their position after each move. Assume that all dice start out showing 1.

Input

The first line contains R, N, and M each separated by a space. R lines follow. Each line will contain d v a b separated by a space. d indicates the label of the dice rolled. v indicates the value shown on the dice. a and b indicate the range of dice used to determine the move distance.

Output

R lines containing the position of the player that just rolled after their roll.

Example

Input:
6 4 20
1 5 1 1
3 10 2 3
2 3 0 3
1 2 0 3
1 5 1 2
0 7 0 1

Output:
5
10
15
10
10
0

Output Explanation

For your assistance, here is the state of the dice after each turn:

  • [1, 5, 1, 1]
  • [1, 5, 1, 10]
  • [1, 5, 3, 10]
  • [1, 2, 3, 10]
  • [10, 50, 30, 100]
  • [7, 50, 30, 100]
Warning: large Input/Output data, be careful with certain languages

Added by:Mark Gordon
Date:2008-07-05
Time limit:1s-1.282s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:own problem

hide comments
2012-07-14 16:49:52 Brian Curcio
Can someone with accepted solution clarify ambiguous parts of statement?
2012-04-23 11:02:14 Brian Curcio
I still don't understand this sentence:

Note in this way it is possible for some dice to show numbers greater than 1,000,000,000. This multiplier does not apply to future rolls.

It doesn't apply to any die or just the one that has value over 10^9?
2011-10-08 11:57:14 Brian Curcio
Thanks, I wasn't aware of SDGAME2, with some changes I managed to get AC for that problem.For this problem, at least I'm more confident that my solution is well implemented, unfortunately it's not the solution for this problem. But I'm more confused now, I'm not sure if in this problem the 'multiplier' is refering to the dice, or to what happens when they land on the same cell, I get WA in 7 seconds if I interpret it as the multiplication by the cell they're on, does this imply that some cases are working on that assumption? Even after knowing what it's refering, all the other quesions in my other comment are still possible interpretations
2011-10-08 07:24:14 :D
Those two sentences are not directly related. First means that the 10^9 limit does not apply when the multiplication takes place. Second sentence is somewhat unclear and that's inspired SDGAME2 problem. I didn't solve it yet, but the example suggests that new dice values are preserved, but when you make a roll you don't multiply it afterwards.
2011-10-07 19:59:08 Brian Curcio
I don't understand this phrase: ' Note in this way it is possible for some dice to show numbers greater than 1,000,000,000. This multiplier does not apply to future rolls.' Does this mean that if some dice shows over 10^9 then this multiplier won't work for any dice for the rest of the game? Or does it mean that dice with value over 10^9 don't get multiplied for the rest of the game? Or does it mean while theres a number over 10^9, this multiplier won't count? Or does it mean that only dice with numbers less than 10^9 get multiplied?

Last edit: 2011-10-07 20:27:55
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.