题目描述
有n+1个箱子从左往右排成一行，编号从0至n 。一开始你在第0个箱子，你的目标是到达第n个箱子。你可以通过跳跃来完成目标，每一步你的跳跃距离不能超过L，你可以选择向左跳，也可以选择向右跳，你任何时刻都不能跳出边界。每当你落在第i个箱子上面，你会受到T[i]点伤害值。求为了完成任务，至少会受到多少伤害值。伤害值用如下的公式产生：
T[0] = 0
state = seed
for i = 1 to N:
state = (state * 1103515245 + 12345) % 2^31
T[i] = 1 + (state % M)
输入
多组测试数据。
第一行，一个整数G,表示有G组测试数。1<=G<=3。
每组测试数据格式如下：
一行，4个整数：n, L, seed,M。
1<=n<=500000，1<=L<=500000，0<=seed<2^31， 1<=M<=10^9。
输出
共G行，每行一个整数。
样例输入输出
输入#1
复制
3
8 3 47 10
100 1 47 123456789
5 5 12345 54321
输出#1
复制
17
5835166389
46038
提示