The World of Genshin consists of two linear cities, with each city being able to be represented on a number line. Both cities A and B have buildings from positions $1$ to $L$. It takes $1$ hour to travel between adjacent buildings.

In order to connect the cities together, $N$ teleporters have been created. The $i$-th teleporter connects the position $P_i$ in both cities. By using the teleporter, citizens can travel from position $P_i$ in city A to the same position in city B or vice versa. All teleporters take negligible time.

However, the Genshin Government plans to create more teleporters to increase the convenience of travelling. The government proposes $Q$ plans, with each plan consisting of $M_i$ teleporters at positions $T_{i,j}$.

They would like to figure out the usefulness of each new teleporter in the plans. Note that all $M_i$ teleporters are placed before the usefulness is calculated and each plan is independent.
Let $R_{i, j}$ be the time of the fastest route from position $i$ of city A to reach position $j$ of city B. The usefulness of a teleporter is defined as the number of $i, j$ where there exists a route of duration $R_{i,j}$ that uses this teleporter.

Help the Genshin Government deal with this linear dilemma!

Input

The first line consists of three integers, $N$, $Q$ and $L$.
The next line consists of $N$ integers $P_i$.
The following $Q$ lines have one integer $M_i$, followed by $M_i$ more integers $T_{i,j}$.

Output

For each plan, output $M_i$ integers: the usefulness of each new teleporter.

Constraints

For all subtasks:
$1\le N, Q\le 2\times 10^5$
$1\le P_i, T_{i,j} \le L\le 10^9$
$P_i\le P_{i+1}, T_{i,j}\le T_{i,j+1}$
$0\le M_i \le 2\times 10^5$
$\sum M_i \le 2\times 10^5$
All teleporters in a plan have unique positions.

Subtask 1 (11%): $Q=1, N+M_i=L$
Subtask 2 (23%): $1\le N, Q, L \le 1000, M_i=1$
Subtask 3 (27%): $M_i=1$
Subtask 4 (39%): No additional constraints