题目背景

A 教练负责一所学校的竞赛训练。学生按照到场顺序进入机房，A 教练为每名学生记录了一个能力值区间。

为了便于统一安排训练，A 教练希望把已经到场的学生分成若干个连续小组。如果分组到最后剩下不足一个正式训练组的学生，他们仍要参加训练，但需要由教练单独指导。学生们一个接一个到场，每来一名学生，A 教练都需要重新评估当前在场学生的分组方案。不过，每次重新评估都很费时。A 教练想到了擅长解决 CSP-S 题的你，希望你编写一个程序，自动完成这项工作。

题目描述

给定四个整数 n,k,B,\mathit{type}，其中 n,k 为正整数，n 为学生总数，k 为正式训练组的人数下限，B 为非负整数，表示教练辅导组额外增加的管理难度，\mathit{type}\in{0,1} 表示输入数据的生成方式。学生按到场顺序编号为 1,2,\ldots,n；每名学生的能力值区间 [L_i,R_i] 按“强制在线”一节中的规则确定。

对于每个 i\ge k，考虑前 i 名学生。将前 i 名学生划分为若干个连续小组的分组方案满足：

G_1=[l_1,r_1],\ G_2=[l_2,r_2],\ \ldots,\ G_m=[l_m,r_m],

其中

j+1=l{j+1}\quad(1\le j<m). $$

也就是说，每名学生恰好属于一个小组，所有小组互不重叠，并且覆盖第 1 名至第 i 名学生。

除最后一组外，每个小组至少包含 k 名学生。最后一组有两种情况：

• 若最后一组至少包含 k 名学生，则它是正式训练组；
• 若最后一组包含少于 k 名学生，则它是教练辅导组。教练辅导组仍然属于分组方案，但教练需要对其中的学生逐一检查训练进度并答疑，因此该组的管理难度需要额外加上 B。

例如，当 i=10、k=3 时：

• [1,3],[4,7],[8,10] 的人数为 3,4,3，合法；
• [1,4],[5,9],[10,10] 的人数为 4,5,1，合法，最后一组是教练辅导组；
• [1,5],[6,10] 的人数为 5,5，合法；
• [1,3],[4,5],[6,10] 不合法，因为中间一组只有 2 名学生，少于 k。

对于前 i 名学生的分组方案，小组 [l,r] 的管理难度定义为

$$

\operatorname{cost}_i(l,r)

\begin{cases} \displaystyle\max_{l\le t\le r}Rt-\min{l\le t\le r}Lt+(r-l+1)+B, & r=i\ \text{且}\ r-l+1<k,\[8pt] \displaystyle\max{l\le t\le r}Rt-\min{l\le t\le r}L_t+(r-l+1), & \text{其他情况}. \end{cases} $$

其中，第一项 $\max_{l\le t\le r}Rt-\min{l\le t\le r}L_t 是两个极值之差，第二项 r-l+1 是小组人数；如果该小组是最后一组且人数少于 k，还需额外加上 B$。

一个分组方案的难度定义为其中所有小组管理难度的最大值。记前 i 名学生能够达到的最小分组方案难度为 c_i，即

$$

c_i

\min{\mathcal P} \ \max{[l,r]\in\mathcal P} \operatorname{cost}_i(l,r), $$

其中 \mathcal P 遍历前 i 名学生的所有合法分组方案。

题目要求输出最终的最小分组方案难度 c_n，以及用于校验的滚动哈希值。

令 h_0=0。按 i=1,2,\ldots,n 的顺序计算

$$ hi=(10007h{i-1}+c_i)\bmod 2^{64}. $$

其中 c_i 是前文定义的前 i 名学生的最小分组方案难度；当 i 时，按照题意取 c_i=0。最终输出 c_n 和 h_n。

强制在线

本题强制在线。每一步得到第 i 名学生的能力值区间时，都必须使用已经确定的 c_{i-1}。

规定 $c0=0。按 i=1,2,\ldots,n 的顺序读入数据，并使用已经确定的 c{i-1} 解码第 i$ 名学生的能力区间：

当 \mathit{type}=0 时，输入中的两个编码值为 u_i,v_i，并规定

$$ L_i=ui\mathbin{\operatorname{xor}}(c{i-1}+i), \qquad R_i=vi\mathbin{\operatorname{xor}}(c{i-1}+i). $$

其中，c_{i-1}+i 先进行普通整数加法，再与 u_i 或 v_i 进行按位异或。保证解码后始终有 L_i\le R_i。

当 \mathit{type}=1 时，输入给出五个整数 x,y,z,b_1,b_2。令

$$ bt=(x b{t-1}+y b_{t-2}+z)\bmod 2^{30}\quad(t\ge3). $$

对每个 i，令

$$ di=c{i-1}+i, $$

$$ pi=(b{2i-1}\mathbin{\operatorname{xor}}d_i)\bmod 10^9,\qquad qi=(b{2i}\mathbin{\operatorname{xor}}d_i)\bmod 10^9, $$

并规定

L_i=1+\min(p_i,q_i),\qquad R_i=1+\max(p_i,q_i).

当 i 时，规定 c_i=0；这些规定值仍用于后续数据的解码。当 i\ge k 时，c_i 按前述定义确定，并用于解码下一名学生的数据。

从文件 training.in 中读入数据。

第一行包含四个整数 n,k,B,\mathit{type}。

当 \mathit{type}=0 时，接下来 n 行输入，每行包含两个整数 u_i,v_i，表示第 i 名学生数据的编码值。

当 \mathit{type}=1 时，接下来一行包含五个整数 x,y,z,b_1,b_2，用于按“强制在线”一节的递推式生成数据。

输出到文件 training.out。

输出一行，包含两个整数 c_n 和 h_n，以空格分隔。

样例说明

解码后五名学生的能力值区间依次为

[1,2],\ [2,3],\ [3,4],\ [4,5],\ [4,5].

前 3 名学生只能组成一个正式训练组。该组的两个极值之差为 4-1=3，包含 3 名学生，所以管理难度为

3+3=6.

因此 c_3=6，这一步的结果会参与下一名学生数据的解码。

前 4 名学生可以分为 [1,3] 和 [4,4] 两组。第一组的管理难度为 6；第二组是教练辅导组，其两个极值之差为 5-4=1，包含 1 名学生，增加 B=4 后的管理难度为 1+1+4=6。因此 c_4=6，并参与下一名学生数据的解码。

前 5 名学生可以分为 [1,3] 和 [4,5] 两组。第二组的两个极值之差为 5-4=1，包含 2 名学生，增加 B=4 后的管理难度为 1+2+4=7，因此最终答案 c_5=7。

附加样例

本题另提供 4 组附加样例，见附件 training.zip。输入文件为 training2.in 至 training5.in，输出文件为对应的 .out 文件。

数据范围与测试点

对于按上述规则解码得到的 L_i,R_i，所有数据均保证：

• 1\le k\le n\le5\times10^6；
• \mathit{type}\in{0,1}；
• 1\le L_i\le R_i\le10^9；
• 0\le B\le2\times10^9；
• 当 \mathit{type}=0 时，输入中的编码值满足 0\le u_i,v_i<2^{30}；
• 当 \mathit{type}=1 时，输入中的 x,y,z,b_1,b_2 均满足 0\le x,y,z,b_1,b_2<2^{30}。

本题共 20 个测试点，每个测试点 5 分，各测试点独立计分。

表中涉及的 L_i,R_i 均指按题意解码后的数值。