Dancing Elephants

Dancing Elephants is a spectacular show in Pattaya featuring n elephants performing in a single line, known as the stage.

After years of training, the elephants have mastered numerous dance moves. Each show consists of a sequence of acts, where in each act, one elephant performs a dance move, potentially changing its position on the stage.

The show producers aim to create a photo album capturing the entire show. They plan to take pictures of all the elephants after each act.

At any point during the show, some elephants might be standing in the same position, meaning they are simply adjacent to each other.

A single camera can capture a group of elephants only if all their positions fit within a segment of length l (including both boundaries of the segment). Since elephants can be spread across the stage, multiple cameras might be necessary to photograph all the elephants simultaneously.

For instance, if l = 10 and the elephants are positioned at 10, 15, 17, and 20, one camera is sufficient to photograph all the elephants, as illustrated below (elephants are shown as triangles, cameras as trapezoids).

In the next act, the elephant at position 15 moves to position 32. Now, at least two cameras are required to capture all the elephants simultaneously.

In the subsequent act, the elephant at position 10 moves to position 7. In this scenario, 3 cameras are needed to photograph all the elephants.

Your task is to determine the minimum number of cameras required to photograph all the elephants after each act.

Input

The first line of the input contains three non-negative integers n, l, and m (0 ≤ n ≤ 15 $\times$ 10^4, 0 ≤ l ≤ 10^9, 0 ≤ m ≤ 15 $\times$ 10^4). The following n lines each contain one integer x_i, representing the position of each elephant (0 ≤ x_i ≤ 10^9). All input positions are guaranteed to be sorted. Note that during the dance, the order of the elephants may change. The next m lines each contain two integers i and y, indicating that in the corresponding act, the elephant numbered i moves to the position with coordinate y. It is guaranteed that y satisfies the constraint: 0 ≤ y ≤ 10^9.

Output

Output m lines, each containing a single number: the minimum number of cameras needed to photograph all the elephants after each act.

Examples