题目背景

因为写博客，小 A 欠下了很多题没有补。

题目描述

小 A 一共有 $n$ 道题目没有补。评估后，他认为第 $i$ 题的难度为 $x_i$。

同时，他对自己的水平有评估值 $w$。他的水平会波动，因此 $w$ 会改变。

小 A 认为补难度和自己水平相近的题目（相差不超过 $b_1$）能带来收益 $inc$；相反，如果相差过大（相差超过 $b_2$）则浪费了时间，导致负收益 $dec$。因此，补第 $i$ 道题的收益为

保证 $b_1 \leq b_2$ 且 $dec < 0 < inc$。

此外，小 A 有一些喜欢和讨厌的题。如果他没有补任何喜欢的题，或补了任何讨厌的题，就会不高兴。

小 A 将选择一段编号连续的题目进行补题。他希望补每道题的收益之和最大，并且补完题目后不会不高兴。请你告诉他这个最大值。

任意询问之间独立。

输入格式

第一行一个整数 $S$，表示该测试点的 Subtask 编号。

第二行七个整数 $n, q, w, b_1, b_2, inc, dec$，其中 $q$ 表示事件数量。

第三行 $n$ 个整数 $x_1, x_2, \cdots, x_n$。

接下来若干行，每一行或三行表示一次事件：

• 首先一个整数 $op\in \{1, 2\}$。
• 若 $op = 1$，则接下来两个整数 $l, h$，表示喜欢的题目数量和讨厌的题目数量；接下来一行 $l$ 个整数 $il_1, il_2, \cdots, il_l$，表示喜欢的题目编号；接下来一行 $h$ 个整数 $ih_1, ih_2, \cdots, ih_h$，表示讨厌的题目编号。保证任意 $il_i \neq ih_j$。
• 若 $op = 2$，则接下来一个整数 $w$，表示新的水平评估值。

输出格式

对于每次 $op = 1$ 的事件，输出一行一个整数表示答案。

0
7 7 1 2 3 2 -3
1 0 6 4 8 2 2
1 1 1
4
3
1 2 0
3 4

1 2 0
2 4

2 1064
1 1 0
1

2 5
1 2 2
2 7
4 6

1
2
4
-3
0

提示

「样例解释」

$w = 1$ 时，每道题目的收益分别为 $2, 2, -3, 0, -3, 2, 2$。

第一次询问必须要补第 $4$ 题，不能补第 $3$ 题，最优方案为 $[4, 7]$，收益为 $1$。

第二次询问必须要补第 $3$ 题或第 $4$ 题，最优方案为 $[1, 7]$，收益为 $2$。

第三次询问必须要补第 $2$ 题或第 $4$ 题，最优方案为 $[1, 2]$，收益为 $4$。

$w = 1064$ 时，所有题目的收益均为 $-3$。

第四次询问必须要补第 $1$ 题，最优方案为 $[1, 1]$，收益为 $-3$。

$w = 5$ 时，每道题目的收益分别为 $-3, -3, 2, 2, 0, 0, 0$。

第五次询问必须要补第 $2$ 题或第 $7$ 题，不能补第 $4$ 题和第 $6$ 题，最优方案为 $[7, 7]$，收益为 $0$。

「数据范围与约定」

本题采用捆绑测试。

• Subtask #1（7 points）：$n, q\leq 100$。
• Subtask #2（12 points）：$n, q\leq 500$。依赖 Subtask #1。
• Subtask #3（20 points）：$n, q\leq 4 \times 10 ^ 3$。依赖 Subtask #2。
• Subtask #4（25 points）：$w, x_i \leq 100$。
• Subtask #5（11 points）：$l = 1$，$h = 0$。
• Subtask #6（15 points）：$w, x_i \leq 10 ^ 5$。依赖 Subtask #4。
• Subtask #7（10 points）：无特殊限制。依赖 Subtask #3，#5，#6。

对于 $100\%$ 的数据：

• $1\leq n, q \leq 10 ^ 5$。
• $0\leq w, x_i \leq 10 ^ 9$，$0\leq b_1 \leq b_2$ 且 $b_2$ 不大于 $w, x_i$ 上界的一半。
• $-10 ^ 4 \leq dec < 0 < inc \leq 10 ^ 4$。
• $1\leq l, il_i, ih_j \leq n$，$0 \leq h < n$，$l + h\leq 5$。
• 保证 $il$，$ih$ 递增，且一组询问每个下标至多出现一次。

「帮助与提示」

请注意 IO 优化。

「题目来源」

• Sweet Round 8 C
• Idea & Solution：tzc_wk。
• Tester：Alex_Wei & chenxia25。