Background

Translated from XXVIII Olimpiada Informatyczna - III etap Surowa zima。

d1t3。

Problem Description

There is a road of length $l$ meters (a number line). There are $n$ charging stations on the road. Every day, the entire road (coordinates $[0,l]$) is covered with snow.

There is a machine that can clear snow. With one charge, it can clear at most $k$ meters of snow. Snow clearing is done at the same time as moving; see the sample explanation. The machine can move 1 meter per second, and charging takes no time.

In short, moving without clearing snow does not consume energy and takes 1 second; moving while clearing snow consumes $\bold{\frac1k}$ of the maximum energy and takes 1 second; clearing snow requires moving.

You are given the machine’s initial position each day. The machine starts with no energy. For each day, find the minimum time to clear all the snow. The final position can be anywhere.

There are updates: charging stations may break or be repaired (before day 1, all are working), but it is guaranteed that every day there is at least one working charging station (so it is never impossible to finish).

Input Format

The first line contains four integers $n,l,k,d$.

The second line contains $n$ integers $x_1,x_2,\dots,x_n$, representing the positions of the charging stations. It is guaranteed that $0\leq x_1<x_2<\dots<x_n\leq l$.

The next $3d$ lines describe the events over $d$ days:

• The first line contains three integers $z,u,p$, representing the number of charging stations repaired last night, the number that broke, and the initial position of the machine.
• The second line contains $z$ integers, the indices of the repaired charging stations.
• The third line contains $u$ integers, the indices of the broken charging stations.

Output Format

Output $d$ lines, each with one integer, the answer for that day.

3 5 2 1
2 3 5
0 1 3

2

9

5 12 1 5
1 3 6 9 11
0 1 1

1
1 1 3
1
2
1 1 6
2
3
1 1 9
3
4
1 1 11
4
5

33
33
36
33
33

11 100 1 26
0 10 20 30 40 50 60 70 80 90 100
0 5 0

2 4 6 8 10
5 6 4
2 4 6 8 10
1 3 5 7 9 11
6 5 8
1 3 5 7 9 11
2 4 6 8 10
5 6 12
2 4 6 8 10
1 3 5 7 9 11
6 5 16
1 3 5 7 9 11
2 4 6 8 10
5 6 20
2 4 6 8 10
1 3 5 7 9 11
6 5 24
1 3 5 7 9 11
2 4 6 8 10
5 6 28
2 4 6 8 10
1 3 5 7 9 11
6 5 32
1 3 5 7 9 11
2 4 6 8 10
5 6 36
2 4 6 8 10
1 3 5 7 9 11
6 5 40
1 3 5 7 9 11
2 4 6 8 10
5 6 44
2 4 6 8 10
1 3 5 7 9 11
6 5 48
1 3 5 7 9 11
2 4 6 8 10
5 6 52
2 4 6 8 10
1 3 5 7 9 11
6 5 56
1 3 5 7 9 11
2 4 6 8 10
5 6 60
2 4 6 8 10
1 3 5 7 9 11
6 5 64
1 3 5 7 9 11
2 4 6 8 10
5 6 68
2 4 6 8 10
1 3 5 7 9 11
6 5 72
1 3 5 7 9 11
2 4 6 8 10
5 6 76
2 4 6 8 10
1 3 5 7 9 11
6 5 80
1 3 5 7 9 11
2 4 6 8 10
5 6 84
2 4 6 8 10
1 3 5 7 9 11
6 5 88
1 3 5 7 9 11
2 4 6 8 10
5 6 92
2 4 6 8 10
1 3 5 7 9 11
6 5 96
1 3 5 7 9 11
2 4 6 8 10
5 6 100
2 4 6 8 10
1 3 5 7 9 11

1090
1096
1098
1092
1094
1100
1094
1092
1098
1096
1090
1096
1098
1092
1094
1100
1094
1092
1098
1096
1090
1096
1098
1092
1094
1100

见附件

见附件

见附件

1000000000000000000
2001007996000

Hint

Sample explanation: $3\rightarrow2_{充电}\Rightarrow0\rightarrow2_{充电}\Rightarrow4\rightarrow5_{充电}\Rightarrow4$。$\rightarrow$ means moving, and $\Rightarrow$ means moving while clearing snow.

Constraints: for all testdata, $1\leq n\leq 250000$, $1\leq l\leq 10^9$, $1\leq k\leq l$, $1\leq d\leq 250000$, $\sum z,\sum u\leq 500000$.

Translated by ChatGPT 5