题目描述

小 R 要去北京参加比赛。有 $n$ 个城市，北京是 $n$ 号城市。 对于所有 $1\le i\le n-1$，都有参数 $T_i$ 表示从 $i$ 号城市出发，坐大巴可以到达 $[i+1,i+T_i]$ 号城市。 给定正整数 $K$ 和非负整数 $D$。如果从 $i$ 坐大巴到 $j$，小 R 的疲劳程度会增加： $$ \left \lfloor \frac{j-i}{K} \right \rfloor \cdot D $$ 第 $i$ 个城市有风景值 $H_i$，可能为负数。小 R 的快乐度为：所有经过城市的风景值之和 - 总疲劳程度。 你不知道小 R 的位置，因此你需要对于每个 $p$ 求出小 R 从 $p$ 出发到北京的最大的快乐度。

输入格式

第一行三个整数 $n,K,D$。 第二行 $n$ 个整数 $H_1,H_2,H_3,...,H_n$。 第三行 $n-1$ 个整数 $T_1,T_2,...,T_{n-1}$。请使用下面提供的快读板子。

输出格式

设 $p=i$ 的答案为 $f_i$，你需要输出 $f_i+i$ 的异或和。

样例

6 2 1
8 -7 -8 9 0 2
5 3 3 2 1

16

数据范围

Subtask #1 (20 分)：$n\le 3000$ 。

Subtask #2 (10 分)：$n\le 2\times 10^5$ ，$H_i$ 在范围内均匀随机。

Subtask #3 (10 分)：$n\le 2\times 10^5$ ，$K=1$ 。

Subtask #4 (10 分)：$n\le 2\times 10^5$ ，$K=n$ 。

Subtask #5 (40 分)：$n\le 2\times 10^5$ 。

Subtask #6 (10 分)：无特殊限制。

对于所有数据，$1\le K\le n\le 2\times 10^6,0\le D,|H_i|\le 10^{10}$。

提示

请优化代码常数。

快读板子

typedef long long ll; 
#define T (1<<15)
char buf[T],*p1=buf,*p2=buf;
#define nc() (p1==p2&&(p2=buf+fread(p1=buf,1,T,stdin),p1==p2)?-1:*p1++)
ll rd(){ 
    ll x=0;char c;bool s=0; 
    do c=nc();while(c!=45&&(c<48||c>57)); 
    if(c==45)c=nc(),s=1; 
    do x=10*x+(c&15),c=nc();while(c>=48&&c<=57); 
    return s?-x:x; 
}
#undef T