问题描述

B 市的地铁系统最近试点了“闸机常开”策略。“闸机常开”策略是指，在乘客核销 乘车凭据之前， 闸机就保持开放状态。如果乘客没有核销乘车凭据就试图通过闸机， 则 闸机会在乘客通过前关闭以阻止乘客通过， 所以乘客并不能因此逃票。而如果乘客成功 核销了乘车凭据， 则乘客无需等待闸机开放就可以通过。这一策略旨在减少乘客通过闸 机的用时，以减少乘车高峰期时车站内的拥堵。 现在 B 市收集了 n 天的乘车记录，记录中包含了每天的乘客。B 市通过调研发现， 乘客要在一次乘车之后，才会适应这一新策略。具体来说， 当一个乘客在这 n 天内第一 次乘车时，会尝试硬闯闸机被阻拦， 导致浪费 a 单位的时间，不会节省时间。当同一乘 客再次乘车时， 会在正常核销乘车凭据后快速通过， 得以节省 b 单位的时间， 不会浪费 时间。B 市会对每一天评估这一策略带来的净时间收益， 即所有乘客节省的时间的总和 减去所有乘客浪费的时间的总和。 B 市还发现，每 m 个第一次乘车的乘客中，就会有一个乘客因为对新策略感到迷 惑而进行投诉。具体来说，在所有的 n 天中，第 m, 2m, 3m, . . . 个第一次乘车的乘客会 进行投诉。为了计入投诉带来的影响，B 市经过研讨决定对每天算出一个总体收益值。 设一天的净时间收益为 t，当天收到投诉的数量为 k，B 市定义了一个投诉系数 s，并定 义当天的总体收益值为 t − sk。 现在给你每天乘客的编号，你需要求出每天的总体收益值。

Format

Input

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

Output

输出 n 行，第 i 行包含一个整数，表示第 i 天的总体收益值。

Samples

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

‐8
‐3
0
‐2
4

【样例 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
1 1 1 0
0
2 1 1

0
0

【样例 2 解释】 • 第一天：没有乘车记录，总体收益值为 0。 • 第二天：浪费的时间为 1，节省的时间为 1。有一次投诉，但是投诉系数为 0，所 以对结果没有影响。总体收益值为 0

Limitation

1s, 1024KiB for each test case.