Winter in Byteotia this year is perfect for building snowmen. However, what is good for our cheerful friends is not liked by road workers, and especially not by Baltazar, who is responsible for clearing the main road in the city.

A road of length $\ell$ meters is covered with snow every night. The fearless Baltazar has at his disposal an electric snowplow capable of clearing $k$ meters of road on a single charge. There are $n$ charging stations along the road that Baltazar can use. Unfortunately, every night brings surprises, and heavy snowfall can break or mysteriously repair broken stations (though at least one station remains functional each time). Before the first blizzard, all charging points were functional. Every night, the wind also takes its toll, blowing the snowplow to various places. After the night, the snowplow loses all its power and must be recharged. Baltazar never knows what to expect the next day.

We will define positions on the road as the distance in meters from the beginning of the road; the $i$-th charging station is located at point $x_i$. Traveling one meter of the road (whether clearing it or not) takes Baltazar one second. The snowplow consumes power only for removing snow; Baltazar moves it manually. The charging time of the snowplow at functional charging points is negligible. Baltazar can turn back at any point on the road.

What is the minimum time in which Baltazar is able to clear the entire road each morning? Baltazar starts work every day at the snowplow, but he can finish work at any point on the road.

Input

The first line of the input contains four integers $n, \ell, k$ and $d$ ($1 \le n \le 250\,000$, $1 \le \ell \le 10^9$, $1 \le k \le \ell$, $1 \le d \le 250\,000$) denoting the number of charging stations, the length of the road, the battery capacity of the snowplow, and the number of days Baltazar will have to clear snow.

The second line contains a sequence of $n$ integers $x_1, x_2, \dots, x_n$ ($0 \le x_1 < x_2 < \dots < x_n \le \ell$), denoting the positions of the consecutive charging stations.

The next $3d$ lines contain descriptions of consecutive nights and days; each description consists of three lines.

The first line of the description contains three integers $z, u$ and $p$ ($0 \le z, u \le n$, $0 \le p \le \ell$) denoting the number of stations that magically repaired themselves overnight, the number of stations that broke down, and the location where the snowplow was blown.

The second line of the description contains an increasing sequence of $z$ integers $a_1, \dots, a_z$ ($1 \le a_i \le n$) denoting the indices of the stations that were mysteriously repaired that night. These stations were previously broken.

The third line of the description contains an increasing sequence of $u$ integers $b_1, \dots, b_u$ ($1 \le b_i \le n$) denoting the indices of the stations that were broken that night. These stations were previously functional.

The sets $\{a_1, \dots, a_z\}$ and $\{b_1, \dots, b_u\}$ for each night will be disjoint. Note that the second and/or third line of the description may be empty.

The sum of all numbers $z$ and $u$ over all nights does not exceed $500\,000$.

Output

Your program should output $d$ integers in separate lines, representing the shortest time needed to clear the road each consecutive day.

Examples

Input 1

3 5 2 1
2 3 5
0 1 3
2

Output 1

9

Note

Explanation of the example: On the first and only day of work, Baltazar finds the snowplow at a broken station at point 3, then goes to point 2, where he charges the snowplow and clears a piece of length 2 to the left, then returns to point 2, charges and clears a piece of length 2 to the right, then goes to point 5, charges the snowplow and clears a piece of length 1 to the left. He finishes at point 4; this takes him 9 seconds.