题目描述

B 市的地铁系统最近试点了“闸机常开”策略。“闸机常开”策略是指，在乘客核销乘车凭据之前， 闸机就保持开放状态。如果乘客没有核销乘车凭据就试图通过闸机， 则闸机会在乘客通过前关闭以阻止乘客通过， 所以乘客并不能因此逃票。而如果乘客成功核销了乘车凭据， 则乘客无需等待闸机开放就可以通过。这一策略旨在减少乘客通过闸机的用时，以减少乘车高峰期时车站内的拥堵。

现在 B 市收集了 n 天的乘车记录，记录中包含了每天的乘客。B 市通过调研发现，乘客要在一次乘车之后，才会适应这一新策略。具体来说， 当一个乘客在这 n 天内第一次乘车时，会尝试硬闯闸机被阻拦， 导致浪费 a 单位的时间，不会节省时间。当同一乘客再次乘车时， 会在正常核销乘车凭据后快速通过， 得以节省 b 单位的时间， 不会浪费时间。B 市会对每一天评估这一策略带来的净时间收益， 即所有乘客节省的时间的总和减去所有乘客浪费的时间的总和。

B 市还发现，每 m 个第一次乘车的乘客中，就会有一个乘客因为对新策略感到迷惑而进行投诉。具体来说，在所有的 n 天中，第 m, 2m, 3m, . . . 个第一次乘车的乘客会进行投诉。为了计入投诉带来的影响，B 市经过研讨决定对每天算出一个总体收益值。设一天的净时间收益为 t，当天收到投诉的数量为 k，B 市定义了一个投诉系数 s，并定义当天的总体收益值为 t − sk。

现在给你每天乘客的编号，你需要求出每天的总体收益值。

输入格式

从文件 $metro.in$ 中读入数据。 第一行包含一个整数 $n$，表示乘车记录的天数。 之后一行包含四个整数 $a,b,m, s$，含义如题目所述。 之后 $n$ 行，每行的第一个整数为 $l$，表示当天乘车记录的数量， 之后有 $l$ 个整数，表示每条乘车记录中乘客的编号。相同的编号代表相同的乘客， 不同的编号代表不同的乘客。

输出格式

输出到文件 $metro. out$ 中。 输出 $n$ 行，第 $i$ 行包含一个整数，表示第 $i$ 天的总体收益值。

样例 #1

样例输入 #1

5
2 1 2 3
4 1 2 1 3
3 1 1 4
3 5 1 4
4 1 9 1 9
4 1 2 3 4

样例输出 #1

‐8
‐3
0
‐2
4

样例 #2

样例输入 #2

2
1 1 1 0
0
2 1 1

样例输出 #2

0
0

样例 #3

样例输入 #3

见选手目录下的 metro/metro3.in。

样例输出 #3

见选手目录下的 metro/metro3.ans。

样例 #4

样例输入 #4

见选手目录下的 metro/metro4.in。

样例输出 #4

见选手目录下的 metro/metro4.ans。

提示

样例1解释 ：

第一天：有 3 条记录中的乘客是第一次乘车，浪费了 6 单位的时间。有 1 条记录中的乘客不是第一次乘车，节省了 1 单位的时间。第 2 个第一次乘车的乘客进行了投诉。这一天的总体收益值为 (1 − 6) − 3 × 1 = −8。

• 第二天：有 1 条记录中的乘客是第一次乘车，浪费了 2 单位的时间。有 2 条记录中的乘客不是第一次乘车，节省了 2 单位的时间。第 4 个第一次乘车的乘客进行了投诉。这一天的总体收益值为 (2 − 2) − 3 × 1 = −3。

• 第三天：有 1 条记录中的乘客是第一次乘车，浪费了 2 单位的时间。有 2 条记录中的乘客不是第一次乘车，节省了 2 单位的时间。没有乘客进行投诉。这一天的总体收益值为 (2 − 2) − 3 × 0 = 0。

• 第四天：有 1 条记录中的乘客是第一次乘车，浪费了 2 单位的时间。有 3 条记录中的乘客不是第一次乘车，节省了 3 单位的时间。第 6 个第一次乘车的乘客进行了投诉。这一天的总体收益值为 (3 − 2) − 3 × 1 = −2。

• 第五天：没有乘客是第一次乘车，没有浪费时间。有 4 条记录中的乘客不是第一次乘车，节省了 4 单位的时间。没有乘客进行投诉。这一天的总体收益值为 (4 − 0) − 3 × 0 = 4。

样例2解释 ： • 第一天：没有乘车记录，总体收益值为 0。

• 第二天：浪费的时间为 1，节省的时间为 1。有一次投诉，但是投诉系数为 0，所以对结果没有影响。总体收益值为 0。

样例3提示 ： 该样例满足测试点 6 的限制。

样例4提示 ： 该样例满足测试点 10 的限制。

数据范围： 设 L 表示每一天对应的 l 的总和。 对于所有测试数据， 保证：$1 ≤ n ≤ 10^5$，$1 ≤ a,b, m ≤ 10$，$0 ≤ s ≤ 10$，$0 ≤ L ≤ 5n$， 乘客的编号在 1 到 L 之间。