题目描述

小 Q 同学在学习操作系统中内存管理的一种页面置换算法，LRU(LeastRecentlyUsed) 算法。

为了帮助小 Q 同学理解这种算法，你需要在这道题中实现这种算法，接下来简要地介绍这种算法的原理：

1. 初始化时，你有一个最大长度为 $n$ 的空队列，用于暂时存储一些页面的地址。
2. 当系统需要加载一个不在队列中的页面时，如果队列已满，则弹出队首元素，并将需要加载的页面加到队 尾，否则直接将需要加载的页面加到队尾。
3. 当系统需要加载一个在队列中的页面时，将该页面移至队尾。

在这道题中，小 Q 同学需要处理有 $q$ 个请求，每个请求会给定一个整数 $x$，表示系统需要加载地址为 $x$ 的页面，而你需要在每个请求完成后给出整个队列中页面的地址之和。为了便于计算，设第 $i$ 个请求给出的整数为 $x_i$，第 $i$ 个请求后你给出的答案为 $y_i$，则对于 $1<i\le q$ 有 $x_i=(A\times x_{i-1}+B)\bmod p$，其中 $x_1,A,B,p$ 是给定的整数，并且你只需要输出 $\sum\limits_{i=1}^q i\times y_i$, 对 $2^{64}$ 取模的值，而不是每个 $y_i$。

输入格式

第一行包含一个正整数 $T$，表示有 $T$ 组数据。 接下来依次给出每组测试数据。对于每组测试数据： 第一行包含两个正整数 $n$ 和 $q$ 。 第二行包含四个整数 $x_1,A,B,p$。

输出格式

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

样例输入

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

样例输出

485
1135

数据范围与约定

对于 $100\%$ 的数据，$1\le n \le 10^5$，$1\le q\le 10^6$，$T\le 20$，$0\le x_1,A,B<p$，$1\le p\le 10^6+3$。

题目来源

鸣谢Tangjz提供试题