Điệu nhảy của VOI là một chương trình tạp kỹ ở Pattaya với \(N\) chú voi nhảy trên một đường thẳng được gọi là sân khấu.

Sau nhiều năm huấn luyện, những chú voi trong chương trình này đã có khả năng nhảy nhiều điệu nhảy tuyệt vời khác nhau. Chương trình gồm có nhiều màn. Ở mỗi màn, có đúng một chú voi biểu diễn một điệu nhảy dễ thương trong lúc di chuyển sang một vị trí khác.

Nhà sản xuất chương trình muốn tạo nên một quyển sách ảnh gồm những bức ảnh của toàn bộ chương trình. Sau mỗi màn, họ muốn chụp những bức ảnh của tất cả chú voi mà khán giả có thể nhìn thấy.

Tại mọi thời điểm của chương trình, có thể có nhiều chú voi cùng đứng tại một vị trí. Khi đó, chúng đơn giản đứng phía sau nhau tại cùng một vị trí.

Một chiếc máy ảnh có thể chụp một nhóm các chú voi khi và chỉ khi tất cả các vị trí của nhóm voi đấy đều nằm trên một đoạn độ dài \(L\) (bao gồm cả hai đầu mút). Vì những chú voi có thể đứng dàn trải khắp sân khấu, cần phải dùng nhiều máy ảnh để đồng loạt chụp nhiều bức ảnh cùng một lúc tất cả các chú voi.

Ví dụ, giả sử rằng \(L = 10\) và các chú voi đang đứng ở vị trí \(10, 15, 17\) và \(20\) trên sân khấu. Tại thời điểm này, chỉ cần một chiếc camera duy nhất đã có thể chụp hết cả bốn chú voi như hình dưới đây. (Voi được thể hiện bằng hình tam giác, camera được thể hiện bằng hình thang.)

Ở màn sau, chú voi ở vị trí \(15\) di chuyển sang vị trí \(32\). Sau màn này, chúng ta cần ít nhất hai chiếc máy ảnh để chụp hình.

Ở màn sau, chú voi ở vị trí \(10\) di chuyển sang vị trí 7. Với sự sắp xếp vị trí mới này, chúng ta cần ba chiếc camera để chụp hết tất cả chú voi.

Trong bài này, bạn hãy xác định sỗ lượng máy ảnh cần thiết để chụp hết tất cả chú voi sau mỗi màn. Lưu ý rằng số lượng máy ảnh cần thiết có thể tăng, giảm hoặc giữ nguyên sau mỗi màn.

Nhiệm vụ

Bạn hãy viết một chương trình nhận vào các thông số sau:

• \(N\) - số lượng chú voi. Các chú voi được đánh số từ \(0\) tới \(N-1\).
• \(L\) - độ dài của đoạn dài nhất có thể được chụp bằng một chiếc camera. Bạn có thể giả sử rằng \(L\) là một số nguyên sao cho \(0 \leq L \leq 1\ 000\ 000\ 000\).
• \(X\) - một mảng một chiều gồm các số nguyên biểu diễn vị trí ban đầu của mỗi chú voi. Với mọi \(0 \leq i < n\), chú voi thứ \(i\) bắt đầu từ vị trí \(X[i]\). Các vị trí ban đầu được sắp xếp sẵn. Cụ thể, bạn được đảm bảo rằng \(0 \leq X[0] \leq \dots \leq X[N-1] \leq 1\ 000\ 000\ 000\). Lưu ý rằng trong lúc nhảy thì những chú voi có thể thay đổi vị trí với nhau.

Sau đó sẽ có \(M\) lần gọi cập nhật, mỗi lần gồm những thông số sau:

• \(i\) - chỉ số của chú voi di chuyển trong màn này.
• \(y\) - vị trí mà chú voi \(i\) sẽ đứng sau khi kết thúc màn. Bạn được đảm bảo rằng \(y\) là một số nguyên sao cho \(0 \leq y \leq 1\ 000\ 000\ 000\).

Thao tác trên sẽ được gọi nhiều lần. Mỗi lần gọi sẽ ứng với một màn riêng lẻ (được biểu diễn sau tất cả các màn trước đó). Mỗi lần gọi cần trả về số lượng tối thiểu máy ảnh cần thiết để chụp được hết tất cả chú voi sau mỗi màn tương ứng.

Dữ liệu đầu vào

• Dòng \(1\): \(N, L\) và \(M\).
• Dòng \(2\) tới \(N+1\): các vị trí ban đầu, tức dòng \(k+2\) chứa \(X[k]\) với \(0 \leq k < N\).
• Dòng \(N+2\) tới \(N+M+1\): thông tin của \(M\) màn nhảy; tức dòng \(N+1+j\) lần lượt chứa hai số \(i[j]\) và \(y[j]\), cách nhau bởi một dấu cách, cho biết rằng ở màn thứ \(j\) chú voi \(i[j]\) nhảy tới vị trí \(y[j]\), với \(1 \leq j \leq M\).

Điểm số

Subtask 1 (10 điểm)

• Có đúng \(N=2\) chú voi
• Tất cả vị trí của các chú voi từ ban đầu và sau mỗi màn đều khác nhau.
• Truy vấn cập nhật sẽ được gọi tối đa \(100\) lần.

Subtask 2 (16 điểm)

• \(1 \leq N \leq 100\)
• Tất cả vị trí của các chú voi từ ban đầu và sau mỗi màn đều khác nhau.
• Truy vấn cập nhật sẽ được gọi tối đa \(100\) lần.

Subtask 3 (24 điểm)

• \(1 \leq N \leq 50\ 000\)
• Tất cả vị trí của các chú voi từ ban đầu và sau mỗi màn đều khác nhau.
• Truy vấn cập nhật sẽ được gọi tối đa \(50\ 000\) lần.

Subtask 4 (47 điểm)

• \(1 \leq N \leq 70\ 000\)
• Các chú voi có thể cùng đứng trùng vị trí.
• Truy vấn cập nhật sẽ được gọi tối đa \(70\ 000\) lần.

Subtask 5 (3 điểm)

• \(1 \leq N \leq 150\ 000\)
• Các chú voi có thể cùng đứng trùng vị trí.
• Truy vấn cập nhật sẽ được gọi tối đa \(150\ 000\) lần.

Ví dụ

4 10 5
10
15
17
20
2 16
1 25
3 35
0 38
2 0

1
2
2
2
3