\(\texttt{Printed Circuit Board}\) （简称 \(\texttt{PCB}\) ），印刷电路板，他可以固定各种电子元器件，然后将它们连接起来，是的整个系统能够实现我们所需要的功能。因此，“焊板子”是一个很多工科学生（尤其是电子、自动化系的同学）都需要掌握的技能。

现代电路板多用印刷技术制成。印刷线路板的最大特点是装配的原件紧凑、美观，并且适合于工厂的大规模生产。当然也适合各种电子小制作。这种线路板的基板是矩形的，用环氧板或纸质板制成。在基板上面用热压工艺贴上一层很薄的铜箔。用印刷法把电路印在铜箔上，再用腐蚀法把不需要的铜箔去掉，留下的铜箔便构成电路，最后钻上小孔，涂上助焊保护剂，电路板便制成了。

由于技术限制，电路板上的铜线的宽度是确定的，并且铜线必须平行于电路板的边界（也就是说铜线必须平行于坐标轴）。

例如以上两幅图都是可行的电路板。

现在 \(\mathbf{R}\) 同学需要制作很多很多电路板，每个电路板上有若干个电子元件。他需要合理布置电路是的铜箔将所有电子元件都连通，并且消耗的铜最少。

第一行输入两个正整数 \(T,n\) ，表示 \(\mathbf{R}\) 同学需要制作的电路板数量和每块电路板上的电子元件数。

由于输入数据规模庞大，因此采用输入种子后随即生成的方式。

第二行输入 \(6\) 个正整数 \(a,c,M_x,M_y,seed_x,seed_y\) ，以及一个字符 \(datatype\) ，并按照以下方式生成序列 \(X_i,Y_i\) ：

若 \(datatype\) 为 \(\texttt{A}\) ，则第 \(i(0\leq i\lt T)\) 组数据中的 \(n\) 个电子元件的坐标：

若 \(datatype\) 为 \(\texttt{B}\) ，则第 \(i(0\leq i\lt T)\) 组数据中的 \(n\) 个电子元件的坐标（即前三个点的横纵坐标分别加上 \(M_x\) 和 \(M_y\) ）：

每组数据输出一行，仅包含一个数，表示最短的铜线长度。

样例解释

样例1：
case0: \((5,3) (6,0) (4,9)\)
case1: \((2,1) (1,4) (2,0)\)
case2: \((1,3) (0,7) (3,1)\)

样例2的前三个数据分别为：
case0: \((0,3) (0,0) (1,1) (4,4) (0,1)\)
case1: \((3,1) (2,3) (2,4) (4,3) (1,0)\)
case2: \((3,2) (2,1) (0,2) (0,4) (3,1)\)

数据范围

对于 \(100\%\) 的数据 \(n\leq 7\) ， \(T\leq 10^6\) ， \(a,c,seed_x,seed_y\leq 2^{31}-1\) ， \(M_x,M_y\leq 2^{16}\) 。

小贴士

为了方便大家编写程序，在这里提供一个上述的数据生成的代码，仅供大家参考（不必以此为模板）。

对于 \(\texttt{C/C++}\) 语言：

int X[7000010], Y[7000010];
int n, T, a, c, Mx, My;
long long seedx, seedy;
char datatype[4];

//生成数据，并将其对Mx,My取模后的值保存在X,Y这两个数组中
void createList() {
    int i, AD = (1 << 16) - 1;
    for (i = 0; i < n * T; i ++){
        X[i] = seedx % Mx;
        Y[i] = seedy % My;
        if (i % n < 3 && datatype[0] == 'B')
            X[i] += Mx, Y[i] += My;
        seedx = (((a * seedx + c) >> 16) & AD);
        seedy = (((a * seedy + c) >> 16) & AD);
    }
}
int main() {
    scanf("%d%d%d%d%d%d%lld%lld%s", &T, &n, &a, &c, &Mx, &My, &seedx, &seedy, datatype);
    createList();
    
    //你的计算代码
    
    return 0;
}

对于 \(\texttt{Pascal}\) 语言：

var
    ax,ay: array[0..7000000] of longint;
    n,T,a,c,Mx,My: longint;
    seedx,seedy: int64;
    datatype: char;
    i,j: longint;

//生成数据，并将其对Mx,My取模后的值保存在ax,ay这两个数组中
procedure createList;
var
    AD,i: longint;
begin
    AD := (1 shl 16) - 1;
    for i:= 0 to n * T - 1 do
    begin
        ax[i] := seedx mod Mx;
        ay[i] := seedy mod My;
        if ((i mod n < 3) and (datatype = 'B')) then
        begin
            ax[i] := ax[i] + Mx;
            ay[i] := ay[i] + My;
        end;
        seedx := (((a * seedx + c) shr 16) and AD);
        seedy := (((a * seedy + c) shr 16) and AD);
    end;
end;

begin
    read(T,n,a,c,Mx,My,seedx,seedy);
    read(datatype);
    while (datatype = ' ') do 
        read(datatype);
    createList;
    
    //你的计算代码
    
end.