Mỗi pháp sư sống tại một độ cao \(H_i\) khác nhau. Khoảng cách giữa hai độ cao là trị tuyệt đối của hiệu giữa chúng.

Một lời nguyền khiến các pháp sư không còn tin tưởng nhau. Ban đầu, không cặp pháp sư nào tin tưởng nhau. Cuối mỗi ngày, đúng một cặp pháp sư bắt đầu hoặc ngừng tin tưởng nhau. Tại mọi thời điểm, mỗi pháp sư tin tưởng không quá \(D\) người khác. Ta biết cặp pháp sư thay đổi quan hệ vào cuối từng ngày.

Kẻ trộm đã nói công thức của một lọ thuốc cho một pháp sư xấu xa vào ngày \(V\). Kẻ trộm đến thăm nhà một người bạn mà mình tin tưởng, còn pháp sư xấu xa đến thăm nhà một người bạn mà người đó tin tưởng. Hai người bạn này có thể là cùng một người, và cũng có thể chính họ đã đến thăm nhà của nhau.

Với mỗi giả thuyết rằng kẻ trộm là \(X\), pháp sư xấu xa là \(Y\), và lời thì thầm được truyền vào ngày \(V\), hãy tìm khoảng cách nhỏ nhất mà lời thì thầm phải truyền qua. Cụ thể, lấy nhỏ nhất \(|H_{X'}-H_{Y'}|\) trên mọi cặp \(X',Y'\) sao cho vào ngày \(V\), \(X'\) được \(X\) tin tưởng và \(Y'\) được \(Y\) tin tưởng. Nếu \(X'=Y'\), khoảng cách là \(0\). Nếu \(X\) hoặc \(Y\) không tin tưởng ai vào ngày đó, câu trả lời là \(10^9\).

LQDOJ cung cấp toàn bộ lịch sử thay đổi và các câu hỏi trong dữ liệu vào. Hãy trả lời các câu hỏi theo đúng thứ tự.

Dữ liệu vào

Dòng đầu gồm bốn số nguyên \(N,D,U,Q\): số pháp sư, giới hạn số người được tin tưởng, số ngày có thay đổi và số câu hỏi.

Dòng thứ hai gồm \(N\) số nguyên \(H_i\).

Mỗi dòng trong \(U\) dòng tiếp theo gồm hai số nguyên \(A_i,B_i\), là cặp pháp sư có quan hệ tin tưởng bắt đầu hoặc kết thúc vào cuối ngày \(i\).

Mỗi dòng trong \(Q\) dòng cuối gồm ba số nguyên \(X,Y,V\), là hai pháp sư trong giả thuyết và ngày cần xét.

Các chỉ số pháp sư bắt đầu từ \(0\). Ở ngày \(0\), chưa có cặp nào tin tưởng nhau. Cặp \((A_i,B_i)\) thay đổi trạng thái từ ngày \(i\) sang ngày \(i+1\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(i\) là khoảng cách nhỏ nhất ứng với câu hỏi thứ \(i\).

Ví dụ

6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4
3 0 8
0 5 5
3 0 11

26
0
1000000000
14

Hình dưới minh họa bốn câu hỏi trong ví dụ.

Hình tiếp theo minh họa các quan hệ tin tưởng thay đổi qua từng ngày.

Ràng buộc

• \(2\le N\le10^5\).
• \(1\le D\le500\).
• \(0\le U\le2\cdot10^5\).
• \(1\le Q\le5\cdot10^4\).
• \(0\le H_i\le10^9\).
• \(0\le A_i,B_i,X,Y<N\).
• \(X\ne Y\) và \(A_i\ne B_i\).
• Mọi thay đổi đều bảo đảm mỗi pháp sư tin tưởng không quá \(D\) người tại bất kỳ thời điểm nào.
• Các giá trị \(A_i,B_i\) xác định đúng một cặp bắt đầu hoặc ngừng tin tưởng nhau.
• \(0\le V\le U\).

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(17\) điểm: \(Q,U\le1000\).
3. \(14\) điểm: \(V=U\) trong mọi câu hỏi.
4. \(18\) điểm: \(H_i\in\{0,1\}\) với mọi \(i\).
5. \(21\) điểm: \(U,N\le10000\).
6. \(30\) điểm: Không có ràng buộc nào khác.