U210430 605菜市场

神仙 $Rings$ 和 $YCX$ 在出题，考虑到这不是 $CTT$ 模拟赛，这场比赛不能出太难，但是他们都不愿出太简单的题，于是他们来到了 $605$ 菜市场，发现这里正在白菜价出售一种名为 $Cyber \_Tree$ 的菜鸡（菜鸡也是菜），于是两人商议让 $Cyber \_Tree$ 来出一道水题。 于是便有了这题。 $Cyber \_Tree$ 出这题用了 $3h \ 59min$ ,由于 $YCX$ 还要赶着去见他的妹妹需要 $59s$，所以你只有 $1s$ 的时间解决这道题。

$YCX$ 和他的妹妹都住在 $WC$ 路上，$WC$ 路上有 $n + 1$ 个路口，编号从 $0$ 到 $n$， 从第 $i - 1$ 个路口到第 $i$ 个路口所需的时间为 $d_i$。 $WC$ 路上每个路口都有红绿灯，且所有的红绿灯都是同步的，且呈周期性变化。具体的，初始时为绿灯，从 $0$ 时刻开始，每过 $g$ 单位时间，路上的所有灯会由绿变红，再过 $r$ 单位时间，路上所有的灯会由红变绿，特别的，在第 $g$ 时刻，所有灯都为红灯，在第 $r + g$ 时刻，所有灯都为绿灯。若你在某个路口且当前为红灯，则你不能前往下一个路口。 现在 $YCX$ 要去找妹妹玩啦！！！ 然而他们两人并不在同一个路口，$YCX$ 在编号为 $l$ 的路口，而妹妹在编号为 $r$ 的路口，现在 $YCX$ 从第 $t$ 时刻出发，$YCX$ 想知道他会在哪一时刻到达（你显然不需要在第 $l$ 和第 $r$ 个路口等红灯）。 由于 $YCX$ 时常会去找妹妹玩耍，所以他一共会抛给你 $q$ 个询问。

第一行四个数，$n, q, g, r, op$ ； 接下来一行 $n$ 个数，其中第 $i$ 个数表示 $d_i$ ； 接下来一行一个数 $q$ ，表示询问次数 ； 接下来 $q$ 行，每行三个数 $t, L, R$ ，表示一次询问，其中 $l, r$ 是被加密的，记 $lst$ 为上次询问的答案（初始为 $0$ )，则这次询问中： $l = (L \oplus (lst * op)) \% (n + 1),r = (R \oplus (lst * op)) \% (n + 1)$ 。 若解密后 $l > r$ ， 则交换 $l, r$ 。

共 $q$ 行，每行一个数，表示这次询问的答案。

#### 样例解释 绿灯时间为 ： $[0, 3), [5, 8), [10, 13), ...$ 。 红灯时间为 ： $[3, 5), [8, 10), [13, 15), ...$ 。 第 $1, 2, 5$ 个询问， $YCX$ 途中不会遇到红灯，路上所用时间为 $7$ ，分别在第 $8, 9, 12$ 时刻到达 $2$ 号路口； 第 $3, 4$ 个询问， $YCX$ 到达第一个路口的时间位于 $[8, 10)$ ，需要等到第 $10$ 时刻才能出发，在第 $12$ 时刻到达 $2$ 号路口。 #### 数据范围 对于 $20 \%$ 的数据， $1 \le n, q \le 3000$ ； 对于另外 $30 \%$ 的数据，$op = 0, l = 0, r = n$ ； 对于另外 $20 \%$ 的数据，$op = 0$ ; 对于另外 $20 \%$ 的数据，$t = 0$; 对于 $100 \%$ 的数据，$op = \{0, 1 \}, 1 \le n, q \le 10^5, 0 \le l < r \le n, 1 \le d_i, r, g \le 10^9$ 。