#P18723. Buy for More, Sell for Less

Buy for More, Sell for Less

Buy for More, Sell for Less

题名没有笔误。

Monocarp 是一个非常奇怪的人:购买物品会让他感到快乐,即使后来卖出的价格低于买入价格。每购买一件物品,他获得 11 单位快乐。

有 nn 种物品,第 ii 种的买入价和卖出价分别为整数 bi,sib_i,s_i,满足 bi>sib_i>s_i。最初 Monocarp 有一定数量的硬币,可以反复执行以下操作:

  • 如果当前至少有 bib_i 枚硬币,可以花费 bib_i 枚硬币购买一件第 ii 种物品。每种物品的库存均为无限。
  • 如果持有至少一件尚未售出的第 ii 种物品,可以卖出其中一件,获得 sis_i 枚硬币。

处理 qq 次独立查询。第 jj 次查询给出初始硬币数 kjk_j,求 Monocarp 最多能获得多少快乐。

输入格式

第一行包含整数 n,qn,q,满足 1≤n≤1041\le n\le10^4、1≤q≤1061\le q\le10^6。

第二行包含 nn 个整数 b1,…,bnb_1,\ldots,b_n,满足 2≤bi≤10142\le b_i\le10^{14}。

第三行包含 nn 个整数 s1,…,sns_1,\ldots,s_n,满足 1≤si<bi1\le s_i<b_i。

第四行包含整数 x,y,zx,y,z,满足 1≤x,y,z≤10141\le x,y,z\le10^{14}。

查询序列按下述方式生成,并非直接写在输入中:

  1. 令 a0=xa_0=x,M=1014+31M=10^{14}+31,对 j>0j>0,令

    aj=(aj−1y+z) mod M.a_j=(a_{j-1}y+z)\bmod M.
  2. 令 c0=0c_0=0,cjc_j 表示第 jj 次查询的正确答案。

  3. 对 j=1,…,qj=1,\ldots,q,令

    kj=(aj+cj−1) mod 1014.k_j=(a_j+c_{j-1})\bmod10^{14}.

因此 kjk_j 可以为 00。每次查询都重新开始,只以上一次查询的答案参与序列生成,不继承上一次查询的硬币或物品。

输出格式

输出一行一个整数:

$$c_1\mathbin\oplus c_2\mathbin\oplus\cdots\mathbin\oplus c_q,$$

其中 ⊕\oplus 表示按位异或。

原样例一

4 6
10 3 6 7
8 1 3 4
2 1 4
7

原样例二

7 10
5 8 11 9 10 12 4
2 6 9 8 1 11 1
13 1234567891011 37
16313242560751

原说明

第一个样例的查询为 6,12,19,27,35,436,12,19,27,35,43,答案分别为 2,5,9,13,17,212,5,9,13,17,21。