[Lydsy2017年4月月赛]LRU算法

时间限制:6s      空间限制:128MB

题目描述

小Q同学在学习操作系统中内存管理的一种页面置换算法,LRU(LeastRecentlyUsed)算法。
为了帮助小Q同学理解这种算法,你需要在这道题中实现这种算法,接下来简要地介绍这种算法的原理:
1.初始化时,你有一个最大长度为n的空队列,用于暂时存储一些页面的地址。
2.当系统需要加载一个不在队列中的页面时,如果队列已满,则弹出队首元素,并将需要加载的页面加到队尾,
否则直接将需要加载的页面加到队尾。
3.当系统需要加载一个在队列中的页面时,将该页面移至队尾。
在这道题中,小Q同学需要处理有q个请求,每个请求会给定一个整数x,表示系统需要加载地址为x的页面,
而你需要在每个请求完成后给出整个队列中页面的地址之和。为了便于计算,设第i个请求给出的整数为x_i,
第i个请求后你给出的答案为y_i,则对于1<i≤q有x_i=(A*x_(i-1)+B)modp,其中x_1,A,B,p是给
定的整数,并且你只需要输出sigma(i*y_i),1<=i<=Q对2^64取模的值,而不是每个y_i。


输入格式

第一行包含一个正整数T,表示有T组数据,满足T≤20。
接下来依次给出每组测试数据。对于每组测试数据:
第一行包含两个正整数n和q,满足1≤n≤10^5,1≤q≤10^6。
第二行包含四个整数x_1,A,B和p,满足0≤x_1,A,B<p,1≤p≤10^6+3。


输出格式

 对于每组测试数据,输出一行一个非负整数,表示这组数据的答案。


样例输入

2
5 10
0 1 1 5
5 10
0 1 1 10

样例输出

485
1135

提示

没有写明提示


题目来源

鸣谢Tangjz提供试题

Menuappsclose